Некоторые математические принципы формулируются настолько просто, что невольно думаешь: серьёзно? Эта банальщина имеет собственное название? А потом ты начинаешь решать задачи и зачарованно наблюдаешь, как вовремя сформулированная банальщина элегантно расправляется с отнюдь не очевидными вопросами. Сегодня говорим об одном из таких утверждений: о принципе Дирихле.
Кролики - это не только ценный мех...
В самом-самом классическом варианте образца 1834 года принцип Дирихле формулируется так:
Если в N+1 кролик рассажены по N клеткам, то хотя бы в одной клетке сидят хотя бы два кролика.
Ну как? Побежали мурашки от математической мощи этого факта? А очень зря.
Проблемы для многих начинаются с того, что этот принцип нужно доказать. И нет, просто пожать плечами и сказать: "А по-другому не получается!" явно недостаточно.
Как доказать очевидную вещь?
Для начала поясним: в математике доказывается всё, кроме аксиом. Более того, просто объявить какое-то утверждение очередной аксиомой нельзя: надо сначала проверить, а не выводится ли оно из уже имеющихся аксиом и их следствий. Очевидные вещи при этом часто доказывают от противного. Давайте посмотрим, как это работает.
Предположим, что принцип Дирихле неверен. Тогда в каждой из N клеток сидит максимум 1 кролик. Значит, общее число кроликов не превосходит N, что противоречит данным условиям (кроликов у нас N+1). Значит, наше предположение неверно, а принцип Дирихле является истинным.
Непривычный читатель на этом моменте пожимает плечами и говорит: "Ну и чем это отличается от того, чтобы просто сказать, что по-другому не получается?" Поясним. Фраза "не получается" означает, что некто попробовал составить контрпример и не смог. С математической точки зрения из этого факта не следует вообще ничего. Личный опыт и интуиция для математики не имеют никакого значения. Из этого вывод: если Вам кажется, что что-то сделать невозможно, постарайтесь найти конкретные противоречия этой гипотетической конструкции с уже известными фактами. Иначе ни один математик Вас всерьёз не воспримет.
Ищем кроликов в детях и королях
Теперь давайте рассмотрим несколько задач, которые решаются с помощью принципа Дирихле. В каждой такой задаче будем указывать, что здесь разумно взять за кроликов, а что - за клетки.
Доказать, что в семье с тремя детьми хотя бы два ребёнка одного пола.
Ну, здесь совсем просто. Кролики - это дети, а клетки - возможные варианты биологического пола (Давно уже хочу составить список задач про соотношения полов и гендеров... Но это потом как-нибудь). Кроликов у нас по условию 3, а клеток - 2. По принципу Дирихле получаем, что хотя бы одна клетка содержит хотя бы двух кроликов. Переводим на язык нашей задачи: хотя бы два ребёнка обладают одним полом.
Можно ли расставить 20 шахматных королей на доске так, чтобы никакие два из них не били друг друга?
Здесь уже посложнее. Кроликами будут шахматные короли, это понятно. А клетками?
В качестве клеток возьмём маленькие квадратики 2 на 2. В каждом таком квадратике может стоять только один король. (В комментариях можете доказать это утверждение. Да, оно очевидно. Я верю, Вы справитесь!) Таких квадратиков на шахматной доске умещается 16 штук.
Итак, у нас 20 кроликов и 16 клеток, что, вообще говоря, не подходит под нашу формулировку принципа Дирихле (в нём указано, что кроликов должно быть на 1 больше, чем клеток). Выход из этого следующий: выберем из наших 20 королей любые 17. Если мы не сможем расставить даже 17 королей, то 20 - тем более. А мы не сможем, потому что по принципу Дирихле хотя бы два короля окажутся в одном квадрате 2 на 2, где будут бить друг друга. Так что ответ на задачу: нет, нельзя.
Доказать, среди любых 55 различных двузначных чисел есть два, сумма которых равна 100.
Заметим, что в любом таком наборе чисел максимум 9 чисел, больших 90 и максимум одно число 50. Таким образом, как минимум 45 чисел - это числа от 10 до 90, не равные 50. Вот они-то и будут кроликами.
Заметим, что такие числа однозначно разбиваются на пары с суммой 100: 10 и 90, 11 и 89 и т. д. Таких пар 40, и они будут нашими клетками.
По принципу Дирихле, хотя бы два числа составят пару с суммой 100.
Чему нас учат кролики?
Принцип Дирихле почти незаменим для тех, кто хочет научиться доказывать и использовать теоремы. Поэтому, если хотите разобраться в математике лучше, изучайте кроликов в клетках! Они миленькие и полезные. Начать можно вот с таких задач:
1. В школе учатся 400 учеников. Доказать, что хотя бы у двоих из них дни рождения совпадают.
2. Все игроки футбольной команды загадали по одному целому числу. Докажите, что из них можно выбрать два, разность которых будет делиться на 10.
3. В квадрате 2 на 2 метра случайным образом поставили пять точек. Докажите, что хотя бы две из них находятся друг от друга на расстоянии не большем, чем корень из двух.
PS
Само собой, сложные вещи из "настоящей математики" тоже используют принцип Дирихле. Например, Китайская теорема об остатках или теорема Дирихле о диофантовых приближениях.
PPS
Мы использовали отнюдь не единственную имеющуюся формулировку принципа Дирихле; их очень много и они обладают крайне разной степенью понятности. Моя любимая такая:
Пусть функция f переводит конечное множество A в конечное множество B, причём мощность A более чем в n раз превосходит мощность множества B. Тогда некоторое своё значение функция f примет хотя бы n+1 раз.
Ну вот, теперь Вы прочитали что-то действительно умное.
