М1768. Аэробус

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

Условие

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

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

Решение

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

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

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

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

С.Токарев

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

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

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

  1.  \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!
  2.  \sum\limits_{k=0}^n \left(k-1\right)^2 \cdot p_{n}\left(k\right) = n!

Примечание

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

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

  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$ элементов (число сочетаний).

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

A=\{ a_1,a_2,\ldots,a_n\}\to\{1,2,\ldots,n\} — естественный порядок.

Определение:

Упорядоченный набор n элементов множества назовём перестановкой n элементов этого множества.
(i_1,i_2,\ldots,i_n), i_j \in \{1,2,\ldots,k\}, j=\overline{1,n}. Перестановка (1,2,\ldots,n) называется нормальной. Так же перестановки бывают четными и нечетными.

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

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

Спойлер

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

[свернуть]

Примеры:

  1. В турнире участвуют семь команд. Сколько вариантов распределения мест между ними возможно?
    Ответ: P_{n}=7!=5040
  2. Сколькими способами могут разместиться за круглым столом 10 человек?
    Ответ: P_n=10!=362880

Два числа 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) \mathbf{4}, 5, 1, 3, 6, 2
4<5, 4>1, 4>3, 4<6, 4>2 \Rightarrow 3
2) 4, \mathbf{5}, 1, 3, 6, 2
5>1, 5>3, 5<6, 5>2 \Rightarrow 3
3) 4, 5, \mathbf{1}, 3, 6, 2
1<3, 1<6, 1<2 \Rightarrow 0
4) 4, 5, 1, \mathbf{3}, 6, 2
3<6, 3>2 \Rightarrow 1
5) 4, 5, 1, 3, \mathbf{6}, 2
6>2 \Rightarrow 1
Теперь суммируя результаты получаем, число инверсий в данной перестановке равна:
3+3+0+1+1=8.

[свернуть]

Литература :

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

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


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

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