Олімпіади

Посилання  на папку Вебінари >>>

Шановні колеги!
Дуже важлива інформація для тих, хто готує учнів до третього етапу.
Рекомендуємо ознайомитися і по можливості потренуватись з учнями в розв'язуванні задач Київської міської олімпіади 2017.

    http://matholymp.com.ua/…/uploads/2017/01/tekst-tur-1-72.pdf

Сайт обласної олімпіади юних математиків Дніпропетровщини 2016-2017

 Принцип Діріхле

Діріхле мав хист поєднувати з мінімумом сліпих формул максимум зрячих думок

Г. Мінковський

 

13 лютого 2017року минає 212 років з дня народження відомого німецького математика  Петера Діріхле (1805 – 1859 рр.). 

Визнання він заслужив завдяки ряду відкриттів у алгебрі і теоріі чисел, важливих досліджень в області математичного аналізу, вагомих результатів у механіці та математичній фізиці.

Ця розробка адресована тим, хто хоче навчитися розв’язувати задачі олімпіадної математики.  

Мета цієї розробки – надати учням конкретну допомогу в розвитку вміння розв’язувати олімпіадні задачі з даної теми.

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

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

***

При розв’язуванні багатьох задач люди користуються способами міркувань, які одержали назву «принцип Діріхле» («принцип висунутих ящиків»). У найпростішій і дотепній формі принцип Діріхле звучить так: »Не можна посадити 7 зайців у 3 клітки так, щоб у кожній клітці було не більше, ніж 2 зайці».

А взагалі твердження формулюється так:

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

Щоб застосувати принцип Діріхле до розв'язування задачі, ми повинні вказати, що саме будемо розуміти під «клітками» і «зайцями», а також спосіб, за яким будемо розсаджувати «зайців» у «клітки».

Як правило, під час розв'язування задач використовують не принцип Діріхле, а деяке його узагальнення:

Дано п кліток і пк+1 зайців, які розміщено у ці клітки. Тоді знайдеться клітка, де сидить не менше к + 1 зайців.

Проілюструємо застосування принципу Діріхле на розв’язуванні задач, серед яких є арифметичні й геометричні, жартівливі й побутові.

При  розв’язуванні таких задач  необхідно, по-перше, грамотно сформулювати  стратегію, а по-друге, довести, що вона справді веде до виграшу.

Тому завдання даного типу дуже корисні для розвитку розмовної математичної культури, чіткого розуміння того, що означає розв’язати задачу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 9. На шаховій дошці розмірами 8x8 клітинок розставлено 31 фігуру. Довести, що знайдеться вільна фігура, яка складається з трьох клітинок і зображена на малюнку.

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

Додаткові задачі

1. В гуртку 10 школярів. Чи можна стверджувати, що серед цих гуртківців є хоча б 2, які відзначають день народження в одному й тому самому місяці?

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

3. У школі 740 учнів. Довести, що принаймні троє з них народилися в один і той самий день.

4.  У похід пішло 12 туристів. Наймолодшому з них 20 років, а найстаршому - 30.

     Чи є серед них однолітки?

5. В шаховому турнірі кожен шахіст зіграв з кожним по одній партії. Всі отримали принаймні по одній перемозі. Довести, що якісь двоє шахістів у підсумку мають однакову кількість перемог.

6.  У вищій лізі першості України з футболу виступає 16 команд. У другому крузі чемпіонату кожні дві команди повинні зіграти між собою один матч. Довести, що завжди є дві команди, які провели однакову кількість ігор чемпіонату.

7.  У районі 15 шкіл. Довести, що як би між ними не розподіляли 90 комп'ютерів, обов'язково знайдуться дві школи, які отримали однакову кількість комп'ютерів (можливо — жодного).

8. ( Районна олімпіада 1998-1999 рр.) В таксі їдуть 5 пасажирів. Доведіть, що серед них знайдуться два пасажири, які мають однакову кількість знайомих серед цих 5-ти пасажирів.

9.  ( Районна олімпіада 2000-2001 рр.) Одинадцять школярів відвідують п’ять гуртків (деякі з учнів не обов’язково відвідують всі гуртки). Доведіть, що серед них є два учні, А і В, такі, що всі гуртки, які відвідує А, відвідує й В.

Список рекомендованої літератури

1.  Бабинская И.Л. Задачи математических олимпиад. – М.: Наука.- 1975.

2. Вишенський В.А., Ядренко М. Й. Вибрані математичні задачі.-К.: Вища школа, 1974.

3. Генкін С.А., Ітенберг І.В., Фомін Д.В. Ленінградські математичні гуртки. -К.:ТВіМС, 1997.

4. Гусев В.А. и др. Внеклассная работа по математике в 6-8 классах. Под ред.. С.И. Шварцбурда. М., «Просвещение», 1977.

5. Конет І.М., Паньков В.Г., Радченко В.М., Теплінський Ю.В. Обласні математичні олімпіади. - Кам’янець-Подільський: Абетка.-2000.

6.     Маланюк М.П., Лукавецький В.І. Олімпіади юних математиків. – К.: Рад. шк., 1972.

7. Конет І.М., Паньков В.Г., Теплінський Ю.В. Хмельницькі обласні олімпіади юних математиків. - Кам’янець-Подільський: Абетка. – 1998.

8.  Сарана О.А. Математичні олімпіади: просте і складне поруч:- К.: Видавництво А. С. К., 2004.

9. Ядренко М.Й. Принцип Діріхле: Бібліотечка фізико-математичної школи.- К.:Вища шк., 1985.  

10. Ясінський В.А. Задачі математичних олімпіад та методи їх розв’язування. -  Вінниця. 1998.

______________________________________________________________________________________________