Задачі на принцип Діріхле

Задачі на принцип Діріхле

Найпоширеніше наступне формулювання цього принципу:

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

Приклад 1. 

У школі навчаються 400 учнів. Довести, що хоча б двоє з них народилися в один день року.

Розв’язання. Найбільше в році буває 366 днів. Якщо дні вважати клітками, як у формулюванні принципу Діріхле, а учнів ― кроликами, то в деякій клітці сидять не менше як 2 кроликів, тобто більше від одного кролика. Отже, не менше двох учнів народилися в один день року. ■

Можна міркувати від супротивного. Припустимо, що кожний день відзначають день народження не більше, ніж один учень, тоді всього учнів не більше від 366 ― суперечність.

Приклад 2. 

У школі навчається 962 учні. Довести, що принаймні у двох учнів збігаються ініціали.

Розв’язання. За умовою 962 учнів. В алфавіті 31 буква. Із 31 букви можна утворити 31*31=961 пару ініціалів (АА, АБ,БА,ББ...). Якщо учнів вважати клітками, як у формулюванні принципу Діріхле, а ініціали― кроликами, то в деякій клітці сидять не менше як 2 кроликів, тобто більше від одного кролика. Отже, не менше двох учнів мають однакові ініціали. ■ 

Приклад 3. 

На співбесіду прийшли 65 школярів. Їм запропонували 3 тестові завдання. За кожне завдання ставилася одна з оцінок: 2, 3, 4 або 5. Чи вірно, що знайдуться два школярі, що одержали однакові оцінки з усіх тестових завдань?

Розв’язання. Розглянемо всі набори з трьох оцінок за відповідні завдання. Кількість таких наборів дорівнює 4³ або 64 (4 можливості за кожне з трьох тестових завдань). Оскільки число учнів 65 більше, ніж 64, то за принципом Діріхле деяким двом учням відповідає один набір оцінок. ■

Приклад 4.

 У місті 2 500 000 жителів. Науковці вважають, що в кожної людини менше, ніж 200 000 волосин на голові. Довести, що є тринадцять жителів з однаковою кількістю волосин.

Розв’язання. Розглянемо всі групи волосатих людей. 1 група - має 0 волосин, 2 група - 1 волосину, 3 група - 2 волосини і т.д. 200 000 група - 199 999 волосин. Тобто всього 200 000 груп, а жителів 2 500 000.

 Маємо 2 500 000=200 000*12+100 000. Отже 1 із 100 000 попаде в одну із цих груп Тобто,  є тринадцять жителів з однаковою кількістю волосин■

Приклад 5.

 Кіт Базіліо пообіцяв Буратіно відкрити велику таємницю, якщо той складе чарівний квадрат 6 × 6 із чисел +1, −1, 0 так, щоб всі суми по рядкам, по стовпцям і по великим діагоналям були різні. Чи може Буратіно скласти такий квадрат?

Розв’язання. Вказані суми чисел можуть змінюватися в межах від −6 до +6. Всього ― 13 значень. Рядків у квадраті є 6, стовпців ― 6, діагоналей ― 2. Маємо 6+6+2=14 різних сум. За принципом Діріхле хоча б дві з цих сум мають дорівнювати одна одній. Отже, скласти такий квадрат неможливо. ■

Приклад 6.

 На співбесіду прийшли 65 школярів. Їм запропонували 3 тестові завдання. За кожне завдання ставилася одна з оцінок: 2, 3, 4 або 5. Чи вірно, що знайдуться два школярі, що одержали однакові оцінки з усіх тестових завдань?

Розв’язання. Розглянемо всі набори з трьох оцінок за відповідні завдання. Кількість таких наборів дорівнює 4³ або 64 (4 можливості за кожне з трьох тестових завдань). Оскільки число учнів більше, ніж 64, то за принципом Діріхле деяким двом учням відповідає один набір оцінок. ■

Приклад 7. 

У класі навчається 29 учнів. Сашко Петренко зробив у диктанті 13 помилок, і ніхто інший не зробив більшої кількості помилок. Довести, що принаймні три учні зробили однакову кількість помилок.

Розв’язання. Усього 29 учнів. Розіб'ємо їх на групи за кількістю допущених помилок: 1 група - 0 помилок, 2 група - 1 помилка і т.д., 14 група - 13 помилок (оскільки це найбільша кількість допущених помилок). Усього 14 груп. Отже, 29=14*2+1. Тобто  принаймні три «зайці» в одній клітці, а це й означає, що знайдуться три учні, які зробили однакову кількість помилок. ■

