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

Поговорим об очень известном принципе Дирихле. По сути это по-другому сформулированный метод доказательства от противного.

Очень популярна такая формулировка: если нужно поселить 5 котиков в 4 домика, то в каком-то домике окажется по крайней мере 2 котика. Доказывается от противного: предположим, что это неверно, тогда ни в каком домике не окажется 2 или более котиков. Значит, в каждом домике не более одного котика, и тогда всего котиков не больше, чем клеток, то есть не больше 4, противоречие.

Посмотрим, как этот принцип работает в конкретных задачах.

1.  Можно ли написать на доску 11 натуральных чисел так, чтобы никакая разность между выписанными числами не делилась на 10?

Ответ. Нет, нельзя

Решение. Отметим, что разность двух чисел делится на 10 в том случае, если числа оканчиваются на одну и ту же цифру.

Всего существует 10 цифр. Число может оканчиваться на каждую из них. Тогда скажем, что цифры, на которые могут оканчиваться числа — это домики, а 11 выписанных на доску чисел — это котики. Таким образом, два котика попадут в один домик, а значит какие-то два числа будут оканчиваться на одну и ту же цифру.

Следовательно, разность этих чисел будет делиться на 10. Значит, нельзя написать на доску 11 натуральных чисел так, чтобы никакая разность между выписанными числами не делилась на 10.

Рассмотрим пару утверждений:

• Если нужно поселить 21 котика в 4 домика, то в каком-то домике окажется по крайней мере 6 котиков.

  Предположим противное. Пусть в каждом домике не более 5 котиков, тогда суммарно во всех домиках не более котиков. Противоречие.

• Если нужно поселить 57 котиков в 7 домиков, то в каком-то домике окажется по крайней мере 9 котиков.

  Действительно, если в каждом домике не более 8 котиков, то суммарно во всех домиках не более котиков. Противоречие.

Тогда можем сформулировать обобщенный принцип Дирихле:

Если нужно поселить котика в домиков, то в каком-то домике окажется по крайней мере котик.

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

Предположим противное. Пусть в каждом домике не более котиков, тогда суммарно во всех домиках не более котиков. А у нас всего котик. Противоречие. Значит, в каком-то домике окажется по крайней мере котик.

Посмотрим, как обобщенный принцип работает в задачах.

2.  Скитаясь по космосу, Пин встретил 50 инопланетян. Докажите, что среди них есть либо 8 существ, у которых ног поровну, либо 8 существ, у всех из которых разное число ног.

Решение. Предположим, что второе условие не выполнилось. Тогда количество ног у этих инопланетян принимает не больше 7 различных значений.

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

Если же среди инопланетян есть 8 существ с разным числом ног, то задача тоже решена.