М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.

С.Токарев

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *