Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2003/02/27.pdf Дата изменения: Fri Dec 23 19:27:20 2005 Дата индексирования: Tue Oct 2 00:31:04 2012 Кодировка: Windows-1251 Поисковые слова: вторая космическая скорость

О колпаках, хранящихся в темном чулане
А.МАЛЕЕВ
Дирихле . В шутливой форме он звучит, например, так: 'Если шесть зайцев посадить в пять клеток, то обязательно найдется клетка, в которой будут сидеть не менее двух зайцев'. (При этом, естественно, подразумевается, что целостность зайцев не нарушается.) В более общем виде принцип Дирихле можно сформулировать таким образом: 'Если kn + 1 или более зайцев посадить в n клеток, то обязательно найдется клетка, в которой будут сидеть не менее k + 1 зайцев'. Это утверждение доказывается на редкость легко. Допустим, что после рассадки в каждой клетке оказалось не более k зайцев. Тогда в n клетках сидят не более kn зайцев. Но это противоречит условию, что зайцев kn + 1 или более. Существует много задач, в основе которых лежит этот принцип, носящий имя знаменитого немецкого математика 1. Рассмотрим, например, такую. Задача 1. В ящике комода хранятся красные, желтые и зеленые носки. Какое наименьшее число носков надо взять наугад из комода, чтобы среди них обязательно оказались четыре носка одного цвета? Решение. Поскольку в условии ничего не сказано о том, сколько носков каждого цвета лежит в комоде, то следует предполагать, что возможны любые (в том числе самые худшие) варианты. Поэтому 9 носков нам может не хватить, ибо среди них могут оказаться по три носка каждого цвета. А вот 10 носков заведомо хватит. Действительно, у нас имеются 10 'зайцев' (это взятые из комода носки) и 3 'клетки' (это цвета носков). Поскольку 10 = 3 Ч 3 + 1 , то по принципу Дирихле обязательно найдется 'клетка', в которой будут сидеть не менее 4 'зайцев', т.е. обязательно найдутся 4 носка одного цвета. Теперь немного усложним ситуацию. Задача 2. Три поросенка, Ниф-Ниф, Нуф-Нуф и НафНаф, хранят в жестяной коробке красные, желтые и зеленые леденцы. Какое наименьшее число леденцов надо взять наугад из коробки, чтобы каждому поросенку обязательно достались пять леденцов одного цвета? Решение. Покажем, что это наименьшее число 23. Сначала заметим, что 13 = 4 Ч 3 + 1 . Следовательно, в силу принципа Дирихле среди любых 13 или более леденцов (леденцы это 'зайцы') всегда найдутся 5 леденцов одного цвета (цвета это 'клетки'). Поэто1 Петер Густав Лежен Дирихле (18051859) немецкий математик, широко известный своими трудами по аналитической теории чисел, теории функций и математической физике.
4*

'КВАНТ'

ДЛЯ

'МЛАДШИХ'

ШКОЛЬНИКОВ

27

В

Ы, НАВЕРНОЕ, НЕ РАЗ УЖЕ СЛЫШАЛИ О ПРИНЦИПЕ

му из 23 леденцов можно выбрать 5 леденцов одного цвета. Отдадим из Ниф-Нифу. Среди оставшихся 18 леденцов вновь найдутся 5 леденцов одного цвета. Отдадим их Нуф-Нуфу. И, наконец, из последних 13 леденцов опять можно выбрать 5 леденцов одного цвета, которые отдадим Наф-Нафу. Остается показать, что 22 леденцов может не хватить. Для этого предположим, что среди наугад выбранных 22 леденцов оказалось 14 красных, 4 желтых и 4 зеленых. Ясно, что в этом случае только два поросенка могут получить по 5 леденцов одного цвета. По сути те же идеи применим теперь к решению задачи, опубликованной в пятом номере журнала 'Квант' за 2002 год в Конкурсе имени А.П.Савина 'Математика 68'. Здесь мы рассмотрим более общую формулировку, чем была приведена в журнале. Задача 3. В темном чулане N гномов хранят вперемешку колпаки разных цветов, причем колпаков каждого цвета поровну. Проснувшись как-то утром, первый гном попросил m1 колпаков одного цвета. Белоснежка сходила в чулан и отсчитала в темноте наугад столько колпаков, чтобы их наверняка хватило выполнить его просьбу. Но тут проснулись остальные гномы, и второй гном попросил m2 колпаков одного цвета, третий попросил m3 колпаков одного цвета, и так далее, вплоть до последнего гнома, который попросил mN колпаков одного цвета, причем m1 > m2 m3 K K mN . Чтобы выполнить просьбы всех гномов, Белоснежка вынуждена была еще раз сходить в чулан. Какое наибольшее количество цветов могли иметь колпаки, хранящиеся в чулане? Решение. Пусть в чулане хранятся колпаки n разных цветов, причем колпаков каждого цвета поровну и не меньше m1 . Покажем, что если выполнено неравенство
n
t = 1,2,K,N - 1

max

m1 + m2 + K + mt , m1 - mt +1

(1)

то Белоснежке не придется второй раз идти в чулан. Действительно, предположим, что она в первый раз наугад отсчитала в чулане s колпаков. Мы, конечно, не знаем это число, но, чтобы наверняка выполнить просьбу первого гнома, оно обязательно должно удовлетворять соотношению

s (m1 - 1) n + 1 ,

(2)

так как по принципу Дирихле из (m1 - 1) n + 1 колпаков всегда можно выбрать m1 колпаков одного цвета, а вот (m1 - 1) n колпаков может не хватить. Далее, предпо-