Розв’язування логічних задач за допомогою принципу Діріхле у 6-7 кл.

При вирішенні багатьох завдань використовується логічний метод міркування - "від протилежного».  Цей принцип стверджує, що якщо безліч з N елементів розбито на пнепересекающіхся частин, що не мають спільних елементів, де N> n то, по крайней мірі, в одній частині буде більше одного елемента. Принцип названий на честь німецького математика Діріхле (1805-1859), який успішно застосовував його до доказу арифметичних тверджень В чому ж полягає принцип Діріхле? Для учнів 6-7 класів зручніше всього подавати його в жартівливій формі: «Якщо в N клітках сидить не менше N+1 кролика, то існує хоча б одна клітка, де сидить не менше, ніж 2 кролика.»

Слід звернути увагу учнів на слова "не менше", "хоча б", оскільки саме ці фрази дозволяють по-перше, розпізнати задачі на принцип Діріхле, а по-друге, тільки використовуючи такі формулювання можна розв'язувати ці задачі. Як же довести цей принцип? Доведення базується на методі доведення від супротивного.

Припустимо, що у кожній клітці сидить не більше одного (тобто один або жодного) кролика. Тоді в усіх клітках сидить не більше N кроликів. А це суперечить умові, оскільки кроликів є N+1. Отже, наше припущення було хибним, тобто знайдеться хоча б одна клітка, в якій сидить не менше 2 кроликів.

Але клітки і кролики є не в кожній задачі. Тому самим першим кроком при розв'язуванні задач є визначення того, кого прийняти за «клітки», а кого за  «кроликів».

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

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

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

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

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

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

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

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

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

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

Розв’язання. Приймемо за «клітки» всі можливі варіанти кількості помилок. Їх є 14, оскільки учні можуть зробити 0, 1, ..., 13 помилок. «Зайцями» вважатимемо учнів, які писали диктант і яких за умовою є 29. Кожного з них «садимо» у «клітку», що відповідає кількості зроблених помилок. Зрозуміло, що знайдеться «клітка», в якій «сидять» принаймні три «зайці», а це й означає, що знайдуться три учні, які зробили однакову кількість помилок. ■

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

Розв’язання. У році може бути максимум 53 тижні. Їх і приймемо за «клітки», а за «зайців» — учнів. Розсаджуватимемо «зайців» у ті «клітки», що відповідають їх дням народження. Оскільки 160 : 53 =  , то за принципом Діріхле знайдеться «клітка», у якій є принаймні 4 «зайці». Це означає, що знайдеться тиждень, на який припаде день народження відразу у чотирьох учнів. ■

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

Розв’язання. Нехай «клітками» будуть усі різні значення сум трьох чисел, кожне з яких набуває значення 0, 1 або −1. Зрозуміло, що таких значень є 7. Це −3; −2; −1; 0; 1; 2; 3. «Зайцями» будуть набори із трьох чисел, що розміщені або в одному стовпці, або в одному рядку, або на одній із двох діагоналей таблиці. Таких наборів є 8.

За принципом Діріхле знайдеться «клітка», де сидять не менше двох «зайців». А це й означає, що знайдуться дві розглядувані трійки чисел, для яких суми рівні.

Відповідь. Ні. ■

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

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

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

Розв’язання. а) Якщо за «клітки» прийняти кольори рукавичок, то взявши три довільні рукавички, ми отримаємо, що в одній із «кліток» знаходяться два «зайці» ― рукавички. А це і вимагається в задачі. Отже, щоб були дві рукавички одного кольору, потрібно витягнути щонайменше 3 рукавички.

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

Справді, якщо за «клітки» прийняти кольори рукавичок (їх два), а за «зай-ців» — рукавички, то за узагальненим принципом Діріхле в одній з «кліток» буде не менше 11 «зайців». Це означає, що знайдеться 11 рукавичок одного кольору. Але ми маємо лише 10 пар рукавичок одного кольору. Тому всі вони не можуть бути на одну руку. Отже, серед цих 11 рукавичок знайдеться одна пара рукавичок одного кольору. ■

Розглянемо, як принцип Діріхле використовують для розв’язування задач на подільність. Такі задачі — це класичний приклад застосування принципу Діріхле.

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

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

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

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

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

Розв’язання. Приймемо за «клітки» різні остачі від ділення чисел на 11. Їх є усього 11. За «зайців» приймемо остачі від ділення даних чисел на 11. Їх є усього 12. Розміщуючи «зайців» у «клітки» аналогічно до попередніх задач, за принципом Діріхле отримаємо, що знайдуться два «зайці» в одній із «кліток». А це означає, що знайдеться два числа, які дають однакові остачі від ділення на 11. Зрозуміло, що різниця цих чисел буде ділитися на 11. ■

Принцип Діріхле використовують і при розв’язуванні задач на зафар-бовування.

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

Розв’язання. Розглянемо довільну вершину куба. У ній перетинаються три грані. Приймемо за «клітки» кольори, а за «зайців» — грані, що перетинаються в цій вершині. Їх є усього три. Тому за принципом Діріхле знайдеться «клітка», у якій міститься два «зайці». А це означає, що знайдуться дві грані, які мають спільне ребро (оскільки вони мають спільну точку) і зафарбовані однаково. ■

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

Рис. 4

Розв’язання. Для того щоб не було вільної від фішок фігури, складеної з трьох клітинок, у будь-якому квадраті розміром 2 × 2 має розміститися не менше двох фішок. Оскільки можна покрити всю дошку 16-ма квадратами розміром 2 × 2, що не перекриваються, то всього фігур має бути не менше від 32, а у нас є 31. Отже, за сформульованим принципом знайдеться квадрат розміром 2 × 2, в якому є лише одна фігура. У ньому і міститься вільна від фішок фігура, що складається з трьох клітинок. ■

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

Розв’язання. Позначимо дані точки через . Із точки  виходять 5 відрізків двох кольорів. За принципом Діріхле, серед цих відрізків є 3 відрізки одного кольору. Нехай це відрізки  червоного кольору. Розглянемо відрізки . Можливі випадки:

а) Серед цих відрізків є відрізок червоного кольору, наприклад, відрі-зок . Тоді в трикутнику  всі сторони червоні.

б) Серед цих відрізків немає відрізка червоного кольору. Тоді в трикутнику  всі сторони сині.

Отже, знайдеться трикутник, усі сторони якого мають один колір. ■

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

Розв’язання. Неважко помітити, що 664 складає приблизно третину від 1991, а саме, 1991 = 3 · 663 + 2, тому при будь-якому розбитті множини, що складається з 1991 точки, на три підмножини, хоча б в одну з цих підмножин потрапить 664 чи більше точок. Отже, для розв’язування задачі достатньо показати, що квадрат зі стороною 6 см можна розбити на три частини, кожну з яких можна покрити квадратом зі стороною 5 см. Як видно з рис. 5, квадратABCD покривають три квадрати PCDQ, AKMN, AKM₁N₁.  Принаймні один з цих трьох квадратів покриває хоча б 664 з даних точок. ■