Принцип Діріхле найпростіше зрозуміти, використавши таку його жартівливу форму: "Якщо в N клітках сидять не менше N+1 кроликів, то у якійсь із кліток сидить не менше двох кроликів". Звернемо увагу на невизначеність висновків – "у якійсь із кліток", "не менше". Ця невизначеність часто призводить до цікавих висновків на основі, здавалось би, недостатніх даних. Часто при розв’язуванні задач на принцип Діріхле точне доведення міркувань можна дати за допомогою доведення від супротивного.

Приклад 1.

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

Розв’язання.

Зрозуміло, що двох кульок може не вистачити: може виявитись, що вони різних кольорів. Тому слід взяти не менше 3 кульок. Доведемо, що 3 кульок досить. Припустимо протилежне – 3 кульок не досить (тобто серед трьох кульок може і не знайтись двох кульок одного кольору). Якщо всі три кульки різного кольору, то вони пофарбовані у три кольори. Але за умовою задачі у мішку є кульки тільки двох кольорів. Ця суперечність означає, що наше припущення неправильне. А отже, серед трьох кульок завжди знайдуться  дві кульки одного кольору. Зрозуміло, що кроликами в цій задачі є кульки, а клітками – кольори: чорний і білий.

Приклад 2.

Довести, що серед n+1 цілого числа можна вибрати два, різниця яких ділиться на n.

Розв’язання.

При діленні на n будь-яке ціле число дає в остачі одне з чисел 0, 1, 2, … , n-1, тобто всього існує n різних остач. Тому серед n+1 чисел знайдуться 2 такі, що дають однакові остачі при діленні на n. Різниця цих чисел і ділитиметься на n.

Узагальнений принцип Діріхле: "Якщо в N клітках сидять не менше kN+1 кроликів, то у якійсь із кліток сидить не менше k+1 кроликів".

Приклад 3.

У магазин привезли 25 ящиків із яблуками трьох сортів, причому в кожному ящику лежать яблука якогось одного сорту. Чи можна знайти 9 ящиків із яблуками одного сорту?

Розв’язання.

Припустимо, що 9 ящиків яблук одного сорту немає. Тоді ящиків кожного сорту не більше 8. Оскільки сортів 3, знаходимо, що тоді всього ящиків не більше 24, а їх 25. Протиріччя. Отже, завжди можна знайти 9 ящиків з яблуками одного сорту.

Зрозуміло, що кроликами в даному випадку будуть ящики, а клітками – сорти яблук. Тоді N=3, а kN+1=25. Отже k=8. Тому, за принципом Діріхле, знайдеться сорт яблук (клітка), якій відповідає не менше k+1=9 ящиків (кроликів).

Задачі.

1. 100 зайців розсадили в 99 кліток. Доведіть, що знайдеться клітка, в якій сидять не менше 2 зайців.

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

3. В темній шафі зберігаються шкарпетки 7 різних кольорів. Яку найменшу кількість шкарпеток слід взяти наосліп, щоб із них можна було утворити пару?

4. На планеті Айсберг живуть п’ятирукі інопланетяни. На базі Айсберг-17 зберігаються рукавички 8 видів. Одного дня на базі вимкнулась електроенергія. Яку найменшу кількість рукавичок має взяти кожен інопланетянин наосліп, щоб після виходу на світло він міг гарантовано одягти на кожну із своїх рук однакові рукавички?

5. У класі 41 учень. В диктанті Григорій зробив 13 помилок, а решта менше. Довести, що принаймні 4 учні зробили однакову кількість помилок.

6. Хлопчик протягом трьох днів купив 100 марок. Довести, що в один із цих днів він купив не менше 34 марок.

Часто при розв’язування задач зручно користуватися такою теоремою:

"Якщо в N клітках сидить менше N*(N-1)/2 кроликів, то знайдуться принаймні 2 клітки, у яких сидить однакова кількість кроликів (можливо жодного)".

Приклад 4.

У місті 14 шкіл. Для міста виділили 90 комп’ютерів. Довести, що як би не розподіляли комп’ютери між школами, знайдуться 2 школи, які отримали однакову кількість комп’ютерів (можливо жодного).

Розв’язання.

Припустимо, що усі школи отримали різну кількість комп’ютерів. Порахуємо найменшу кількість комп’ютерів, потрібних для цього. Нехай одна зі шкіл отримала 0 комп’ютерів, друга – 1, третя – 2, і т.д., чотирнадцята – 13 комп’ютерів. Тоді всього комп’ютерів потрібно 0+1+2+3+…+13=91. А їх всього 90. Протиріччя. Отже, знайдеться принаймні 2 школи, які отримали однакову кількість комп’ютерів. В цій задачі кроликами будуть комп’ютери, а клітками – школи. N=14. Тоді N*(N-1)/2=14*(14-1)/2=91. Отже, щоб всі школи отримали різну кількість комп’ютерів, потрібен 91 комп’ютер.

7. 15 хлопчиків зібрали 100 горіхів. Довести, що як би вони їх не ділили, знайдуться 2 хлопчики, які отримають порівну горіхів.

8. До свята 10 хлопчиків надули 44 кульки, серед них 11 червоних, а решта – інших кольорів. Довести, що 1) знайдеться хлопчик, який надув принаймні 2 червоні кульки, 2) знайдеться хлопчик, який надув принаймні 5 кульок, 3) знайдуться два хлопчики, які надули однакову кількість кульок (можливо, жодної).

9. Чи можна розкласти 44 кубики на 9 купок так, щоб кількість кубиків в усіх купках була різною?

10. Кілька футбольних команд проводять турнір в одне коло. Доведіть, що в будь-який момент турніру знайдуться дві команди, що зіграли однакову кількість разів.

Приклад 5.

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

Розв’язання.

Ця задача зводиться до принципу Діріхле простим твердженням: різниця двох чисел ділиться на 5, якщо вони мають однакові остачі при ділення на 5. Отже, нам досить довести, що серед шести чисел завжди знайдуться два, які мають однакові остачі при ділення на 5. Оскільки можливих остач всього 5: 0, 1, 2, 3, 4, а чисел 6, то за принципом Діріхле знайдуться два, які мають однакові остачі при ділення на 5. У цій задачі кроликами будуть числа, а клітками – остачі від ділення на 5.

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

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

13. Чи можна знайти такі два різні степені числа 4, у яких 1) остання цифра однакова, 2) дві останні цифри однакові, 3) три останні цифри однакові?

14. У клітинках таблиці 3×3 розставили числа -1; 0; 1. Після цього обчислили суми чисел в кожній стрічці, в кожному стовпчику і в кожній діагоналі. Доведіть, що серед обчислених сум знайдуться дві однакові.

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

16. Площина довільним чином розфарбована у два кольори. Довести, що знайдуться дві точки одного кольору на відстані 1 м одна від одної.

Заняття підготував вчитель математики Крутівської ЗОШ Монько І.О.