Приклад 8. 

На Землі океан займає більше половини площі поверхні. Довести, що в світовому океані можна вказати дві діаметрально протилежні точки.

Розв’язання. Відобразимо океан симетрично центру Землі. Оскільки сума площ океану і його образу перевищує площу земної поверхні, то існує точка, що належить океану і його образу. Візьмемо за шукані цю точку разом з протилежною до неї. ■

Приклад 9. 

Довести, що серед довільних семи цілих чисел можна знайти три, сума яких ділиться на 3.

Розв’язання. За «клітки» приймаємо різні остачі від ділення на 3. Їх є усього три: 0, 1, 2. «Зайцями» вважатимемо остачі від ділення на 3 даних семи чисел. Їх є усього 7. Як і в попередній задачі, розмістивши «зайців» у «клітки» і використавши узагальнений принцип Діріхле, робимо висновок, що знайдуться три «зайці», що знаходяться в одній із «кліток». А це й означає, що знайдуться три числа, які дають однакові остачі від ділення на 3. Їх сума ділиться на 3. ■

Приклади для самостійного розв'язання:

Завдання 10. 

У класі навчається 41 учень. Під час диктанту 1 учень допустив  13 помилок, і ніхто інший не зробив більшої кількості помилок. Довести, що принаймні чотири учні зробили однакову кількість помилок.

Завдання 11.

У 500 ящиках лежать яблука. Причому кожен ящик може містити не більше, як 240 яблук. Довести, що є 3 ящики, які містять однакову кількість яблук.

Завдання 12. 

У п’ятих класах школи навчається 160 учнів. Довести, що знайдуться 4 п’ятикласники, у яких день народження припаде на один і той самий тиждень.

Завдання 13. 

У клітинках таблиці розміром 3 × 3 розміщено числа −1; 0; 1. Розглянемо вісім сум: суми всіх чисел у кожному рядку, кожному стовпці і на двох діагоналях таблиці. Чи можуть усі ці суми бути різними?

(Відповідь. Ні)

Завдання 14. 

У ящику лежать 10 пар чорних рукавичок і 10 пар червоних одного розміру. Скільки рукавичок потрібно витягнути з ящика навмання, щоб серед них були:

а) хоча б дві рукавички одного кольору;

б) хоча б одна пара рукавичок одного кольору?

Завдання 15.

 Довести, що серед довільних трьох цілих чисел можна знайти два числа, сума яких ділиться на 2.

Завдання 16.

 Дано 12 цілих чисел. Довести, що з них можна вибрати два числа, різниця яких ділиться на 11.
Завдання 17. 

Кожну грань куба зафарбовано у білий або чорний колір. Довести, що знайдуться однаково зафарбовані грані, що мають спільне ребро.
Завдання 18.

 На шаховій дошці розміром 8 × 8 клітинок розставлено 31 фішку. Довести, що знайдеться вільна від фішок фігура, яка складається з трьох клітинок, зображена на рис. 1.

 Рис. 1

Завдання 19. 

На площині дано шість точок загального положення (жодні три з них не лежать на одній прямій). Кожні дві точки з’єднано відрізком червоного або синього кольору. Довести, що знайдеться трикутник із вершинами в даних точках, усі сторони якого мають один колір.

Завдання 20. 

У квадраті, сторона якого дорівнює 6 см, розміщена 1991 точка. Довести, що квадратом, сторона якого дорівнює 5 см, можна покрити хоча б 664 з цих точок.

 Завдання 21.

 Довести, що в довільному опуклому 2n-кутнику знайдеться діагональ, яка не паралельна жодній зі сторін.

Завдання 22. 

Усередині квадрата зі стороною 10 см «відмічено» 101 точку (жодні три не лежать на одній прямій). Довести, що серед цих точок є три точки, які утворюють трикутник, площа якого не перевищує 1 .
 Завдання 23

 Доведіть, що існує натуральне число, останніми чотирма цифрами якого є 1972 і яке ділиться на 1971. 

Завдання 24. 

Чи можна знайти такий натуральний степінь числа 3, який закінчується на 0001?
Завдання 25.

У квадраті, сторона якого дорівнює 1, взято 51 точку. Доведіть, що деякі три з цих точок обов’язково містяться всередині круга, радіус якого дорівнює 17  .