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

Мотивація вивчення нових знань.

«...Помиляються ті, хто запевняє, ніби матема­тичні науки нічого не кажуть про прекрасне або добре.

...найголовніші форми прекрасного — порядок (у просторі), співрозмірність і визначеність — мате­матичні науки якраз і найвиразніше показують  їх.»

                                           Арістотель

Осмислення нових знань.

Дуже часто буває так, що при розв'язуванні складних математичних задач використовують різний інструментарій, уже відомі методи, прийоми, принципи, теорії тощо. Завдяки цьому, деякі класи задач стають алгоритмічними, і їхні розв'язки — доступними широкому загалу.
На цьому занятті  ми познайомимося з принципом, що формулюється надзвичайно просто і доступно навіть для наймолодших школярів, з його допомогою ми навчимося розв'язувати досить складні задачі. Жартома
цей принцип формулюється так: "Якщо п'ятьох зайців розсадити в чо­тири клітки, то принаймні в одній із них опиниться два зайці".

В україномовній математичній літературі цей принцип називають принципом Діріхле на честь відомого німецького математика Петера Лежена Дірі­хле, який перший із допомогою такого простого твердження отримав глибокі результати про наближення ірраціональних чисел раціональни­ми (в англомовній літературі цей принцип більше відомий як ріgеоn ргіnсіріе — "принцип голубів")/ Зауважимо, що задачі цієї розділу не претендують на оригінальність, більшість із них уже стала математич­ним "фольклором", і вже зараз складно встановити їх авторів.

Розгляньмо кілька елементарних задач.

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

Розв'язання. Зрозуміло, що узявши три кульки, ми виявимо, що дві з них одного кольору. У даному випадку роль зайців відіграють кульки, а роль кліток — чорний та білий кольори.

2. У лісі росте мільйон ялинок. Відомо, що на кожній із них не більше ніж 800 000 голок. Доведіть, що в лісі знайдуться дві ялинки з однаковою кількістю голок.

Доведення. Припустімо, що в лісі всі ялинки мають різну кількість голок (на деякій ялинці голок могло не бути зовсім). Тоді в лісі не більше ніж 800 001 ялинка, що суперечить умові. Тут у ролі зай­ців були ялинки, а в ролі кліток — усі можливі варіанти кількості голок на них.

3. На 5 поличках книжкової шафи 160 книг, причому на одній із них — 3 книги. Доведіть, що знайдеться поличка, на якій не менше ніж 40 книг.

Доведення. Припустімо, що на кожній із решти 4 поличок не більше ніж 39 книг. Тоді на всіх 5 поличках не більше ніж З + 4 • 39 = 159 книг, що суперечить умові. Отже, на одній із поличок не менше ніж 40 книг.

Проте найчастіше принцип Діріхле використовують в узагальненому формулюванні.

Узагальнений принцип Діріхле.

Якщо nк +1 предмет розкладено в n ящиків, то принаймні в од­ному з ящиків знаходиться не менше  ніж к + 1 предмет.

Доведення. Нехай х_і, (і = 1,...,n) — кількість предметів, що знаходяться в i-ому ящику.

За умовою х₁+х₂+... + х_n = nк + 1. Припустімо, що для кожного i виконується х_i  к. Тоді

х₁+х₂+... + х_n <nк, що суперечить умові. Отже, наше припущення було хибним, тобто в одному з ящиків є принаймні к +1 предмет.

Цей спосіб доведення надалі спрощено також називатимемо принципом Діріхле.

4. У місті більше ніж 8 мільйонів жителів. Науковці вважають, що в кож­ної людини менш ніж

200 000 волосин на голові. Доведіть, що є принаймні 41 житель з однаковою кількістю волосин
на голові.

Доведення. Оскільки 40-200000 = 8000000 (кількість волосин у людини коливається від  0  до   199 999,  всього  200 000  ва­ріантів), то,   згідно з принципом Діріхле знайдеться принаймні 41 житель, що має однакову кількість волосин на голові. Тут роль предметів відіграють жителі, а роль ящиків — усі мо­жливі варіанти кількості волосин на голові.

5. Дано два многочлени від однієї змінної, кожен із яких — сума 9 членів парного степеня, не більшого за 36. Доведіть, що в добутку обов'язково знайдуться три подібних члени.

Доведення. Якщо ми перемножимо два даних многочлени, то отримаємо новий многочлен степеня, не більшого за 72, кожний із 81 одночлена якого має парний степінь. Оскільки парних чисел від 0 по 72 є 37, то, згідно з принципом Діріхле, знайдуться принаймні три подіб­них члени.

6. Доведіть, що серед 82 кубиків, кожен із яких помальовано певним кольором, існує 10 кубиків різного кольору або 10 кубиків одного кольору.

Доведення. Якщо для розмалювання 82 кубиків використано не менше ніж 10 кольорів, то зрозуміло, що знайдеться 10 кубиків різного кольору. Якщо ж для розмалювання 82 кубиків використано не більше ніж 9 різних кольорів, то, згідно з принципом Діріхле, знайдеться при­наймні 10 кубиків одного кольору. Тут у ролі предметів виступають кубики, а в ролі ящиків — кольори.

7. Цифри 1, 2, ..., 9 розбили на три групи. Довести, що добуток цифр  в одній із груп не менший за 72.

Доведення. Оскільки

9! = 1 • 2·... • 9 = (8 • 9) • (З • 4 • 6) • (7 • 5 • 2) = 70 •72² = = (71²-1)(71 + 1)=71³ +71²-71-1>71³, то, згідно з принципом Діріхле, добуток цифр в одній із груп не мен­ший за 72.

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

Доведення. Припустімо, що твердження задачі неправильне. Тоді 15 хлопчиків зібрали щонайменше 0 + 1 + 2 + .. . + 14 = 14•15:2 = 105 грибів. Це суперечить умові.