Дуже часто буває так, що при розв'язуванні складних математичних задач використовують уже відомі методи, прийоми, принципи, теорії тощо. Завдяки цьому, деякі класи задач стають алгоритмічними, і їхні розв'язки - доступними широкому загалу. Одним із таких принципів є широковідомий принцип Діріхле. За традицією в літературі принцип Діріхле пояснюється на прикладі "зайців і кліток": якщо п'ятьох зайців розсадити в чотири клітки, то принаймні в одній із них опиниться більше одного зайця.
Принцип Діріхле, не зважаючи на його надзвичайну очевидність і простоту, часто використовується при розв'язувані задач і доведенні теорем у різних галузях математики. Більш загальне формулювання принципу Діріхле звучить так: якщо пк+1 предмет розкладено в п ящиків, то принаймні в одному з ящиків знаходиться не менше ніж к+1 предмет.
Продемонструємо приклади застосування принципу Діріхле до розв’язування логічних задач.
Задача 1. По вулицях міста рухаються 487 тролейбусів. В кожному з них може знаходитися не більше ніж 70 людей. Крім водія в тролейбусі завжди їде кондуктор. Довести, що обов’язково знайдеться 8 тролейбусів, в яких їде однакова кількість людей.
Розв’язання. За умовою задачі різних кількостей людей в тролейбусах може бути не більше ніж 69 варіантів (від 2 до 70 чоловік). Оскільки 69*7=483<487, то за принципом Діріхле обов’язково знайдеться 8 тролейбусів з однаковою кількістю людей.
Задача 2. Баба-Яга та Кащей зібрали деяку кількість мухоморів. Кількість цяточок на мухоморах Баби-Яги в 13 разів більше, ніж на мухоморах Кащея, але після того, як Баба-Яга віддала Кащею свій мухомор з найменшим числом цяточок, на її мухоморах стало цяточок тільки у 8 разів більше, ніж у Кащея. Доведіть, що спочатку у Баби-Яги було не більше 23 мухоморів.
Розв’язання. Нехай на мухоморах Кащея було п цяточок, а на тому, що він отримав, було к цяточок. Тоді в Баби-Яги було 13п цяточок, а залишилося 13п - к = 8(п + к). Тобто п = 9к/5. Виходить, у Баби-Яги на початку було цяточок 117к/5=23,4к < 24к, а оскільки на кожному мухоморі було не менше к цяточок, то, за принципом Діріхле, їх у неї було не більше ніж 23.
Задача 3. На збори приїхала 201 людина з п’яти країн. Серед кожних 6 з них знайдеться двоє однакового віку. Доведіть, що з деякої країни на збори приїхало не менше 5 людей однієї статі та одного віку.
Розв’язання. Оскільки за умовою задачі з кожних 6 присутніх можна вибрати двох однакового віку, то серед учасників є люди не більше, ніж п’яти різних віків. Принцип Діріхле дає змогу з’ясувати, що принаймні 41 учасник зборів має однаковий вік (40*5<201). Повторно застосувавши принцип Діріхле, робимо висновок, що з 41 учасника принаймні 9 будуть з однієї країни. Втретє застосувавши принцип Діріхле, маємо змогу переконатись, що не менше 5 з цих 9 учасників будуть однієї статі.
Задачі для самостійного розв’язування
Задача 4. 10 учнів на олімпіаді розв’язали 35 задач, причому відомо, що серед них є учні, які розв’язали рівно одну задачу, учні, які розв’язали рівно дві задачі і учні, які розв’язали рівно три задачі. Доведіть, що є учень, який розв’язав не менше п’яти задач.
Задача 5. П’ятеро працівників отримали на всіх зарплату в розмірі 1500 грн. Кожний з них хоче придбати собі телефон вартістю 320 грн. Доведіть, що комусь з них доведеться почекати з придбанням телефону до наступної зарплати.
Задача 6. У бригаді працюють 7 чоловік. Їх загальний вік - 332 роки. Довести, що серед них можна вибрати трьох працівників, сума віків яких не менше 142 років.
Задача T. Дві коробки містять разом 65 кульок не обов’язково однакових розмірів. Кожна кулька одного з чотирьох кольорів: білого, чорного, червоного або жовтого. Якщо взяти будь-яких п’ять кульок одного кольору, то щонайменше дві з них матимуть однаковий розмір. Довести, що існує принаймні три кульки, які мають однаковий колір і однаковий розмір, і знаходяться в одній коробці.
Задача 8. Довести, що серед довільних 255 попарно різних натуральних чисел, які не перевищують 500, знайдуться вісім чисел, сума яких дорівнює 2008.
Вказівка. Розіб‘ємо всі натуральні числа від 1 до 500 на групи наступним чином: l).j^.500 ,j3},499 $0,252 ,j5$51 (в усіх групах крім першої і останньої сума чисел дорівнює 502). Груп
всього 251. Розглянемо довільні 255 натуральних чисел, що не перевищують 500. За принципом Діріхле знайдеться чотири групи в які потрапили по два числа з цих 255 (дійсно, якби в кожну групу потрапило не більше одного з розглядуваних 255 чисел, то груп мало б бути не менше 255). Очевидно, це не перша і не остання група (вони складаються, за побудовою, лише з одного числа).
Використані джерела
Олімпіади з математики Чернігівської області, 2005-2008 роки./ Укл.: Дяченко О.В., Лось В.М., Тихієнко В.П. - Чернігів: ЧПДУ, 2008. - 60 с.
Лось В.М., Тихієнко В.П. Математика: навчаємо міркувати. Розв’язування нестандартних задач. Навчальний посібник. - К.: Кондор, 2005. -312с.
Немає коментарів:
Дописати коментар