Принцип Діріхле
Не знаючи формулювання принципа Діріхлє, ми користуємося ним навіть у повсякденному житті, настільки він простий і очевидний. Зрозуміло, що для розв'язування задач необхідно ознайомитися з ним, щоб легше було здогадатись, в яких випадках можна застосовувати. Принцип Діріхле можна сформулювати в такій жартівливій формі: “Якщо п’ятьох зайців розсадити в чотири клітки, то принаймні в одній із них опиниться два зайці”.
В математичній літературі цей принцип називають принципом Діріхле на честь відомого німецького математика Петера Лежена Діріхле, який перший із допомогою такого простого твердження отримав глибокі результати про наближення ірраціональних чисел раціональними (в англомовній літературі цей принцип більше відомий як ріgеоn ргіnсіріе — “принцип голубів”).
Задачі з розв'язанням
1. У школі навчаються 400 учнів. Довести, що хоча б двоє з них народилися в один день року.
РОЗВ’ЯЗАННЯ. Найбільше в році буває 366 днів. Якщо дні вважати клітками, як у формулюванні принципу Діріхле, а учнів ― кроликами, то в деякій клітці сидять не менше як два кролики, тобто більше від одного кролика. Отже, не менше двох учнів народилися в один день року. Можна також міркувати від супротивного. Припустимо, що кожний день відзначають день народження не більше, ніж один учень, тоді всього учнів не більше від 366 ― виникла суперечність.
2. У класі навчається 29 учнів. Петрик зробив у диктанті 13 помилок, і ніхто інший не зробив більшої кількості помилок. Довести, що принаймні три учні зробили однакову кількість помилок.
РОЗВ’ЯЗАННЯ. Приймемо за «клітки» всі можливі варіанти кількості помилок. Їх є 14, оскільки учні можуть зробити 0, 1, ..., 13 помилок. «Зайцями» вважатимемо учнів, які писали диктант і яких за умовою є 29. Кожного з них «садимо» у «клітку», що відповідає кількості зроблених помилок. Зрозуміло, що знайдеться «клітка», в якій «сидять» принаймні три «зайці», а це й означає, що знайдуться три учні, які зробили однакову кількість помилок.
3. У ящику лежать 10 пар чорних рукавичок і 10 пар червоних одного розміру. Скільки рукавичок потрібно витягнути з ящика навмання, щоб серед них були:
а) хоча б дві рукавички одного кольору;
б) хоча б одна пара рукавичок одного кольору?
РОЗВ’ЯЗАННЯ. а) Якщо за «клітки» прийняти кольори рукавичок, то взявши три довільні рукавички, ми отримаємо, що в одній із «кліток» знаходяться два «зайці» ― рукавички. А це і вимагається в задачі. Отже, щоб були дві рукавички одного кольору, потрібно витягнути щонайменше 3 рукавички.
б) Якщо взяти 20 рукавичок на одну руку, то з них не можна буде вибрати пару рукавичок одного кольору, тому шукана кількість рукавичок не менша, ніж 21.
Справді, якщо за «клітки» прийняти кольори рукавичок (їх два), а за «зайців» — рукавички, то за узагальненим принципом Діріхле в одній з «кліток» буде не менше 11 «зайців». Це означає, що знайдеться 11 рукавичок одного кольору. Але ми маємо лише 10 пар рукавичок одного кольору. Тому всі вони не можуть бути на одну руку. Отже, серед цих 11 рукавичок знайдеться одна пара рукавичок одного кольору.
4. 100 человек сидят за круглым столом, причем более половины из них — мужчины. Докажите, что какие-то двое мужчин сидят друг напротив друга.
РЕШЕНИЕ. Разобьем всех на 50 пар людей, сидящих друг напротив друга. Тогда получаем, что у нас есть 50 пар («клетки»), в которые нужно рассадить не менее 51 мужчины («кролики»). Из принципа Дирихле следует, что в одной из этих пар-«клеток» оба человека — мужчины-«кролики».
Ще кілька задач
1. Докажите, что среди любых шести целых чисел найдутся два, разность которых кратна 5.
2. В лесі ростуть мільон ялинок. Відомо, що на кожній з них не більше 600 000 голок. Довести, що в лісі знайдуться принаймні дві ялинки з однаковою кількістю голок.
Перейдемо тепер до узагальненого принципу Діріхле. Мовою кроликів та кліток його можна сформулювати таким чином: "Якщо в 10 клітках сидить 51 кролик, то принаймні в одній з кліток сидить не менше 6 кроликів". Математичню мовою можна записати таким чином: якщо nk+1 елемент розділений на n множин, то принаймні в одній множині виявиться не менше k+1 елементів.
3. В магазин привезли 25 ящиков с яблоками трех сортов, причем в каждом ящике лежали яблоки какого-то одного сорта. Можно ли найти 9 ящиков с яблоками одного сорта?
4. На площадке 20 собак восьми разных пород. Докажите, что среди них есть не менее трех собак одной породы.
5. В классе 27 учеников. Найдется ли месяц, в котором отмечают свои дни рождения не меньше, чем три ученика этого класса?