Задача из журнала «Квант» (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], только если выполняется одно из следующих условий:
- Все пассажиры включены в один цикл;
- Число циклов равно [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].