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

Математики всего мира объясняют принцип Дирихле на примере кроликов и коробочек (в англоговорящих странах используются голуби и коробки). Не будем нарушать эту добрую традицию. Упомянем только, что возникновению этого метода мы обязаны немецкому математику Петеру Густаву Леже Дирихле.

Пусть имеется определенное количество кроликов (m) и коробок (n). Причем количество кроликов больше чем количество коробок (m > n). Разместим всех кроликов по коробкам. Тогда найдется коробка, в которой будет больше одного кролика.

Приведем рассуждения, из которых получим вывод: сперва рассадим по коробкам n кроликов. Количество оставшихся кроликов будет равно m-n. Условия задачи таковы, что после рассадки все кролики находятся в коробках. Следовательно, m-n кроликов мы будем рассаживать в не пустые коробки. А значит, существуют коробки в которых будет более одного кролика. Мы привели простые рассуждения, более строгое доказательство предлагаем проделать самостоятельно, используя метод математической индукции. Основная сложность применения метода Дирихле заключается в трудности определения: что является “кроликом”, а что “коробками”. Давайте разберем ряд задач, которые нам в этом помогут. 

Пример №1. Классический пример - волосы жителей города.

Принцип Дирихле может доказать, что в Алматы живут не менее двух человек с одинаковым количеством волос. Конечно же, мы исключаем лысых людей. Приведем ход рассуждений ниже.

Сперва определим количество людей, проживающих в Алматы. Согласно последним данным переписи населения, в городе проживает 1 552 349 человек. Далее используем факт о том, что количество волос у среднестатистического человека не более 150 000. Давайте отберем из общего числа жителей города ровно по одному человеку, у кого на голове один волос, два волоса и до того, у кого на голове будет 150 000 волос. В итоге мы отберем не более 150 000 человек (ведь может оказаться что остальные жители 1 402 349 имеют от 1 до 150 000 волос). Любой из них может быть причислен к одной из групп (собранных по количеству волос на голове).

Задача №1. 145 семян рассыпаны на поле размером 12 метров на 12 метров. Докажите, что существуют хотя бы два семя, которые упали друг от друга на расстояние меньше чем метра. Подсказка: вспомните теорему Пифагора.

Пример №2. Разноцветные носки и темнота.

Представьте, что все ваши носки могут быть только двух цветов: черного и белого. После очередной стирки все пары носков перемешались. Какое наименьшее количество носков вы должны взять не глядя, чтобы собрать пару одного цвета?

Пусть носки волшебным образом, после того как вы их вытащили, раскладываются согласно своему цвету в соответствующую коробку белую или черную. Пусть первый носок, который вы вытащили, будет белого цвета, теперь подумаем, а если следующий носок окажется тоже белым? В этом случае условие задачи выполнено, но следующий носок может быть и черным. Сделаем еще один ход, попробуем вытащить еще носок, он может быть либо черным, либо белым. Соответственно третий носок точно составит пару одному из предыдущих носков (если пара еще не состоялась). Ответ к нашей задаче - наименьшее количество носков, которое вы должны вытащить при двух цветах равняется трем (3).

Задача №2. Решите задачу из примера №2 при условии, что белых носков 14, а черных 10.

Пример №3. Степень тройки.

В предыдущих примерах мы рассматривали случаи с конечным числом элементов в условии. Попробуем решить следующую задачу:

Докажите, что существует степень тройки (3^a), которая оканчивается цифрами 001.

Степенями тройки выступают числа: 3⁰ = 1, 3¹ = 3, 3² = 9, 3³ = 27, 3⁴ = 81, 3⁵ = 243 и так далее. Разделим эти числа на 1000 и выпишем все возможные остатки (r):

3 ^a = 1000k + r

Например, 3¹⁰ = 59 049 = 59000 + 49 (остаток), 3¹¹ = 177 147 = 177000 + 147 (остаток) и так далее. Так как степеней тройки бесконечно много, то остатков будет от 0 до 999 ровно 1000 штук. Используя принцип Дирихле, мы утверждаем, что найдутся две таких степени тройки, у которых будут одинаковый остаток от деления на 1000. Пусть это будут два числа 3^m и 3ⁿ:

3 ^m = 1000k + r

3 ⁿ = 1000q + r

Посчитаем их разницу: 3^m - 3ⁿ= 3ⁿ(3^(m-n) - 1) = 1000k + r - 1000q - r = 1000(k-q), иначе говоря - произведение 3ⁿ и (3^(m-n) - 1) кратно 1000. Мы знаем, что ни при каких значениях степени n число 3ⁿ не может быть кратным 1000. Следовательно, кратным 1000 должно быть число (3^(m-n) - 1):

3^(m-n) - 1 = 1000(k-q)

или

3^(m-n) = 1000(k-q) +1

Мы доказали что существует степень тройки, которая оканчивается цифрами 001!

Задача №3. Докажите, что существует степень числа 17, которая оканчивается цифрами 0001.