занятие 17

Тема: Делимость и остатки

4. Принцип Дирихле

     Продолжим работу над применением принципа Дирихле. Тема очень непростая, а первую ее часть усвоили далеко не все. Настоятельно рекомендую хорошо поработать над прошлым занятием еще раз, и только потом перейти к данному занятию.

     Задача 5. В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта.

     Решение. Здесь потребуется применить обобщенный принцип Дирихле, который заключается в следующем.

Если в N клетках сидят не менее kN + 1 кроликов, то в какой-то из клеток сидит по крайней мере k + 1 кролик.

Вот в эту схему решение задачи про яблоки прекрасно укладывается. Ведь 25 = 3 • 8 + 1, то есть в 8 клетках-сортах сидят не менее 25 кролика-ящика, значит, в какой-то клетке-сорте не менее 9 ящиков.

     Задача 6. Дано 8 различных натуральных чисел, не больших 15. Докажите, что среди их положительных попарных разностей есть три одинаковых.

     Решение. 

1. Разности между числами могут принимать значения от 1 до 14, так как все числа различны. Это будут номера клеток. 

2. Кто же будут кроликами? Это пары чисел, для которых составляются разности (каждый раз вычитаем из большего числа меньшее, чтобы разность получалась положительной). 

3. Посчитаем количество таких пар - это комбинаторная задача. Применяем метод "точек". На первом месте может стоять любое из 8 чисел, на втором - любое из оставшихся 7 чисел. Повторы нужно исключить, получаем:

количество пар = (8 • 7) : 2 = 28.

Но 28 кроликов можно спокойно рассадить по 2 в 14 клеток!!! В чем же дело?

Задачи для самостоятельного решения

     Задача 6. Закончите решение задачи. В присланных решениях прошу вас привести полное решение этой задачи, записанное своими словами.

     Задача 7. Докажите, что в любой компании из 5 человек есть двое, имеющие одинаковое число знакомых в этой компании.

Решения и ответы

Задача 6. Итак, у нас имеется 28 кроликов и 14 клеток. Но клетка под номером 14 особенная, в ней может сидеть только один кролик: разность, равная 14, может получиться только в одном случае: 15 - 1. Тогда оставшиеся 27 кроликов должны разместиться в остальных 13 клетках. Работает обобщенный принцип Дирихле:

kN + 1 = 2*13 + 1, k = 2, значит, в какой-то клетке сидит, по крайней мере, 2 + 1 = 3 кролика. Итак, среди попарных разностей данных чисел есть три одинаковых.

Задача 7. Номера клеток - это количество возможных знакомств, это числа от 0 до 4. Но так ли это? Если какой-то человек никого не знает, то не найдется человека, который знает четверых. То есть клетки с номерами 0 и 4 одновременно существовать не могут, и клеток остается 4. А кроликов-людей - 5. Значит, в какой-то клетке сидят 2 кролика, то есть как минимум двое имеют одинаковое количество знакомых.