Математика - це цікаво

Розвязування задач за допомогою принципу Діріхле

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

Принцип Діріхле, не зважаючи на його надзвичайну очевидність і простоту, часто використовується при розв'язувані задач і доведенні теорем у різних галузях математики. Більш загальне формулювання принципу Діріхле звучить так: якщо пк+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. У школі навчається 962 учні. Довести, що принаймні у двох учнів збігаються ініціали.
          Розв’язання.  Зауважимо, що з двох букв можна утворити 2 ∙ 2 = 4 різних пар ініціалів. (Якщо це, наприклад, букви А і Б, то матимемо: А.А., А.Б., Б.А., Б.Б.). В українському алфавіті 31 буква, що може входити до складу ініціалів. Тому всього можна утворити 31 ∙ 31 = 961 різних пар ініціалів. Візьмемо 961 ящик і кожному з них нанесемо пару ініціалів. Напишемо для кожного учня його ініціали на картці і кожну картку покладемо у той ящик, на якому написано таку саму пару ініціалів. Оскільки розкладаємо 962 картки в 961 ящик, то, відповідно до принципу Діріхле, принаймні в одному ящику буде не менше від однієї картки.

Задача 5. У класі навчається 29 учнів. Під час диктанту один учень допустив 13 помилок, а всі інші учні – менше. Довести, що в класі є принаймні три учні, які припустились однакової кількості помилок.
          Розв’язання.   Розіб’ємо всіх учнів у класі на 14 груп: до першої віднесемо тих учнів, які написали диктант без помилок, до другої − тих, які припустились однієї помилки, до третьої – двох помилок, і т. ін., до тринадцятої – дванадцять помилок, чотирнадцята група складається тільки з одного учня, який припустився 13 помилок. 
          Якби в кожній з перших тринадцяти груп було не більше від двох учнів, то загальне число учнів у класі не перевищувало б 2 ∙ 13 + 1 = 27 учнів. Тому принаймні в одній з груп повинно бути не менш ніж три учні. 

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

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

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

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

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

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

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

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

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

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

 Задачі для самостійного розв’язування

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

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

3. У бригаді працюють 7 чоловік. Їх загальний вік - 332 роки. Довести, що серед них можна вибрати трьох працівників, сума віків яких не менше 142 років.

4. Дві коробки містять разом 65 кульок не обов’язково однакових розмірів. Кожна кулька одного з чотирьох кольорів: білого, чорного, червоного або жовтого. Якщо взяти будь-яких п’ять кульок одного кольору, то щонайменше дві з них матимуть однаковий розмір. Довести, що існує принаймні три кульки, які мають однаковий колір і однаковий розмір, і знаходяться в одній коробці.

5. Довести, що серед довільних 255 попарно різних натуральних чисел, які не перевищують 500, знайдуться вісім чисел, сума яких дорівнює 2008.

6.У похід пішло 14 туристів. Наймолодшому з них 20 років, а найстаршому - 30.Чи є серед них однолітки?

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

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

МАГІЧНІ КВАДРАТИ

Жартівливі приклади часто набувають більшого значення, ніж корисні. 

М.  Штіфель

           Магічні квадрати — це  квадратні таблиці нату­ральних чисел з однаковою кількістю рядків і стовп­ців, які мають одну й ту ж саму суму чисел у всіх рядках,  стовпцях і діаго­налях.

  Можна побудувати  ма­гічний квадрат 3x3.
 Такий квадрат єдиний. Решту ма­гічних квадратів 3x3 мож­на  одержати з нього або шляхом повороту  навколо центра  або  відображенням    відносно  однієї з його осей симетрії.
          Зі збільшенням розмірів квадрата (кількості кліти­нок) швидко зростає

кіль­кість можливих магічних квадратів  такого  розмі­ру. Кількість різних ма­гічних квадратів розміром 4x4 дорівнює 880, а розмі­ром 5x5 — наближається до чверті      мільйона. 

                                               ЧОМУ КВАДРАТИ    МАГІЧНІ?

            Назву магічних (чарівних, таємничих) квадрати одержали від арабів, які вбачали в   таких числових властивостях і сполуках дещо неземне та  містичне і вважали  такі  квадрати талісманами.

         Історія виникнення магічних квадратів сягає  сивої давнини. Найбільш ранні відомості про такі  квадрати містять  китайські книги, написані у  IV-V ст. до н. е.

         Найвідомішим із стародавніх  магічних квадратів є  Ло-шу (2200 р. до н. е): таблиця  з дев'яти клітинок, заповнена числами  від 1 до 9. І сьогодні його можна побачити    на амулетах, які носять у Східній Азії та Індії. Наступні  за часом відомості  про магічні квадрати дійшли до нас    із   Індії та Візантії. 

Способами складання магічних квадратів     

                                     займалися   відомі  математики

 А. Різе, М. Штіфель( ХVI ст.),  А. Кірхер, Баше де Мезеріак  (XVII ст) та інші.

   У Європі зображення  магічного квадрата вперше з'явилося в гравюрі «Меланхолія» відомогонімецького   художника Альбрехта Дюрера.

З давніх часів і дотепер дослідження магічних  квадратів  процвітало як своєрідний   культ і досить часто було овіяно   містичним    туманом.

ОСОБЛИВОСТІ ДЕЯКИХ МАГІЧНИХ КВАДРАТІВ

         Найдавніший квадрат четвертого порядку було знайдено в  Кхаджурахо (Індія). Цей магічний квадрат належить до так званих «диявольських» (або 

«пандіагональних») квадратів, ще більш дивовижних, ніж симетричні.
Крім звичайних властивостей, такі квадрати є магічними за всіма«ламаними діагоналями». Наприклад, числа 2, 12, 15 і  5,а також 2, 15 і  4 стоять на ламаних діагоналях. «Диявольський» квадрат збереже свої властивості, якщо його верхній рядок пере­ставити вниз, або навпаки,   нижній     рядок поміс­тити  вгору, а також якщо викреслити  останній стовпець   зліва або    справа і приписати його до квадрата з    протилежної   сторони.

ЧИ ВІРИТЕ ВИ, ЩО...

-         не існує магічних ква­дратів розміром 2x2?

-         існує безліч магічних квадратів розміром 3x3?

-         властивостями магіч­них квадратів цікавився Бенджамін Франклін — один із авторів Деклара­ції незалежності США?

-         числа 15 і 14, які сто­ять у нижньому рядку магічного квадрата, зoбраженого на гравюрі Дюрера, означають да­ту 1514 — рік створення цієї  гравюри?

-         французький трак­тат про магічні квадра­ти, який вийшов у світ 

      1838  року, складається з трьох великих за обся­гом томів?

 Сірникові головоломки 

 Хіба ти міг коли-небудь подумати, що в звичайнісінькій сірниковій коробці живуть головоломки? Звичайно, вони не живуть там тоді, коли ми використовуємо сірники для запалювання вогню. Але вони одразу поселяються у сірниковій коробці тоді, коли сірники перестають бути звичайними сірниками, а перетворюються на цифри, слова чи фігури. Hе віриш?

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

Отож,  сірникові головоломки.