Мы уже рассказывали вам о методе математической индукции и методе доказательства от противного. Сегодня мы хотим поговорить о принципе Дирихле, несмотря на его простоту и очевидность, данный принцип очень часто используется при доказательстве теорем и решении задач с невероятными на первый взгляд условиями.
Математики всего мира объясняют принцип Дирихле на примере кроликов и коробочек. Не будем нарушать эту добрую традицию. Упомянем только, что возникновению этого метода мы обязаны немецкому математику Петеру Густаву Леже Дирихле.
Пусть имеется определенное количество кроликов (m) и коробок (n). Причем количество кроликов больше чем количество коробок (m > n). Разместим всех кроликов по коробкам. Тогда найдется коробка, в которой будет больше одного кролика.
Приведем рассуждения, из которых получим вывод: сперва рассадим по коробкам n кроликов. Количество оставшихся кроликов будет равно m-n. Условия задачи таковы, что после рассадки все кролики находятся в коробках. Следовательно, m-n кроликов мы будем рассаживать в не пустые коробки. А значит, существуют коробки в которых будет более одного кролика.
Мы привели простые рассуждения, более строгое доказательство предлагаем проделать самостоятельно, используя метод математической индукции. Основная сложность применения метода Дирихле заключается в трудности определения: что является «кроликом», а что «коробками». Давайте разберем ряд задач, которые нам в этом помогут.
Пример №1: КЛАССИЧЕСКИЙ ПРИМЕР — ВОЛОСЫ ЖИТЕЛЕЙ ГОРОДА
Принцип Дирихле может доказать, что в Алматы живут не менее двух человек с одинаковым количеством волос. Конечно же, мы исключаем лысых людей. Приведем ход рассуждений
ниже. Сперва определим количество людей проживающих в Алматы. Согласно последним данным переписи населения в городе проживает 2 211 198 человек.
Далее используем факт о том, что количество волос у среднестатистического человека не более 150 000. Давайте отберем из общего числа жителей города ровно по одному человеку
у кого на голове один волос, два волоса и до того у кого на голове будет 150 000 волос. В итоге мы отберем не более 150 000 человек (ведь может оказаться что остальные жители имеют от 1 до 150 000 волос). Любой из них может быть причислен к одной из групп (собранных по количеству волос на голове).
Пример №2: СТЕПЕНЬ ТРОЙКИ
В предыдущих примерах мы рассматривали случаи с конечным числом элементов в условии. Попробуем решить следующую задачу:
Докажите, что существует степень тройки (3a), которая оканчивается цифрами 001.
Степенями тройки выступают числа: 30 =1, 31= 3, 32 =9, 33 = 27, 34 = 81, 35 = 243 и так далее.
Разделим эти числа на 1000 и выпишем все возможные остатки (r):
3a = 1000k + r
Например, 310 = 59 049 = 59000 + 49 (остаток), 311 = 177 147 = 177000 + 147 (остаток) и так далее.
Так как степеней тройки бесконечно много, то остатков будет от 0 до 999 ровно 1000 штук.
Используя принцип Дирихле, мы утверждаем, что найдутся две таких степени тройки, у которых будут одинаковый остаток от деления на 1000.
Пусть это будут два числа 3m и 3n:
3m = 1000k + r
3n = 1000q + r
Посчитаем их разницу:
3m-3n = 3n(3(m-n)-1) = 1000k+r-1000q-r = 1000(k-q),
иначе говоря — произведение 3n и (3(m-n) — 1)
кратно 1000. Мы знаем, что ни при каких значениях степени n число 3n не может быть кратным
- Следовательно, кратным 1000 должно быть число (3(m-n) — 1): 3(m-n) — 1 = 1000(k-q) или 3(m-n) = 1000(k-q) +1
Мы доказали, что существует степень тройки, которая оканчивается цифрами 001
