Processing math: 100%

М1768. Аэробус

Задача из журнала «Квант» (2001 год, 5 выпуск)

Условие

а) Расположите первые [latex]100[/latex] натуральных чисел в таком порядке, чтобы для любых нескольких (но не всех) из этих чисел сумма номеров занятых ими мест не равнялась сумме самих этих чисел.

б*) При посадке в аэробус пассажиры сели куда попало. В итоге все места оказались заняты, а для любого множества, в котором не более [latex]100[/latex] пассажиров, среднее арифметическое номеров занятых ими мест не менее чем на [latex]1[/latex] отличается от среднего арифметического номеров мест, указанных в билетах. Каково наименьшее возможное число мест в таком аэробусе?

Решение

а) Укажем два способа: [latex]100, 1, 2, \ldots, 97, 98, 99[/latex] и [latex]2, 3,4, \ldots, 99, 100, 1[/latex]. Каждый из них дает требуемое расположение чисел, в чем легко непосредственно убедиться.

б) Ответ: [latex]301[/latex] место.
Каждый пассажир включен в один из циклов вида [latex]P_{1}, P_{2}, \ldots , P_{m}[/latex], где [latex]P_{1}, P_{2}, \ldots , P_{m}[/latex] – некоторые пассажиры, причем [latex]P_{i}[/latex]-й пассажир ([latex]i =  1, 2, \ldots , m — 1[/latex]) имеет билет на место, которое занимает [latex]P_{i+1}[/latex]-й пассажир, а [latex]P_{m}[/latex]-й пассажир – на место, которое занимает [latex]P_{1}[/latex]-й пассажир. Если в таком цикле [latex]100[/latex] пассажиров или менее, то все они могли составить одну рассматриваемую группу, для которой среднее арифметическое номеров занимаемых ими мест равно среднему арифметическому номеров мест, указанных в их билетах, что противоречит условию. Поэтому [latex]m \geq 101 + r \geq 202[/latex]. Значит, если число циклов не меньше [latex]3[/latex], то в аэробусе размещаются [latex]303[/latex] или более пассажиров. Заметим далее, что если [latex]P_{k}, P_{k+1}, \ldots , P_{k+r} [/latex]– цепочка пассажиров, последовательно включенных в некоторый цикл, причем номера билетов [latex]P_{k}[/latex]-го и [latex]P_{k+r}[/latex]-го отличаются на [latex]1[/latex], то [latex]r \geq 101[/latex]. Рассматривая цепочку [latex]P_{k+r}, P_{k+r+1} , \ldots , P_{m}, P_{1}, \ldots , P_{k}[/latex], получим неравенство [latex]m — (k + r) + k \geq 101[/latex]. Следовательно, [latex]m \geq 101 + r \geq 202[/latex] , и поэтому число мест в аэробусе может быть меньшим, чем [latex]303[/latex], только если выполняется одно из следующих условий:

  1. Все пассажиры включены в один цикл;
  2. Число циклов равно [latex]2[/latex], причем любые два билета на соседние (по номерам) места принадлежат пассажирам из разных циклов.

Пусть выполнено первое условие. Рассмотрим пассажиров [latex]A_{n}, A_{n+1}[/latex] и [latex]A_{n+2}[/latex] с билетами на [latex]n[/latex]-е, [latex](n + 1)[/latex]-е и [latex](n + 2)[/latex]-е места соответственно. Между [latex]A_{n}[/latex]-м и [latex]A_{n+1}[/latex]-м пассажирами в кратчайшей из цепочек, их соединяющих, имеется не менее [latex]100[/latex] пассажиров, между [latex]A_{n+1}[/latex]-м и [latex]A_{n+2}[/latex]-м также не менее [latex]100[/latex] пассажиров, а между [latex]A_{n+2}[/latex]-м и [latex]A_{n}[/latex]-м либо нет ни одного пассажира, либо имеется не менее [latex]100[/latex]. Значит, если общее число мест меньше [latex]303[/latex], то либо [latex]A_{n}[/latex] сидит на [latex](n + 2)[/latex]-м месте, либо [latex]A_{n+2}[/latex] сидит на [latex]n[/latex]-м месте. Ввиду произвольности номера [latex]n[/latex] имеем (с точностью до направления) цикл [latex]A_{1} A_{3} A_{5} \ldots A_{N}A_{2}A_{4} \ldots A_{N’}[/latex], где [latex]N[/latex] и [latex]N'[/latex] – наибольший нечетный и наибольший четный номера соответственно, а [latex]A_{i}[/latex]–пассажир, занимающий [latex]i[/latex]-е место, [latex]i = 1, 2, \ldots, max ( N, N’)[/latex].Пассажиры, сидящие на местах [latex]N, 2, 4, \ldots , 198[/latex], имеют билеты на места [latex]2, 4, 6, \ldots , 200[/latex], а разность соответствующих средних равна [latex](N — 200) : 100[/latex]. Так как эта разность больше [latex]1[/latex], получаем [latex]N \geq 301[/latex]. Нетрудно убедиться, что цикл [latex] A_{1}A_{3}A_{5} \ldots A_{301}A_{2}A_{4} \ldots A_{300}[/latex] удовлетворяет условиям задачи. Пусть теперь выполнено второе условие, т.е. имеются два цикла, каждый из которых включает всех пассажиров с билетами на места одной четности. Если в каком-нибудь из этих циклов пассажир [latex]A_{n}[/latex] сидит не на [latex](n + 2)[/latex]-м месте, а [latex]A_{n+2}[/latex]– не на [latex]n[/latex]-м месте, то в цикле не менее [latex]202[/latex] пассажиров, а в аэробусе – не менее [latex]403[/latex] мест. В противном же случае имеем (с точностью до направления) цикл [latex]A_{1}A_{3}A_{5} \ldots A_{N}[/latex] , где пассажиры с билетами на места [latex]1,3, 5, \ldots , 199[/latex] сидят на местах [latex]N, 1, 3, \ldots , 197[/latex]; разность соответствующих средних арифметических [latex] (N — 199) :100[/latex] больше [latex]1[/latex], откуда [latex]N \geq 301[/latex].

С.Токарев

M1077. Перестановки с неподвижными точками

Задача из журнала «Квант» (1987 год, выпуск 12)

Пусть [latex]p_{n}\left(k\right)[/latex]  — число перестановок множества из [latex] n (n \geq 1) [/latex] элементов, имеющих ровно k неподвижных точек. Докажите, что:

  1. [latex] \sum\limits_{k=0}^n k \cdot p_{n}\left(k\right) = 0 \cdot p_{n}\left(0\right)+1 \cdot p_{n}\left(1\right)+\ldots+n \cdot p_{n}\left(n\right) = n![/latex]
  2. [latex] \sum\limits_{k=0}^n \left(k-1\right)^2 \cdot p_{n}\left(k\right) = n![/latex]

Примечание

Перестановкой конечного множества S называется взаимно однозначное отображение f множества S на себя; число всех перестановок множества из n элементов равно [latex] n! = 1 \cdot 2 \cdot \ldots \cdot n [/latex]

Доказательство

  1. Заметим прежде всего, что nk=0pn(k)=n!, так как в левой части стоит суммарное число перестановок, имеющих 0,1,,n неподвижных точек, т.е. просто число всех перестановок. Теперь докажем, что при 1kn kpn(k)=npn1(k1), считая, что p0(0)=1. Для этого подсчитаем двумя способами число N пар (f,i), где f — произвольная перестановка n элементов с k неподвижными точками, а i — любая из этих точек f(i)=i. С одной стороны, каждая из этих pn(k) перестановок входит в k пар, поэтому N=kpn(k). Суммируя равенства (2) по k=1,,n и учитывая (1) ( с заменой n на n1), получим nk=0kpn(k)=nnk=1pn1(k1)=n(n1)!=n!
  2. Докажем сразу более общее тождество s(n,m)=nk=mk!(km)!pn(k)=n! nm, m=0,1,2, (по определению, 0!=1). При m=0 оно совпадает с (1), при m=1 — с утверждением 1, а при m=2 эквивалентно 2, поскольку nk=0(k1)2pn(k)=nk=0k(k1)pn(k)nk=0kpn(k)++nk=0pn(k)=s(n,2)s(n,1)+s(n,0).
    Из тождества (2) следует, что при 1mnk k!(km)!pn(k)=k(k1)(km+1)pn(k)==n(k1)(km+1)pn1(k1)==n(n1)(k2)(km+1)pn2(k2)==n(n1)(nm+1)pnm(km)==n!(nm)!pnm(km). Суммируем эти равенства по k=1,,n: s(n,m)=n!(nm)!s(nm,0)=n!
    Другое доказательство (3) можно получить из почти очевидного соотношения pn(k)=Cknpnk(0), где Ckn=n!k!(nk)! — число k -элементных подмножеств множества из n элементов (число сочетаний).

Перестановки. Лемма о числе перестановок длины n


Определение
Упорядоченный набор n элементов множества назовём перестановкой n элементов этого множества.
(i1,i2,,in), ij{1,2,,k}, j=¯1,n. Перестановка (1,2,,n) называется нормальной. Также перестановки бывают четными и нечетными.
A={a1,a2,,an}{1,2,,n} — 
естественный порядок.

Лемма о числе перестановок длины n 
Число перестановок n-элементов множества равна n!, где n — длина перестановки.

Для n=1 это очевидно. Пусть утверждение верно для любого множества из n1 чисел. Все перестановки из n чисел можно разбить на n классов, помещая в один класс лишь те перестановки, которые на первом месте имеют одно и то же число. Число перестановок в каждом классе совпадает с числом перестановок n1 чисел, т. е. равно (n1)!. Следовательно, число всех перестановок из n чисел равно n!.

Примеры:

  1. В турнире участвуют семь команд. Сколько вариантов распределения мест между ними возможно?
    Ответ
  2. Сколькими способами могут разместиться за круглым столом 10 человек?
    Ответ

Два числа i и j образуют инверсию, если i>j, но i стоит в перестановке раньше j.

Пример:

  • (1,2,3,4,5,6) — нормальная перестановка.
  • (1,2,4,5,3,6) — инверсия.

В каждой перестановке можно определить число инверсий в ней, которое можно подсчитать следующим образом: для каждого числа определяют количество стоящих справа чисел, меньших данного числа, и полученные результаты суммируются.

Пример:

Определите число инверсий в данной перестановке: (4,5,1,3,6,2).
Решение

Литература :

  1. Воеводин В.В. Линейная алгебра. М.: Наука, 1980 — стр.123-124.
  2. Белозёров Г.С. Конспект лекций.
  3. Курош А.Г. Курс высшей алгебры. М.: Наука, 1968 — стр.28-36.

Перестановки

Тест на знание темы «Перестановки»


Таблица лучших: Перестановки

максимум из 5 баллов
Место Имя Записано Баллы Результат
Таблица загружается
Нет данных