Принцип Діріхле в задачах

 ,

то число

х^п + у^п

дає при діленні на п² ту ж саму остачу, що й . Але кількість різних сум виду не перевищує кількості невпорядкованих пар виду

{},

де , тобто не перевищує числа

 

яке дорівнює

 

Значить і кількість різних залишків, які одержуються від ділення х^п + у^п на  n² не перевищує

 

Оскільки

<,

то серед чисел

0,1,.... n² -1

знайдеться хоча б одне число r, яке не є залишком від ділення х^п + у^п на п² ні при яких цілих х та у. Це число r і є шуканим.

Задача 36. Нехай а та b - фіксовані натуральні числа. Довести, що для довільного натурального числя х₀ серед членів рекурентної послідовності (х_п),

х_п =

є нескінченна кількість складених чисел.

Розв'язання. Твердження задачі 17 є очевидним у випадку, коли числа а та b не є взаємно простими. Тому вважатимемо далі, що числа а та b є взаємно простими. Тоді з різностей

b= х_п

одержуємо, що числа а та х_п є взаємно простими при будь-якому п 1. Зрозуміло, що послідовність (х_п) є монотонно зростаючою і всі члени, починаючи з першого, є більшими за .

Позначимо довільне число  через N і доведемо, що серед членів

 

обов'язково знайдеться складене число. Розділимо з остачею кожне з цих чисел на N. Оскільки чисел є

N +1, а можливих різних остач - N, то  деякі два з цих цих чисел х_p та x_q, р > q. дають однакові остачі при діленні на N, а тому їхня різниця х_р — х_q ділиться на N. Але

х_р -х_q - (x_p-1 + b) - (ах_q-1 + b) =

і, оскільки числа та N є взаємно простими, то .

Продовжуючи цей процес далі ми кінець-кінцем одержимо, що число

 

також ділиться на N. Але = N, тому

,

оскільки

> N.

 то число

 

є складеним. Таким чином, серед чисел

є принаймі одне складене число. Взявши тепер замість N число

 

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

Задача 37. Вісім команд провели круговий турнір з волейболу, тобто кожна команда зіграла з будь-якою іншою одну гру (результатом гри є виграш однієї з команд).Довести, що з цих команд можна вибрати чотири команди А,В,С,D так, що А виграла в В, С, D; В виграла в С, D; i С - виграла в D.

Розв'язання. Кожна з команд зіграла по сім матчів. За принципом Діріхле є принаймні одна з команд, яка виграла 4 матчі або більше. Позначимо цю команду А і розглянемо ті чотири команди, у яких виграла А. Між собою вони зіграли по три матчі, тому одна з цих чотирьох команд, назвемо її В, виграла принаймні в двох інших. З цих двох інших одна (С) виграла в іншої (D). Четвірка команд А,В,С, D є шуканою.

Задача 38. Сім учнів займаються в чотирьох гуртках. Доведіть, що знайдуться два школярі А та B такі, що всі гуртки, які відвідує А, відвідує також і В.

Розв'язання. Занумеруємо гуртки числами від 1 до 4. Тоді кожному учню відповідає деяка множина гуртків, яку він відвідує, тобто деяка підмножина множини {1,2,3,4}, розіб'ємо всі підмножини цієї множини на 6 класів:

,{1},{1,2},{1,2,3},{1,2,3,4},

2){2},{2,4},{1,2,4},

3){3},{1,3},{1,3,4},

4) {4},{3,4},{2,3,4}, 

5){2,3},

6)

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

Задача 39. Деяка комісія засідала 40 разів. Кожного разу в засіданні брали участь 10 чоловік, причому будь-які двоє членів комісії засідали спільно не більше одного разу. Довести, до комісії входить не менше 61 чоловіка.

Розв'язання. Нехай до комісії входить п людей. З кожних 10-ти людей, які брали участь в одному засіданні, можна утворити різних пар членів комісії. За умовою задачі різним засіданням відповідають різні пари людей. Тому за принципом Діріхле

 

Розв'язавши цю нерівність і  врахувавши, що п - натуральне число, одержуємо, що п 61.

Задача 40. 10 друзів відправили один одному листівки з поздоровленнями, причому кожен відправив 5 листівок. Довести, що принаймні двоє друзів відправили листівки один одному.

Розв'язання. Оскільки всього було відправлено 50 листівок, а кількість пар друзів = 45, то за принципом Діріхле твердження задачі є правильним.

Задача 41. Множина X складається з шести різних елементів. Нехай

 

