Задачі НА ПРИНЦИП ДІРІХЛЕ

ПРИНЦИП ДІРІХЛЕ

Цей принцип формулюється так: "Якщо п'ятьох зайців розсадити в чо­тири клітки, то принаймні в одній із них опиниться два зайці".

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

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

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

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

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

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

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

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

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 грибів. Це суперечить умові.

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

2°. Учені дослідили, що кількість голок у їжака не перевищує 200 тисяч. Доведіть, що із 250 тисяч їжаків можна вибрати принаймні двох, що мають однакову кількість голок.

3°. У Верховну Раду обрано 336 народних депутатів, причому серед них 123 жінки, 245 — особи — представники правих сил. Дове­діть, що серед правих є не менше ніж 32 жінки.

4°. У школі 30 класів і 1000 учнів. Доведіть, що у школі є клас, у якому не менше ніж 34 учнів.

5°. На Землі більше ніж 4 мільярди людей, вік яких не переви­щує 100 років. Доведіть, що на Землі є двоє людей, що народилися тієї самої секунди.

6°. Яку найменшу кількість карток спортлото "6 із 49" потрібно купити, щоб на одній із них обов'язково було вгадано хоча б один но­мер?

7°. У магазин завезли 25 ящиків із трьома різними сортами яблук (у кожному ящику яблука лише одного сорту). Доведіть, що серед них є принаймні 9 ящиків одного сорту яблук.

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

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

10°. З повного набору доміно викинули всі кісточки з шістками. Чи можна викласти в ланцюг усі кісточки, що залишилися?