ГУРТКИ, ФАКУЛЬТАТИВИ Застосування принципу Діріхле до різних задач теорії чисел Світлана Рогачкіна

ГУРТКИ, ФАКУЛЬТАТИВИ Застосування принципу Діріхле до різних задач теорії чисел Світлана Рогачкіна, учитель математики БЗШ І-ІІІ ступенів №18, м. Біла Церква, Київська обл.. Німецький математик XIX століття Лежен Діріхле у своїх наукових дослідженнях часто користувався міркуваннями, які пізніше дістали назву принципу Діріхле. Ознайомлення з цим принципом розпочнемо з такої простої задачі: Чи можна розмістити 5 кроликів у 4-х клітках так, щоб у жодній з кліток не містилося більше одного кролика? – Міркування, безумовно, будуть такими. Якби у кожній клітці сиділо не більше одного кролика, то у 4 клітках помістилося б не більше чотирьох кроликів. А тому 5 кроликів розмістити обумовленим способом не можна. А якщо в тих же чотирьох клітках потрібно буде розмістити 9 кроликів? – Міркуємо аналогічно. Якщо в кожній клітці буде не більше двох кроликів, то в чотирьох клітках всі 9 кроликів не помістяться. Отже, принаймні в одній із кліток слід буде помістити не менше трьох кроликів. Нехай тепер маємо n кліток і т кроликів (т > п), причому відомо, що т = к п + р, де к і р – натуральні числа (р > 1). Тоді в одну з кліток доведеться помістити не менше, ніж (к + 1) кролика. Замінюючи клітки та кроликів довільними множинами А та В що складаються відповідно із п та т елементів (т > п), приходимо до такого твердження. Якщо кожному елементу множини А поставлено у відповідність деякий елемент множини В, то принаймні одному елементу із А відповідатиме не менше двох елементів із В. Це твердження і називається принципом Діріхле. У випадку, коли т = к п + р, де р > 1, одержуємо найпростіше його узагальнення: принаймні одному елементу із А відповідатиме не менше, ніж (к + 1) елемент із В. Принцип Діріхле, не зважаючи на його надзвичайну очевидність і простоту, часто використовується під час розв'язування задач і дове­денні теорем у різних галузях математики. Заслуга Діріхле не в формулю­ванні очевидного твердження, а в тому, що він перший помітив, що з та­кого простого твердження можна дістати глибокі результати про наближення ірраціональних чисел раціональними. Розглянемо різні нематематичні застосування принципу Діріхле. Задача 1. У школі навчається 962 учні. Довести, що принаймні у двох учнів збігаються ініціали. Розв’язання: Зауважимо, що з двох букв можна утворити 2 ∙ 2 = 4 різних пар ініціалів. (Якщо це, наприклад, букви А і Б, то матимемо: А.А., А.Б., Б.А., Б.Б.). В українському алфавіті 31 буква, що може входити до складу ініціалів. Тому всього можна утворити 31 ∙ 31 = 961 різних пар ініціалів. Візьмемо 961 ящик і кожному з них нанесемо пару ініціалів. Напишемо для кожного учня його ініціали на картці і кожну картку покладемо у той ящик, на якому написано таку саму пару ініціалів. Оскільки розкладаємо 962 картки в 961 ящик, то, відповідно до принципу Діріхле, принаймні в одному ящику буде не менше від однієї картки. Задача 2. У турнірі бере участь п шахістів. Кожні два з них повинні зіграти між собою одну партію. Довести, що в будь-який момент змагань є два шахісти, які зіграли однакову кількість партій. Розв’язання: Розглянемо два випадки: у даний момент є шахіст, який не зіграв ще жодної партії; у даний момент немає шахіста, який не зіграв жодної партії; Пронумеруємо шахістів і запишемо для кожного шахіста число партій, які він зіграв на даний момент. Дістанемо числа у випадку 1) кожне з чисел дорівнює одному з чисел 0, 1, …, п–2 (шахіста, який зіграв усі п-1 партій немає, бо відомо, що є шахіст, який не зіграв ще жодної партії). Серед п чисел, які набувають одне з даних п –1 значень, є принаймні два однакових. Таким чином, у випадку 1) твердження задачі справедливе. У випадку 2) кожне з чисел дорівнює одному з чисел 1, 2, ..., п–1, і знову за принципом Діріхле випливає справедливість твердження задачі. Задача 3. У класі навчається 29 учнів. Під час диктанту один учень допустив 13 помилок, а всі інші учні – менше. Довести, що в класі є принаймні три учні, які припустились однакової кількості помилок. Розв’язання: Розіб’ємо всіх учнів у класі на 14 груп: до першої віднесемо тих учнів, які написали диктант без помилок, до другої − тих, які припустились однієї помилки, до третьої – двох помилок, і т. ін., до тринадцятої – дванадцять помилок, чотирнадцята група складається тільки з одного учня, який припустився 13 помилок. Якби в кожній з перших тринадцяти груп було не більше від двох учнів, то загальне число учнів у класі не перевищувало б 2 ∙ 13 + 1 = 27 учнів. Тому принаймні в одній з груп повинно бути не менш ніж три учні. Задача 4. Учень протягом року розв’язує задачі. Щодня він розв’язує принаймні одну задачу, але щотижня – не більш ніж 12. Довести, що знайдеться кілька послідовних днів, протягом яких учень розв’яже 20 задач. Розв’язання: Припустимо, що за перший день учень розв’язав задач, за перші два дні – задач, за перші 77 днів (11 тижнів) -задач. Розглянемо числа: ,,…,. Усього цих чисел 154. Число не перевищує 12 ∙ 11 = 132. Отже, кожне з написаних чисел не перевищує 152, і тому серед них є принаймні два однакових. Проте всі числа у першому рядку різні, бо щодня учень розв’язував принаймні одну задачу. Тому всі числа другого рядка також різні. Залишається припустити, що деяке число з першого рядка дорівнює якомусь числу з другого рядка, тобто при деяких k і l , що й треба було довести. Задача 5. Якщо пряма l лежить у площині трикутника АВС і не проходить через кожну з його вершин, то вона не може перетинати всі три сторони трикутника. Довести це. Розв’язання: Позначимо через і півплощини, на які розбиває площину трикутника пряма l. Півплощини вважатимемо відкритими, тобто не включаємо до них прямої l. Три вершини А, В, С трикутника АВС належить двом півплощинам і . Отже принаймні в одній з півплощин знаходиться дві вершини. Якщо, наприклад, точки А і В лежать в одній площині, то вони знаходяться по один бік від прямої l і пряма l не перетинає сторону АВ. Таким чином, у трикутнику АВС знайшлася сторона, яку пряма l не перетинає. Задача 6. Довести, що з будь-яких десяти двозначних чисел можна вибрати дві різні групи чисел так, щоб суми чисел в обох групах були однаковими. Розв’язання: Підрахуємо спочатку число різних груп, які можна утворити з десяти чисел. Оскільки кожне число може або належати, або не належати до однієї групи, то, згідно з основним принципом комбінаторики, число всіх можливих груп, які утворюються з 10 чисел, дорівнює . При цьому враховуємо й групу, яка не містить жодного числа. Сума чисел у кожній з цих груп менша, ніж 99 ∙ 10 = 990, тобто різних сум не більше як 990. Відповідно до принципу Діріхле, є дві групи, суми чисел в яких однакові. Задача 7. Нехай а і b цілі числа. Відомо, що а² ділиться на а + b. Довести, що b² ділиться на а + b. Розв’язання: Зазначимо, що а² - b²= (а - b)∙(а + b). Отже, b² = а² - (а - b)∙(а + b). За умовою, а² ділиться на а + b, число (а - b)∙(а + b) також ділиться на а+b, отже b² ділиться на а + b. Задача 8. Нехай а і b цілі числа. Довести, що а³ + b³ ділиться на а+ b. Розв’язання: Маємо а³ + b³ = (а + b)(а² - аb + b²), отже а³ + b³ ділиться на а + b. Задача 9. Довести, що коли а і b цілі числа, то аⁿ - bⁿ ділиться на а - b при будь-якому натуральному п. Розв’язання: Легко перевірити, розкривши дужки, що аⁿ - bⁿ= (а-b)(аn-1+ аnb +…+ аbn-2+ bn-1) Таким чином, аⁿ - bⁿ ділиться на а-b. Задача 10. Довести, що серед довільних 1998-ми цілих чисел можна вибрати не менше двох таких, різниця яких ділиться на 1997. Розв'язання: При діленні цілого числа на 1997 можна дістати лише 1997 різних остач: 0, 1, ..., 1996. Оскільки задано 1998 цілих чисел, то принаймні два з них при діленні на 1997 дають одну і ту ж остачу. А тому різниця цих чисел ділитиметься на 1997. Роль кліток у цій задачі відіграють 1997 можливих остач, а роль кроликів – 1998 заданих чисел. Проте спочатку були задані лише "кролики", а "клітки" для них треба було придумати. Задача 11. Довести, що числа і дають однакову остачу при діленні на 11. Розв’язання: Різниця -= (100–1) ∙ = 99 ∙ділиться на 11. Тому числа і при діленні на 11 дають однакові остачі. Задача 12. Із семи аркушів паперу деякі розрізали на 7 частин, потім знову ще кілька аркушів розрізали на 7 частин і т. д. Чи можна у такий спосіб одержати 1984 аркуші? Розв’язання: Зауважимо, що під час розрізання одного аркуша число всіх аркушів збільшується на 6. Якщо всього було розрізано k аркушів, то загальне число аркушів становитиме 6k + 7 = 1984 при натуральному k неможлива, оскільки число 1984 при діленні на 6 дає в остачі 4, а не 7. Отже, в результаті такого розрізання не можна одержати 1984 аркуші. Задача 13. Довести, що число ірраціональне. Розв’язання: Припустимо, що – раціональне число. Тоді = , де а і b натуральні числа, причому вважатимемо, що дріб нескоротний. Тоді а² = 3b². Число 3b² ділиться на 3, тому а² ділиться на 3, а отже, і а ділиться на 3. Таким чином, а = 3с, с – натуральне число. Замінивши а на 3с у рівності а² = 3b², матимемо: 9с² = 3b², b² = 3с. Звідси випливає, що b², а тому і b ділиться на 3. Отже, і число а, і число b ділиться на 3, що суперечить припущенню про нескоротність дробу . Таким чином не є раціональним. Задача 14. Довести, що число ірраціональне. Розв’язання: Нехай = , де а і b натуральні числа, причому а і b взаємно прості (дріб – нескоротний). Тоді а² = 6b². Звідси маємо, що а², а отже, і а є парним числом. Покладемо а = 2с, де с – натуральне число. Тоді 4с² = 6b², 2с² = 3b². Таким чином, число 3b² парне, а це може бути тоді і тільки тоді, коли b парне. Отже, обидва числа а і b ділиться на 2. Це суперечить припущенню про нескоротність дробу . Таким чином, є ірраціональне число. При розв’язуванні задач інколи доводиться мати справу з такою ситуацією: задана система послідовно змінює свій стан, і необхідно визначити певну характеристику її кінцевого стану. Повністю прослідкувати за всіма переходами буває складно, а то і неможливо. Тоді знайти розв’язок допомагає обчислення деякої величини, що характеризує стан системи і зберігається при всіх її переходах. Таку величину називають інваріантом даної системи. Задача 15. Чи можна всі двоцифрові числа від 32 до 86 включно виписати у деякому порядку одне за одним так, щоб одержати запис простого числа? Розв’язання: В якому б порядку ми не записували задані числа, сума цифр, що стоятимуть на непарних місцях, тобто сума перших цифр чисел від 32 до 86 включно, дорівнюватиме 300. Сума ж цифр, що стоятимуть на парних місцях, дорівнюватиме 245. Оскільки число 300 – 245 = 55 ділиться на 11, то в результаті дістанемо число, яке ділиться на 11, і яке, отже, не є простим. Задача 16. Для числа 1997підрахували суму його цифр. В одержаному числі знову підрахували суму цифр, і т.д. аж поки не одержали одноцифрове число. Визначити це останнє число. Розв’язання: При діленні на 9 число 1997 дає остачу 8. Тому остача від ділення на 9 числа 1997така ж, як і числа 8. Але числа 8n при діленні на 9 дають таку послідовність остач: 8, 1, 8, 1, 8 …, елементи якої повторюються з періодом 2. Тому число 8 , а з ним і число 1997, при діленні на 9 дає остачу 8. Оскільки, крім того, остача від ділення на 9 довільного числа та суми цифр цього числа однакові, то скільки разів не застосовувати описану в умові задачі операцію, кожного разу одержуватимемо числа, які при ділені на 9 дають остачу 8. А тому одноцифрове число, яке дістанемо на останньому етапі, дорівнюватиме 8. Задача 17. Скільки існує двоцифрових чисел, обидві цифри яких різні? Розв’язання: Запис довільного двоцифрового числа, очевидно, можна здійснити послідовним записом двох його цифр. Зрозуміло, що першою може бути записана будь-яка з десяти цифр, відмінна від нуля. Тоді другою можна записати будь-яку з решти дев’яти цифр, крім уже записаної першої цифри. Отже, для кожної з дев’яти можливостей запису першої цифри існує по 9 можливостей запису другої. Таким чином дістаємо 9 · 9 = 81 двоцифрових чисел, обидві цифри яких різні. Звернемо увагу, що цю задачу можна було б розв’язати й простіше. Справді, легко підрахувати, що всіх двоцифрових чисел 90. З них лише 9 чисел 11, 22, …, 99 мають обидві однакові цифри. Отже, у 90 – 9 = 81 числа обидві цифри різні. Число 9, як кількість можливостей для вибору другої цифри, можна розглядати як інваріант цієї задачі. Розглянемо ще один клас задач, при розв’язуванні яких важливу роль відіграють інваріанти. Це задачі на ігри двох осіб. В кожній такій грі бере участь двоє. Вони роблять ходи почергово. В задачі вимагається встановити, у якого з гравців – того, що починає гру, чи його суперника, є виграшна стратегія і в чому вона полягає. Повний перебір усіх можливих ходів та ходів відповідей, як правило, здійснити не вдається. Тому при розв’язуванні таких задач доводиться шукати деяку властивість – інваріант, на основі якої можна побудувати виграшну стратегію. Задача 18. Двоє по черзі розламують шоколадну плитку 68. За один хід дозволяється зробити прямолінійний розлом будь-якого із шматків вздовж заглиблення. Програє той, хто не зможе зробити наступного ходу. У котрого з гравців є виграшна стратегія? Розв’язання: При кожному розламуванні кількість шматків збільшується на 1. Спочатку був 1 шматок. В кінці гри, коли не можна зробити уже жодного ходу, таких шматків 48. Отже, гра триватиме рівно 47 ходів. Оскільки при цьому кожний непарний хід робить гравець, який розпочинає гру, то він же зробить і останній 47-й хід. Тому перший гравець переможе, незалежно від того, як буде грати він сам та його суперник. Таким чином, число 47 виявилося інваріантом даної задачі. Задача 19. На дошці записане рівняння х3 + ___ х2 + ___ х +___ = 0. Два учні по черзі вписують на вільних місцях цілі числа – коефіцієнти рівняння. Довести, що починаючи гру може досягти того, щоб усі корені рівняння були цілими числами. Розв’язання: Для перемоги першому гравцю слід записати перед х число –1. Тоді, де і яке б число не записав його суперник, перший гравець на останньому вільному місці записує протилежне по знаку число. В результаті рівняння набуде такого загального вигляду: х³ + ах² – х – а = 0. Розкладаючи його ліву частину на множники, дістанемо: (х + а)(х² –1) = 0. Звідси х = –а, х= 1, х = –1. Отже, всі одержані корені є цілими числами. Задача 20. Гра починається з числа 7. За один хід дозволяється додати до наявного числа довільне, менше від нього натуральне число. Грають двоє, роблячи ходи позачергово. Виграє той, хто дістане число 1997. У котрого з гравців є виграшна стратегія? Розв’язання: Проаналізуємо задачу з кінця. 1997 – виграшна позиція. Із позицій 999-1996 її можна досягнути за один хід. Тому всі ці позиції програшні. Із позиції 998 всі ходи ведуть у програшну позицію, тому 998 – виграшна позиція. Аналогічно встановлюємо: позиції 500-997 – програшні, 499 – виграшна, 250-498 – програшні, 249 – виграшна, 125-248 – програшні, 124 – виграшна, 63-123 – програшні, 62 – виграшна, 32-61 – програшні, 31 – виграшна, 16-30 – програшні, 15 – виграшна, 8-14 – програшні , і, нарешті, 7 – виграшна позиція. Отже, перемогу здобуде другий гравець, якщо своїми ходами послідовно займатиме такі виграшні позиції: 15, 31, 62, 124, 249, 499, 998, 1997. Широкий спектр інваріантів зустрічаємо в геометрії: сума кутів трикутника; величина вписаних кутів, що спираються на одну дугу; суми протилежних кутів у вписаному чотирикутнику; суми довжин протилежних сторін в описаному чотирикутнику; теорема Піфагора, теореми про точки перетину висот, медіан, бісектрис трикутника тощо. Бажаємо творчої наснаги й подальших успіхів у розв’язуванні задач з цієї теми.

Схожі: