Задача из журнала «Квант» (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].

С.Токарев

Задача из журнала «Квант» (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. Заметим прежде всего, что $$\begin{equation}
   \sum\limits_{k=0}^n p_{n}\left(k\right) = n!,
   \end{equation}
   $$ так как в левой части стоит суммарное число перестановок, имеющих $0,1,\ldots,n$ неподвижных точек, т.е. просто число всех перестановок. Теперь докажем, что при $1 \leqslant k \leqslant n$ $$\begin{equation}
   k \cdot p_{n}\left(k\right) = n \cdot p_{n-1} \cdot \left(k-1\right),
   \end{equation}
   $$ считая, что $p_{0}\left(0\right) = 1 $. Для этого подсчитаем двумя способами число $N$ пар $\left(f,i\right)$, где $f$ — произвольная перестановка $n$ элементов с $k$ неподвижными точками, а $i$ — любая из этих точек $f\left(i\right)=i$. С одной стороны, каждая из этих $p_{n}\left(k\right)$ перестановок входит в $k$ пар, поэтому $N=k \cdot p_{n}\left(k\right)$. Суммируя равенства (2) по $k = 1,\ldots,n$ и учитывая (1) ( с заменой $n$ на $n-1$), получим $$\sum\limits_{k=0}^n k \cdot p_{n}\left(k\right) = n \cdot \sum\limits_{k=1}^n p_{n-1}\left(k-1\right) = n \cdot \left(n-1\right)! = n!$$
2. Докажем сразу более общее тождество $$\begin{equation}
   s\left(n,m\right) = \sum\limits_{k=m}^n \frac {k!}{\left(k-m\right)!} \cdot p_{n}\left(k\right) = n!
   \end{equation}$$ $n \gneq m$, $m = 0,1,2,…$ (по определению, $0!=1$). При $m=0$ оно совпадает с (1), при $m=1$ — с утверждением 1, а при $m=2$ эквивалентно 2, поскольку $$ \begin{multline*} \sum\limits_{k=0}^n \left(k-1\right)^2 \cdot p_{n}\left(k\right) = \sum\limits_{k=0}^n k \cdot \left(k-1\right) \cdot p_{n}\left(k\right) — \sum\limits_{k=0}^n k \cdot p_{n}\left(k\right)+{}\\{}+\sum\limits_{k=0}^n p_{n}\left(k\right) = s\left(n,2\right)-s\left(n,1\right)+s\left(n,0\right). \end{multline*} $$
   Из тождества (2) следует, что при $1\le m\le n\le k$ $$ \begin{multline*} \frac {k!}{\left(k-m\right)!} \cdot p_{n}\left(k\right) = k \cdot \left(k-1\right) \cdot \ldots \cdot \left(k-m+1\right) \cdot p_{n}\left(k\right) = {}\\ {}=n \cdot \left(k-1\right) \cdot \ldots \cdot \left(k-m+1\right) \cdot p_{n-1}\left(k-1\right) = {}\\ {} = n \cdot \left(n-1\right) \cdot \left(k-2\right) \cdot \ldots \cdot \left(k-m+1\right) \cdot p_{n-2}\left(k-2\right)= {}\\ {} = n \cdot \left(n-1\right) \cdot \ldots \cdot (n-m+1) \cdot p_{n-m}\left(k-m\right)= {}\\ {} = \frac {n!}{\left(n-m\right)!} \cdot p_{n-m}\left(k-m\right). \end{multline*} $$ Суммируем эти равенства по $k = 1,\ldots,n$: $$s\left(n,m\right)=\frac {n!}{\left(n-m\right)!} \cdot s\left(n-m,0\right) = n! $$
   Другое доказательство $(3)$ можно получить из почти очевидного соотношения $p_{n}\left(k\right) = C^k_{n} \cdot p_{n-k}\left(0\right)$, где $C^k_{n} = \frac {n!}{k! \left(n-k\right)!}$ — число $k$ -элементных подмножеств множества из $n$ элементов (число сочетаний).