Приклад 3.1. У школі навчаються 400 учнів. Довести, що хоча б двоє з них народилися в один день року.
Розв’язання. Найбільше в році буває 366 днів. Якщо дні вважати клітками, як у формулюванні принципу Діріхле, а учнів ― кроликами, то в деякій клітці сидять не менше як кроликів, тобто більше від одного кролика. Отже, не менше двох учнів народилися в один день року. ■
Можна міркувати від супротивного. Припустимо, що кожний день відзначають день народження не більше, ніж один учень, тоді всього учнів не біль-ше від 366 ― суперечність.
Приклад 3.2. Кіт Базіліо пообіцяв Буратіно відкрити велику таємницю, якщо той складе чарівний квадрат 6 × 6 із чисел +1, −1, 0 так, щоб всі суми по рядкам, по стовпцям і по великим діагоналям були різні. Чи може Буратіно скласти такий квадрат?
Розв’язання. Вказані суми чисел можуть змінюватися в межах від −6 до +6. Всього ― 13 значень. Рядків у квадраті є 6, стовпців ― 6, діагоналей ― 2. Маємо 14 різних сум. За принципом Діріхле хоча б дві з цих сум мають дорівнювати одна одній. Отже, скласти такий квадрат неможливо. ■
Приклад 3.3. На Землі океан займає більше половини площі поверхні. Довести, що в світовому океані можна вказати дві діаметрально протилежні точки.
Розв’язання. Відобразимо океан симетрично центру Землі. Оскільки сума площ океану і його образу перевищує площу земної поверхні, то існує точка, що належить океану і його образу. Візьмемо за шукані цю точку разом з протилежною до неї. ■
Приклад 3.4. На співбесіду прийшли 65 школярів. Їм запропонували 3 тестові завдання. За кожне завдання ставилася одна з оцінок: 2, 3, 4 або 5. Чи вірно, що знайдуться два школярі, що одержали однакові оцінки з усіх тестових завдань?
Розв’язання. Розглянемо всі набори з трьох оцінок за відповідні завдання. Кількість таких наборів дорівнює 43 або 64 (4 можливості за кожне з трьох тестових завдань). Оскільки число учнів більше, ніж 64, то за принципом Діріхле деяким двом учням відповідає один набір оцінок. ■
Приклад 3.5. У класі навчається 29 учнів. Сашко Петренко зробив у диктанті 13 помилок, і ніхто інший не зробив більшої кількості помилок. Довести, що принаймні три учні зробили однакову кількість помилок.
Розв’язання. Приймемо за «клітки» всі можливі варіанти кількості помилок. Їх є 14, оскільки учні можуть зробити 0, 1, ..., 13 помилок. «Зайцями» вважатимемо учнів, які писали диктант і яких за умовою є 29. Кожного з них «садимо» у «клітку», що відповідає кількості зроблених помилок. Зрозуміло, що знайдеться «клітка», в якій «сидять» принаймні три «зайці», а це й означає, що знайдуться три учні, які зробили однакову кількість помилок. ■
Приклад 3.6. У п’ятих класах школи навчається 160 учнів. Довести, що знайдуться 4 п’ятикласники, у яких день народження припаде на один і той самий тиждень.
Розв’язання. У році може бути максимум 53 тижні. Їх і приймемо за «клітки», а за «зайців» — учнів. Розсаджуватимемо «зайців» у ті «клітки», що відповідають їх дням народження. Оскільки 160 : 53 = , то за принципом Діріхле знайдеться «клітка», у якій є принаймні 4 «зайці». Це означає, що знайдеться тиждень, на який припаде день народження відразу у чотирьох учнів. ■
Приклад 3.7. У клітинках таблиці розміром 3 × 3 розміщено числа −1; 0; 1. Розглянемо вісім сум: суми всіх чисел у кожному рядку, кожному стовпці і на двох діагоналях таблиці. Чи можуть усі ці суми бути різними?
Розв’язання. Нехай «клітками» будуть усі різні значення сум трьох чисел, кожне з яких набуває значення 0, 1 або −1. Зрозуміло, що таких значень є 7. Це −3; −2; −1; 0; 1; 2; 3. «Зайцями» будуть набори із трьох чисел, що розміщені або в одному стовпці, або в одному рядку, або на одній із двох діагоналей таблиці. Таких наборів є 8.
За принципом Діріхле знайдеться «клітка», де сидять не менше двох «зайців». А це й означає, що знайдуться дві розглядувані трійки чисел, для яких суми рівні.
Відповідь. Ні. ■
Приклад 3.8. У ящику лежать 10 пар чорних рукавичок і 10 пар червоних одного розміру. Скільки рукавичок потрібно витягнути з ящика навмання, щоб серед них були:
а) хоча б дві рукавички одного кольору;
б) хоча б одна пара рукавичок одного кольору?
Розв’язання. а) Якщо за «клітки» прийняти кольори рукавичок, то взявши три довільні рукавички, ми отримаємо, що в одній із «кліток» знаходяться два «зайці» ― рукавички. А це і вимагається в задачі. Отже, щоб були дві рукавички одного кольору, потрібно витягнути щонайменше 3 рукавички.
б) Якщо взяти 20 рукавичок на одну руку, то з них не можна буде вибрати пару рукавичок одного кольору, тому шукана кількість рукавичок не менша, ніж 21.
Справді, якщо за «клітки» прийняти кольори рукавичок (їх два), а за «зай-ців» — рукавички, то за узагальненим принципом Діріхле в одній з «кліток» буде не менше 11 «зайців». Це означає, що знайдеться 11 рукавичок одного кольору. Але ми маємо лише 10 пар рукавичок одного кольору. Тому всі вони не можуть бути на одну руку. Отже, серед цих 11 рукавичок знайдеться одна пара рукавичок одного кольору. ■
Розглянемо, як принцип Діріхле використовують для розв’язування задач на подільність. Такі задачі — це класичний приклад застосування принципу Діріхле.
Приклад 3.9. Довести, що серед довільних трьох цілих чисел можна знайти два числа, сума яких ділиться на 2.
Розв’язання. Приймемо за «клітки» різні остачі від ділення чисел на 2. Їх є усього дві: 0 і 1. «Зайцями» будемо вважати остачі від ділення на 2 трьох даних чисел, їх є три. Розмістивши «зайців» у «клітки» (кожного «зайця» розміщаємо у «клітку», що дорівнює остачі від ділення його на 2), за принципом Діріхле отримаємо, що знайдеться «клітка» з двома «зайцями», тобто знайдуться два числа, що дають при діленні на 2 однакові остачі. Їхня сума і ділиться на 2. ■
Приклад 3.10. Довести, що серед довільних семи цілих чисел можна знайти три, сума яких ділиться на 3.
Розв’язання. За «клітки» приймаємо різні остачі від ділення на 3. Їх є усього три: 0, 1, 2. «Зайцями» вважатимемо остачі від ділення на 3 даних семи чисел. Їх є усього 7. Як і в попередній задачі, розмістивши «зайців» у «клітки» і використавши узагальнений принцип Діріхле, робимо висновок, що знайдуться три «зайці», що знаходяться в одній із «кліток». А це й означає, що знайдуться три числа, які дають однакові остачі від ділення на 3. Їх сума ділиться на 3. ■
Приклад 3.11. Дано 12 цілих чисел. Довести, що з них можна вибрати два числа, різниця яких ділиться на 11.
Розв’язання. Приймемо за «клітки» різні остачі від ділення чисел на 11. Їх є усього 11. За «зайців» приймемо остачі від ділення даних чисел на 11. Їх є усього 12. Розміщуючи «зайців» у «клітки» аналогічно до попередніх задач, за принципом Діріхле отримаємо, що знайдуться два «зайці» в одній із «кліток». А це означає, що знайдеться два числа, які дають однакові остачі від ділення на 11. Зрозуміло, що різниця цих чисел буде ділитися на 11. ■
Принцип Діріхле використовують і при розв’язуванні задач на зафар-бовування.
Приклад 3.12. Кожну грань куба зафарбовано у білий або чорний колір. Довести, що знайдуться однаково зафарбовані грані, що мають спільне ребро.
Розв’язання. Розглянемо довільну вершину куба. У ній перетинаються три грані. Приймемо за «клітки» кольори, а за «зайців» — грані, що перетинаються в цій вершині. Їх є усього три. Тому за принципом Діріхле знайдеться «клітка», у якій міститься два «зайці». А це означає, що знайдуться дві грані, які мають спільне ребро (оскільки вони мають спільну точку) і зафарбовані однаково. ■
Приклад 3.13. На шаховій дошці розміром 8 × 8 клітинок розставлено 31 фішку. Довести, що знайдеться вільна від фішок фігура, яка складається з трьох клітинок, зображена на рис. 4.
|
|
|
|
|
|
Рис. 4
Розв’язання. Для того щоб не було вільної від фішок фігури, складеної з трьох клітинок, у будь-якому квадраті розміром 2 × 2 має розміститися не менше двох фішок. Оскільки можна покрити всю дошку 16-ма квадратами розміром 2 × 2, що не перекриваються, то всього фігур має бути не менше від 32, а у нас є 31. Отже, за сформульованим принципом знайдеться квадрат розміром 2 × 2, в якому є лише одна фігура. У ньому і міститься вільна від фішок фігура, що складається з трьох клітинок. ■
Приклад 3.14. На площині дано шість точок загального положення (жодні три з них не лежать на одній прямій). Кожні дві точки з’єднано відрізком чер-воного або синього кольору. Довести, що знайдеться трикутник із вершинами в даних точках, усі сторони якого мають один колір.
Розв’язання. Позначимо дані точки через . Із точки виходять 5 відрізків двох кольорів. За принципом Діріхле, серед цих відрізків є 3 відрізки одного кольору. Нехай це відрізки червоного кольору. Розглянемо відрізки . Можливі випадки:
а) Серед цих відрізків є відрізок червоного кольору, наприклад, відрі-зок . Тоді в трикутнику всі сторони червоні.
б) Серед цих відрізків немає відрізка червоного кольору. Тоді в трикутнику всі сторони сині.
Отже, знайдеться трикутник, усі сторони якого мають один колір. ■
Приклад 3.15. У квадраті, сторона якого дорівнює 6 см, розміщена 1991 точка. Довести, що квадратом, сторона якого дорівнює 5 см, можна покрити хоча б 664 з цих точок.
Розв’язання. Неважко помітити, що 664 складає приблизно третину від 1991, а саме, 1991 = 3 · 663 + 2, тому при будь-якому розбитті множини, що складається з 1991 точки, на три підмножини, хоча б в одну з цих підмножин потрапить 664 чи більше точок. Отже, для розв’язування задачі достатньо показати, що квадрат зі стороною 6 см можна розбити на три частини, кожну з яких можна покрити квадратом зі стороною 5 см. Як видно з рис. 5, квадратABCD покривають три квадрати PCDQ, AKMN, AKM1N1. Принаймні один з цих трьох квадратів покриває хоча б 664 з даних точок. ■
Приклад 3.16. Довести, що в довільному опуклому 2n-кутнику знайдеться діагональ, яка не паралельна жодній зі сторін.
Розв’язання. Припустимо, що в деякому опуклому 2n-кутнику кожна діагональ паралельна деякій стороні. Ідея отримання протиріччя така: вибираємо найбільшу групу взаємно паралельних діагоналей і покажемо, що таку кількість діагоналей не можна розмістити всередині опуклого 2n-кутника. Отже, розіб’ємо всі діагоналі на групи взаємно паралельних діагоналей. Таких груп не більше як 2n (деякі сторони можуть бути паралельні між собою). Кількість усіх діагоналей дорівнює 1,5), тому в деякій групі є не менше як (n − 1) діагоналей. Ці (n − 1) діагоналі паралельні деякій стороні і лежать відносно неї в одній півплощині. Але тоді на цю сторону та на ці (n − 1) діагоналей припадає 2n вершин, тобто та з діагоналей, яка лежить далі від сторони , має бути стороною 2n-кутника. Отримали протиріччя.
Отже, припущення неправильне, тому знайдеться діагональ, яка не паралельна жодній зі сторін. ■
Приклад 3.17. Усередині квадрата зі стороною 10 см «відмічено» 101 точку (жодні три не лежать на одній прямій). Довести, що серед цих точок є три точки, які утворюють трикутник, площа якого не перевищує 1 .
Розв’язання. Розіб’ємо квадрат на 50 прямокутників зі сторонами 1 см та 2 см. Тоді хоча б в один з цих прямокутників попаде не менш як 3 точки. Ці три точки утворюють трикутник, площа якого не перевищує 1 см2 (половини площі прямокутника, в якому міститься цей трикутник). ■
Задача 3.18. Довести, що для будь-якого натурального числа m знайдуться такі числа a та b, що та
Розв’язання. Розглянемо множину чисел
.
Усі числа множини S різні (припустивши супротивне, отримуємо, що є часткою цілих чисел), їхня кількість дорівнює . Всі вони належать сегменту і розбивають цей сегмент на частин. Довжина найменшої з цих частин менша від
Нехай цей найменший проміжок утворений числами та , причому . Тоді
і числа задовольняють умову задачі. ■
У деяких випадках допомагають міркування, аналогічні до обгрунтування принципу Діріхле.
Приклад 3.19. Обмежена фігура на площині має площу S > 1. Довести, що її можна «пересунути» на вектор з цілими координатами так, щоб початкова фігура та її образ перетинались.
Розв’язання. Нехай дана фігура F міститься у квадраті зі стороною d. Виберемо систему координат так, щоб точка O(0, 0) була внутрішньою точкою даної фігури. При довільному розглянемо всі можливі образи фігури F при паралельних перенесеннях на вектор , де
. Очевидно, що кожен з таких образів міститься всередині квадрата
.
Припустимо, що жодні два таких образи не перетинаються. Тоді їхня загальна площа не перевищує площі квадрата A, тобто , або .
Але внаслідок умови S – 1 > 0 та властивостей квадратичної функції це неможливо при достатньо великих k. Отже, деякі два образи та фігури F (при паралельних перенесеннях відповідно на вектори та ) перетинаються. Очевидно, що паралельне перенесення на вектор відображає фігуру у фігуру . ■
Приклад 3.20. Для кожного натурального числа через позначимо таке найменше натуральне число, що з довільних різних натуральних чисел, кожне з яких не перевищує n, можна вибрати чотири числа, одне з яких дорівнює сумі трьох інших. Довести, що . Тут ― найбільше ціле число, яке не перевищує x.
Розв’язання. Нехай ― натуральні числа. Тоді
Позначимо: , де i = 3, 4, …, k. Маємо , тому , або .
Усі числа (всього їх є 2k − 5) належать відрізку , довжина якого
Тому цей відрізок містить не більше ніж (2n – k) цілих чисел.
Нехай k = k(n) = . Тоді , звідки отримуємо: 2n – k < 2k − 5. У цьому випадку серед точок на відрізку є хоча б дві однакові, тобто існують такі , що , або .
Нехай . У цьому випадку достатньо навести приклад множини, що складається з чисел і не має вказаної четвірки чисел.
Розглянемо множину k чисел n – k + 1, n – k + 2, …, n . Тоді навіть сума трьох найменших з них:
n – k + 1 + n – k + 2 + n – k + 3 = 3n – 3k +6 > n,
оскільки , або . Отже, з такого набору не можна вибрати чотири числа, одне з яких дорівнює сумі трьох інших. ■