ЗАДАЧА 1
В класі навчається 30 учнів. В диктанті 1 учень зробив 13 помилок, а інші — менше. Довести, що є принаймні 3 учні, що зробили однакову кількість помилок.
Доведення
1 учень відділений в умові, тоді учнів 30—1 = 29. Помилок може бути від 0 до 12, тобто їх кількість — 13. Припустимо, що не більше 2-х учнів зробили однакову кількість помилок, тоді всього в класі (13*2=26) — не більше 26 учнів, а це суперечить умові, адже їх 29. Отже, наше припущення хибне, і в класі є хоча б 3 учні, що зробили однакову кількість помилок.
ЗАДАЧА 2
У лісі росте мільйон ялинок. Відомо, що на кожній із них не більше, ніж 800 000 голок. Доведіть, що в лісі знайдуться дві ялинки з однаковою кількістю голок.
Доведення1
Припустімо, що в лісі всі ялинки мають різну кількість голок (на деякій ялинці голок могло не бути зовсім). Тоді в лісі не більше, ніж 800 001 ялинка, що суперечить умові. Тут у ролі зайців були ялинки, а в ролі кліток — усі можливі варіанти кількості голок на них.
Доведення2
Припустимо супротивне: нехай у цьому лісі не існує дві ялинки з однаковим числом голок. Тоді існує не більше однієї ялинки (одна, чи жодної), що має одну голку.
Аналогічно: існує не більше однієї ялинки (одна, чи жодної) з двома голками…, існує не більше однієї ялинки (одна, чи жодної) з 499999 голками, не більше однієї ялинки (одна, чи жодної) з 500000 голками.
Таким чином не більше, ніж 500000 ялинок мають кількість голок від 1 до 500000.
Оскільки у лісі ростуть 800000 ялинок і кожна має не більше, ніж 500000 голок, то з цього випливає, що знайдеться хоча б дві ялинки з однаковим числом голок.
ЗАДАЧА 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
Доведіть, що серед 82 кубиків, кожен із яких помальовано певним кольором, існує 10 кубиків різного кольору або 10 кубиків одного кольору.
Доведення
Якщо для розмалювання 82 кубиків використано не менше, ніж 10 кольорів, то зрозуміло, що знайдеться 10 кубиків різного кольору. Якщо ж для розмалювання 82 кубиків використано не більше, ніж 9 різних кольорів, то, згідно з принципом Діріхле, знайдеться принаймні 10 кубиків одного кольору. Тут у ролі предметів виступають кубики, а в ролі ящиків — кольори.
ЗАДАЧА 6
Цифри 1, 2, …, 9 розбили на три групи. Довести, що добуток цифр в одній із груп не менший за 72.
Доведення
Оскільки 9! = 1 • 2•… • 9 = (8 • 9) • (З • 4 • 6) • (7 • 5 • 2) = 70 •722 =
(712-1)(71 + 1)=713 +712-71-1>713, то, згідно з принципом Діріхле, добуток цифр в одній із груп не менший за 72.
ЗАДАЧА 7
15 хлопчиків зібрали 100 грибів. Доведіть, що принаймні двоє з них зібрали однакову кількість.
Доведення
Припустімо, що твердження задачі неправильне. Тоді 15 хлопчиків зібрали щонайменше 0 + 1 + 2 + .. . + 14 = 14•15:2 = 105 грибів. Це суперечить умові.
ЗАДАЧА 8
У класі навчається 29 учнів. Сашко Петренко зробив у диктанті 1З помилок, і ніхто інший не зробив більшої кількості помилок. Довести, що принаймні три учні зробили однакову кількість помилок.
Розв’язання
Приймемо за «клітки» всі можливі варіанти кількості помилок. їх 14, оскільки учні можуть зробити 0, 1, …, 13 помилок. «Зайцями» вважатимемо учнів, які писали диктант і яких за умовою 29. Кожного з них «садимо» у «клітку», що відповідає кількості зроблених помилок. Зрозуміло, що знайдеться «клітка», в якій «сидять» принаймні три «зайці», а це й означає, що знайдуться три учні, які зробили однакову кількість помилок.
ЗАДАЧА 9
У п’ятих класах школи навчається 160 учнів. Довести, що знайдуться 4 учні, у яких день народження припаде на один і той самий тиждень.
Розв’язання
У році може бути максимум 53 тижні. їх і приймемо за «клітки», а за «зайців» — учнів. Розсаджуватимемо «зайців» у ті «клітки», що відповідають їх дням народження. Оскільки 160 : 53 = , то за принципом Діріхле знайдеться «клітка», у якій принаймні 4 «зайці». Це означає, що знайдеться тиждень, на який припаде день народження відразу у чотирьох учнів.
ЗАДАЧА 10
У клітинках таблиці розмірами 3×3 розмішено числа -1; 0; 1. Розглянемо вісім сум: суми всіх чисел у кожному рядку, кожному стовпці і на двох діагоналях таблиці. Чи можуть усі ці суми бути різними?
Розв’язання
Нехай «клітками» будуть усі різні значення сум трьох чисел, кожне з яких набуває значення 0, 1 або -1. Зрозуміло, що таких значень 7. Це -3; -2; – 1; 0; 1; 2; З
«Зайцями» будуть набори із трьох чисел, що розмішені або в одному стовпці, або в одному рядку, або на одній із двох діагоналей таблиці. Таких наборів 8.
Як розсаджуватимемо «зайців»? Кожного «зайця» садитимемо в «клітку», що є значенням суми чисел «зайця». Тоді за принципом Діріхле знайдеться «клітка», де сидять не менше двох «зайців». А це й означає, що знайдуться дві розглядувані трійки чисел, для яких суми рівні.Відповідь Ні.
ЗАДАЧА 11
У ящику лежать 10 пар чорних рукавичок і 10 пар червоних одного розміру. Скільки рукавичок потрібно витягнути з ящика навмання, щоб серед них були:
а) хоча б дві рукавички одного кольору;
б) хоча б одна пара рукавичок одного кольору?
Розв’язання
а) Якщо за «клітки» прийняти кольори рукавичок, то взявши три довільні рукавички, ми отримаємо, що в одній із «кліток» знаходяться два «зайці»-рукавички. А це і вимагається в задачі.
б) Якщо взяти 20 рукавичок на одну руку, то з них не можна буде вибрати пару рукавичок одного кольору, тому шукана кількість рукавичок не менша, ніж 21.
Справді, якщо за «клітки» прийняти кольори рукавичок (їх два), а за «зайців» — рукавички, то за узагальненим принципом Діріхле в одній з «кліток» буде не менше 11 «зайців». Це означає, що знайдеться 11 рукавичок одного кольору. Але ми маємо лише 10 пар рукавичок одного кольору. Тому всі вони не можуть бути на одну руку. Отже, серед цих 11 рукавичок знайдеться одна пара рукавичок одного кольору.
Розглянемо, як принцип Діріхле використовується до розв’язування задач на подільність. Такі задачі — класичний приклад застосування принципу Діріхле.
ЗАДАЧА 12
Довести, що серед довільних трьох цілих чисел можна знайти два, сума яких ділиться на 2.
Розв’язання
Приймемо за «клітки» різні остачі від ділення чисел на 2. Їх усього дві: 0 і 1. «Зайцями» будемо вважати остачі від ділення на 2 трьох даних чисел. їх буде три. Розмістивши «зайців» у «клітки» (кожного «зайця» розміщаємо у «клітку», що дорівнює остачі від ділення його на 2), за принципом Діріхле отримаємо, що знайдеться «клітка» з двома «зайцями», тобто знайдуться два числа, що дають при діленні на 2 однакові остачі. їх сума і ділиться на 2.
ЗАДАЧА 13
Довести, що серед довільних семи чисел можна знайти три, сума яких ділиться на 3.
Розв’язання
За «клітки» приймаємо різні остачі від ділення на 3. Їх усього три: 0, 1, 2. «Зайцями» вважатимемо остачі від ділення на 3 даних семи чисел. Їх усього 7. Як і в попередній задачі, розмістивши «зайців» у «клітки» і використовуючи узагальнений принцип Діріхле, робимо висновок, що знайдуться три «зайці», що знаходяться в одній із «кліток». А це й означає, що знайдуться три числа, які дають одна¬кові остачі від ділення на 3. Їх сума ділиться на 3.
ЗАДАЧА 14
Дано 12 довільних цілих чисел. Довести, що з них можна вибрати два, різниця яких ділиться на 11.
Розв’язання
Приймемо за «клітки» різні остачі від ділення чисел на 11. Їх усього 11. За «зайців» приймемо остачі від ділення даних чисел на 11. Їх усього 12. Розміщуючи «зайців» у «клітки» аналогічно до попередніх задач, за принципом Діріхле отримаємо, що знайдеться два «зайці» в одній із «кліток». А це означає, що знайдеться два числа, які дають однакові остачі від ділення на 11. Зрозуміло, що різниця цих чисел буде ділитися на 11.
Принцип Діріхле використовується і під час розв’язування задач на зафарбовування.
ЗАДАЧА 15
Кожну грань куба зафарбовано у білий або чорний колір. Довести, що знайдуться однаково зафарбовані грані, що мають спільне ребро.
Розв’язання
Розглянемо довільну вершину куба. У ній перетинаються три грані. Приймемо за «клітки» кольори, а за «зайців» — грані, що перетинаються в одній вершині. Їх усього три. Тому за принципом Діріхле знайдеться клітка, у якій міститься два «зайці». А це означає, що знайдуться дві грані, які мають спільне ребро (оскільки вони мають спільну точку) і зафарбовані однаково.
ЗАДАЧА 16
На шаховій дошці розмірами 8×8 клітинок розставлено 31 фігуру. Довести, що знайдеться вільна фігура, яка складається з трьох клітинок і зображена на малюнку.
Розв’язання
Для того щоб не було вільної фігури, складеної з трьох клітинок, у будь-якому квадраті розмірами 2х2 клітинки має розміститися не менше двох фігур. Оскільки можна покрити всю дошку 16-ма квадратиками розмірами 2×2 клітинки, що не перекриваються, то всього фігур має бути не менше 32, а у нас є 31. Отже, за сформульованим принципом знайдеться квадрат розмірами 2×2 клітинки, в якому опиниться лише одна фігура. У ній і міститься вільна фігура, що складається з трьох клітинок.
ЗАДАЧА 17
У класі 26 учнів, доведіть, що у році є місяць, коли святкують день народження точно 3 учні?
Розв’язання
Припустимо, що ми маємо найменш сприятливий варіант, коли кожного місяця є учні, що святкують день народження. Оскільки місяців 12, то якщо кожного місяця буде по два іменинника, тоді:
12*2=24, 26-24=2.
Отже, у цих двох учнів день народження припадає на місяць, у якому вже народилося два учні, тобто є хоча б один місяць, коли народилося 3 учні!
ЗАДАЧА 18
У школі навчається 962 учні. Довести, що принаймні у двох учнів збігаються ініціали.
Розв’язання
Зауважимо, що з двох букв можна утворити 2 ∙ 2 = 4 різних пар ініціалів. (Якщо це, наприклад, букви А і Б, то матимемо: А.А., А.Б., Б.А., Б.Б.). В українському алфавіті 31 буква, що може входити до складу ініціалів. Тому всього можна утворити 31 ∙ 31 = 961 різних пар ініціалів. Візьмемо 961 ящик і кожному з них нанесемо пару ініціалів. Напишемо для кожного учня його ініціали на картці і кожну картку покладемо у той ящик, на якому написано таку саму пару ініціалів. Оскільки розкладаємо 962 картки в 961 ящик, то, відповідно до принципу Діріхле, принаймні в одному ящику буде не менше від однієї картки.
ЗАДАЧА 19
У школі навчаються 400 учнів. Довести, що хоча б двоє з них народилися в один день року.
Розв’язання
Найбільше в році буває 366 днів. Якщо дні вважати клітками, як у формулюванні принципу Діріхле, а учнів ― кроликами, то в деякій клітці сидять не менше як кроликів, тобто більше від одного кролика. Отже, не менше двох учнів народилися в один день року.
Можна міркувати від супротивного. Припустимо, що кожний день відзначають день народження не більше, ніж один учень, тоді всього учнів не біль-ше від 366 ― суперечність.
ЗАДАЧА 19
Кіт Базіліо пообіцяв Буратіно відкрити велику таємницю, якщо той складе чарівний квадрат 6 × 6 із чисел +1, −1, 0 так, щоб всі суми по рядкам, по стовпцям і по великим діагоналям були різні. Чи може Буратіно скласти такий квадрат?
Розв’язання
Вказані суми чисел можуть змінюватися в межах від −6 до +6. Всього ― 13 значень. Рядків у квадраті є 6, стовпців ― 6, діагоналей ― 2. Маємо 14 різних сум. За принципом Діріхле хоча б дві з цих сум мають дорівнювати одна одній. Отже, скласти такий квадрат неможливо. ■
ЗАДАЧА 20
На Землі океан займає більше половини площі поверхні. Довести, що в світовому океані можна вказати дві діаметрально протилежні точки.
Розв’язання
Відобразимо океан симетрично центру Землі. Оскільки сума площ океану і його образу перевищує площу земної поверхні, то існує точка, що належить океану і його образу. Візьмемо за шукані цю точку разом з протилежною до неї.
ЗАДАЧА 21
На співбесіду прийшли 65 школярів. Їм запропонували 3 тестові завдання. За кожне завдання ставилася одна з оцінок: 2, 3, 4 або 5. Чи вірно, що знайдуться два школярі, що одержали однакові оцінки з усіх тестових завдань?
Розв’язання
Розглянемо всі набори з трьох оцінок за відповідні завдання. Кількість таких наборів дорівнює 43 або 64 (4 можливості за кожне з трьох тестових завдань). Оскільки число учнів більше, ніж 64, то за принципом Діріхле деяким двом учням відповідає один набір оцінок.
ЗАДАЧА 22
В класі навчається 35 учнів. Доведіть , що серед них є принаймні 2, у яких день народження одного числа (можливо, в різні місяці).
Доведення
Тут „клітки” – дні місяця, а „кролики” -учні. Оскільки треба довести, що є принаймні 2 таких учні, то припускаємо, що таких учнів є не більше одного. Тоді за 31 день місяця може відсвяткувати свій день народження не більше 31 учня. Але це суперечить умові (учнів 35). Отже, наше припущення невірне. Тому є в класі хоча б 2 таких учні, у яких день народження одного числа.
ЗАДАЧА 23
В мішку лежать кульки двох кольорів – чорного і білого. Яку найменшу кількість кульок треба витягнути, щоб серед них опинилось дві кульки одного кольору?
Розв’язання
Кульки – „кролики”, кольори – „клітки”. І за принципом Діріхле „кроликів” мало би бути хоча б на 1 більше, тому логічно припустити, що кульок мало би бути 3. Доведемо це. Припустимо, що кульок слід дістати не більше, ніж дві. Тоді одна може бути чорна, а одна біла, що не задовольняє умову. Якщо ж кульок три, то для 2-х кольорів є З кульки. Отже, за законом Діріхле знайдеться хоча б 2 кульки одного кольору.
ЗАДАЧА 24
В місті Санкт-Петербург живе три мільйони людей. Доведіть, що у
яких-небудь двох із них однакова кількість волосин на голові.
Розв’язання
Очевидно, що «кролики» – це жителі Санкт-Петербурга, «клітки»- кількість волосин на голові. Але перше запитання тут: скільки є “кліток”? Їх буде 2 000 001, оскільки люди можуть бути як з волоссям на голові, так і лисі. І знову доведення від супротивного: Припустимо, що є не більше однієї людини з певною кількістю волосся на голові. Тоді всього в місті живе не більше 2 000 001 людини, що суперечить умові. Отже, наше припущення невірне. Отже, у Санкт-Петербурзі є щонайменше двоє людей з однаковою кількістю волосин на голові.
ЗАДАЧА 25
В магазин привезли 25 ящиків яблук з трьома різними сортами
яблук – в кожному ящику по окремому сорту яблук. Довести, що серед них
знаходиться принаймні 9 ящиків яблук одного сорту.
Доведення
«Клітки» — сорти яблук; «кролики»” — ящики.
Припустимо, що кожного сорту не більше 8 ящиків. Тоді 8*3=24, а ящиків 25.
Отже, наше припущення хибне. Тому є принаймні 9 ящиків яблук одного
сорту.
ЗАДАЧА 26
10 школярів на олімпіаді розв’язали 35 задач, причому серед них є такі, що розв’язали рівно одну, рівно дві, рівно три задачі. Довести, що є
учень, який розв’язав не менше 5 задач.
Доведення
Якщо розв’язувати задачу напряму, то матимемо: Припустимо, що всі діти розв’язали не більше, ніж по 4 задачі, тоді розв’язаних задач , що задовольняє умову.
Але можна відокремити трьох учнів: одного — з однією задачею, одного — з двома, одного — з трьома задачами. Тоді відокремимо відповідно і 1+2+3=6 задач.
Маємо: 10—3=7учнів, 35—6=29 задач.
Припустимо, що кожен з 7 учнів розв’язав не більше 4 задач, тоді всього
розв’язано не більше 28 задач. А це суперечить умові. Тому є хоча б один учень, що розв’язав хоча б 5 задач.
Крім відокремлювання змінних зустрічаються ще і задачі, які потребують додаткових міркувань. Їх можна запропонувати на наступному етапі вивчення теми.
ЗАДАЧА 27
У країні Дитляндії М футбольних команд по 11 чоловік в кожній. Всі футболісти зібрались у аеропорту для поїздки в іншу країну на відповідальний матч. Літак зробив 10 рейсів у іншу країну, перевозячи при цьому по М футболістів кожного рейсу. Ще один футболіст добрався сам. Доведіть, що хочаб 1 команда зібралась у повному складі у іншій країні.
Доведення
I спосіб
Нехай жодна із команд не зібралась повним складом у іншій країні.
Літак перевіз 10М пасажирів, а ще один добрався сам, тому всього переїхало
(10М+1) футболістів. Всього ж їх було 11М. Згідно з нашим припущенням,
принаймні по одному гравцю кожної команди залишилось у аеропорту, тобто
їх залишилось не менше М гравців. Але було 11М гравців, і прилетіло (10М+1)
гравців, тобто залишилось 11М-10М-1=М-1 футболістів. Отже, наше
припущення хибне. Тому хоча б 1 команда зібралась повним складом у іншій
країні.
Слід звернути увагу, що учні могли б піти іншим шляхом міркувань. В такому випадку не слід їх зупиняти, а розібрати обидва способи розв’язання цієї задачі.
II спосіб: Нехай в країні призначення не зібралось жодної команди у повному складі. Тоді кожної команди приїхало не більше 10 чоловік, а всього приїхало не більше 10М чоловік, що суперечить умові і літак привіз 10М чоловік і 1 добрався сам. Тобто всього добралося (10М+1) чоловік. Отже, наше припущення невірне, тому хоча б одна команда зібралась повним складом у
іншій країні.
ЗАДАЧА 28
Дано 8 різних натуральних чисел, кожне з яких не перевищує 15. Довести, що серед попарних різниць різних чисел є 3 однакові.
Доведення
Різниця двох таких попарно різних чисел може дорівнювати будь-якому числу від 1 до 14. А кількість таких пар чисел дорівнює . Тоді можна взяти „ кроликів” як пари чисел і розташувати їх по 2 в кожну „клітку”- результат різниці. І умова задачі не виконується. Але можна
також ще помітити, що любе число від 1 до 13 може бути поданим у вигляді
кількох різниць, а 14- ні :
1=2-3=4-3=… 2=5-3=6-4=… 13=15-2=14-1 14=15-1.
Тоді матимемо 13 „кліток” і 27 „кроликів” і згідно принципа Діріхле дійсно,
серед попарних різниць різних чисел є хоча б 3 однакових.
ЗАДАЧА 29
В кожній клітинці клітчастої дошки 7*7 сидить коник. Всі вони за командою перескакують на сусідню клітинку, але не по діагоналі. Довести, що після виконання цієї команди знайдеться клітинка, в якій сидить 2, або більше коників.
Доведення
Дуже часто в задачах з клітчастою дошкою застосовують метод розфарбовування в декілька кольорів. Розфарбуємо нашу дошку за принциом шахової. Тоді кожний коник сидить на білій або чорній клітинці. Причому чорних клітинок буде 25, а білих 24(або навпаки, що не є суттєвим). За командою коник, що був на чорній клітинці переходить на білу і навпаки. Отже, з 25 чорних клітинок 25 коників перестрибують на 24 білих клітинки. Тому за принципом Діріхле обов’язково знайдеться клітинка, на якій буде сидіти принаймні 2 коника.
Також принцип Діріхле використовується і в геометрії.
ЗАДАЧА 30
Вся площина розмальована в 2 кольори. Довести, що знайдеться дві точки одного кольору, які знаходяться на відстані 1 метра одна від одної.
Доведення
Кольорів 2, тоді інтуїтивно відчувається, що точок слід брати не 1, а більше, тобто три (И кліток; (М+1)кроликів). Візьмемо три точки площини, які розташовані на відстані 1 метра одна від одної. Такі точки вибрати можливо, оскільки існує рівносторонній трикутник із стороною 1 метр. А точками будуть вершини цього трикутника. Тоді за принципом Діріхле серед трьох точок знайдеться хоча б дві однакового кольору. Що і треба було довести.