- такі підмножини X, що кожна з них містить по три різні елементи. Доведіть, що існує "пофарбування" елементів в два кольори (тобто кожному елементу ставиться у відповідність один з двох кольорів) таке, що в кожній множині,.будe, принаймні два різнокольорові  елементи.

Розв'язання. Всього у множини різних трьохелементних підмножин. Розіб'ємо ці множини на 10 пар, віднести до однієї пари трьохелементну множину А та її доповнення Х\А. З принципом Діріхле існує трьохелементна множина В така, що ні В ні Х\В не співпадають з жодною з множин

.

Пофарбувавши елементи множини В одним кольором, а Х\В - іншим кольором, ми одержимо потрібне розфарбовування.

Задача 42. Площину розфарбували в а) 2, б) в п кольорів. Доведіть, що знайдеться прямокутник, вершини якого розфарбовані одним кольором.

Розв'язання. а) Розглянемо точки, які знаходяться на перетині деяких трьох горизонтальних і дев'ятьох вертикальних прямих. Вертикальні трійки точок можуть бути розфарбовані одним з 2³ = 8 способів. Тому серед дев'яти вертикальних трійок деякі дві розфарбовані однаково (одна з них отримується з іншої шляхом горизонтального зсуву). За принципом Діріхле принаймні дві точки в кожній з цих трійок розфарбовані одним кольором. Твердження задачі доведено.

Зауваження. Для розв'язання задачі а) досить розглянути точки, які лежать на перетині трьох горизонтальних і семи вертикальних прямих (дивись розв'язання наступної задачі).

б) Розглянемо точки, які  знаходяться на перетині n + 1 горизонтальної і ⁿ⁺¹ + 1 вертикальних прямих. За принципом Діріхле знайдуться два стовпчики, один з яких отримується горизонтальним переміщенням з іншого. Цим стовпчикам належать 4 точки одного кольору, які розміщені у вершинах прямокутника.

Задача 43. Кожну клітинку прямокутної таблиці 7 х 211 розфарбовано одним з двох кольорів. Доведіть, що можна вибрати 4 стовпчики і 4 рядки, всі 16 клітинок перетину яких пофарбовано одним кольором.

Розв'язання. Зрозуміло, що в кожному із стовпців буде не менше чотирьох клітинок одного з двох кольорів. Тоді за принципом Діріхле в 106 стовпцях буде по чотири клітинки, які розфарбовані одним кольором (наприклад, першим).В кожному з цих стовпців чотири розфарбовані цим кольором клітки можна розмістити = 35 способами. За принципі Діріхле одержуємо щo в 4-х з цих 106 стовпців зафарбовані першим кольором клітинки будуть розміщені однаково. Тоді знайдені чотири рядки і чотири стовпці, які підходять через однаково розміщені клітинки, що розфарбовані першим кольором є шуканими.

Задача 44.В кожному з двох однакових правильних шістнадцятикутників відмічено по 7 вершин. Довести, що можна так накласти ці многокутники один на одного, щоб принаймні 4 відмічені вершини одного многокутника співпали з відміченими вершинами іншого многокутника.

Розв'язання. Всього є 16 різних способів накладань одного многокутника на інший. Кожна відмічена вершина першого многокутника може суміститися з однією з семи відмічених вершин другого многокутника. Тому є всього 7 х 7 = 49 способів суміщень відмічених верши. За принципом Діріхле деякому накладанню многокутників відповідає принаймні 4 суміщена відмічених вершин, що і доводить твердження задачі.

Задача 45.На площині є 100 точок загального положення. Розглянемо довільні 295 відрізків з кінцями в цих точках. Довести, що деякі два з проведених відрізків перетинаються у внутрішній точці.

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

х·180° = 180°(n 2) + 360°(100n),

звідки

х =198 п.

З рівності

3х + п = 2у

знаходимо, що

у = 297n.

 Оскільки п 3, то у 294, а допущенням у 295. Одержали суперечність.

Задача 46.Довести, що з будь-яких десяти двозначних чисел можна вибрати дві різні групи чисел так, щоб. суми чисел в обох групах були однаковими.

 Розв’язання. Кількість все можливих різних непорожніх груп, які можна утворити з десяти елементів, дорівнює 2¹⁰ -1 = 1023. Оскільки всі числа є двозначними, то для суми S  чисел в кожній групі виконуються нерівності: 10. Таким чином, 1023 натуральні числа знаходяться на відрізку . Тому деякі два з цих чисел є однаковими, тобто існують дві групи чисел з однаковими сумами.

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

Розв'язання. Розглянемо п'ять відрізків, які виходять з деякої фіксованої вершини А. За принципом Діріхле серед них існує три однокольорові відрізки. Нехай це будуть відрізки                           А₂, АА₃.

Не порушуючи загальності  вважатимемо  ці відрізки червоними. Якщо серед відрізків

 

є хоча б один червоний, то твердження задачі правильне. В протилежному випадку шуканим трикутником буде трикутник .

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

Задача 48. В деякій країні була проведена супердемокритизація в результаті якої було створено 61 партію, причому членами кожної партії є більше половини мешканців країни. Довести, що в цій країні можна вибрати парламент з п'яти осіб так, що ці парламентарі представлятимуть інтереси всіх партій (тобто, для кожної партії знайдеться член парламенту, якій буде також членом цієї партії).

Розв'язання. За принципом Діріхле існує громадянин, який є членом більше як половини наявних партій. Тому існує особа яка є членом 31 партії. Цілком аналогічно, існує особа , яка є членом більше половини з 30 партій, що залишилися, тобто є членом 16 інших партій. Далі існує особа яка є членом 8 з  14 партій, які залишилися. Нехай 0₄ - це особа, яка є членом 4 з 6 партій, що залишилися. Зрозуміло, що існує особа ка є членом останніх двох партії. Тоді  парламент, що утворений з осіб ,

Задача 49. На мужній фестиваль зібралося 6 музикантів. На кожному концерті частина музикантів виступає, а інші слухають їх, сидячи в залі. За яку найменшу кількість концертів кожен з шести музикантів зможе послухати із залу кожного з інших?

Розв'язання. Для довільних  двох музикантів А та В через (А; В) позначим впорядковану пару, яка відповідає деякому концерту, причому на цьому концерті А - виступав (можливо, з іншими музикантами), а В - слухав у залі (можливо, з інтими музикантами). Всього є 6·5 =30 впорядкованих пар музикантів. На одному концерті реалізується щонайбільше таких впорядкованих пар. Тому за принципом Діріхле реалізації усіх 30 впорядкованих пар потрібно не менше чотирьох концертів. Легко організувати 4 концерти, які б реалізували всі 30 впорядкованих пар. Нехай

 

це занумеровані музиканти, а - це набір музикантів, які виступають на і- му концерті

 і = 1,2,3,4. Для закінчення розв'язання задачі досить покласти

 

Задача 50. Нехай

            (9)

є деякими підмножинами скінченної множини X. Довести наступні твердження:

а) Якщо переріз довільних двох множин набору (1) непорожній і п менше за половину кількості всіх підмножин множини X, то знайдеться підмножина множини X, яка відмінна від усіх множин (9) і переріз якої з кожною множиною з набору (9) є непорожньою множиною.

б)Якщо переріз довільних трьох множин сукупності (1) є непорожнім і п дорівнює половині кількості всіх підмножин множини X, то переріз усіх множин (9) є непорожньою множиною.

Доведення а). Розіб'ємо всі підмножини множини X на пари, віднісши до однієї пари множину та її доповнення в X. Таким чином в нас утворилася множина пар виду {В, Х\В},В X, і кількість різних таких пар дорівнює половині кількості усіх підмножин множини X. За принципом Діріхле існує пара множин {А, Х\А} така, що ні А ні  Х\А не містяться серед множин набору (9). Тоді одна з множин А або Х\А є шуканою. Дійсно, якби це було не так, то існували б різні множини та   з набору (9), для яких одночасно

 

Тому

Х\А) і ,

а значить , що суперечить умові.

б) Оскільки рівно воловина підмножин множини X знаходиться серед множин набору (9) і переріз будь-яких двох множин з (9) є непорожньою множиною, то з кожної пари множин виду {В, X\В?}, де В X, одна з множин В або Х\В входить до набору (9), а інша - ні. А тоді для довільних двох різних множин та , з набору (9) їхній переріз , також є деякою множиною з набору (9), бо в протилежному випадку такою множиною була б множина , і за умовою ми одержали б, що множина не є порожньою, що не так. Послідовно використовуючи той факт,, що переріз будь-яких двох множин з (9) належить до (9) одержуємо, що множина

 

такок входить в сукупність (9), а значить не є порожньою множиною. 

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

Задача 51. З чисел 1,2,3,4,5,6,7,8,9 довільним чином вибрано 6 чисел. Довести, що серед вибраних чисел є три числа, одне з яких є середнім арифметичним двох інших. Чи буде правильним це твердження для вибірки з 5-ти чисел?