ПРИНЦИП ДІРІХЛЕ

"Часто у боротьбі нового зі старим 

перемагає добре забуте старе.» 

Андрій Коваль.

ПРИНЦИП ДІРІХЛЕ

Цей принцип формулюється так: "Якщо п'ятьох зайців розсадити в чо­тири клітки, то принаймні в одній із них опиниться два зайці".

В україномовній математичній літературі цей принцип називають принципом Діріхле на честь відомого німецького математика Петера Лежена Дірі­хле, який перший із допомогою такого простого твердження отримав глибокі результати про наближення ірраціональних чисел раціональни­ми (в англомовній літературі цей принцип більше відомий як ріgеоn ргіnсіріе — "принцип голубів")/ Зауважимо, що задачі цієї розділу не претендують на оригінальність, більшість із них уже стала математич­ним "фольклором", і вже зараз складно встановити їх авторів.

Розгляньмо кілька елементарних задач.

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

Розв'язання. Зрозуміло, що узявши три кульки, ми виявимо, що дві з них одного кольору. У даному випадку роль зайців відіграють кульки, а роль кліток — чорний та білий кольори.

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

Доведення. Припустімо, що в лісі всі ялинки мають різну кількість голок (на деякій ялинці голок могло не бути зовсім). Тоді в лісі не більше ніж 800 001 ялинка, що суперечить умові. Тут у ролі зай­ців були ялинки, а в ролі кліток — усі можливі варіанти кількості голок на них.

3. На 5 поличках книжкової шафи 160 книг, причому на одній із них — 3 книги. Доведіть, що знайдеться поличка, на якій не менше ніж 40 книг.

Доведення. Припустімо, що на кожній із решти 4 поличок не більше ніж 39 книг. Тоді на всіх 5 поличках не більше ніж З + 4 • 39 = 159 книг, що суперечить умові. Отже, на одній із поличок не менше ніж 40 книг.

4. У місті більше ніж 8 мільйонів жителів. Науковці вважають, що в кож­ної людини менш ніж  200 000 волосин на голові. Доведіть, що є принаймні 41 житель з однаковою кількістю волосин
на голові.

Доведення. Оскільки 40-200000 = 8000000 (кількість волосин у людини коливається від  0  до   199 999,  всього  200 000  ва­ріантів), то,   згідно з принципом Діріхле знайдеться принаймні 41 житель, що має однакову кількість волосин на голові. Тут роль предметів відіграють жителі, а роль ящиків — усі мо­жливі варіанти кількості волосин на голові.

5. Дано два многочлени від однієї змінної, кожен із яких — сума 9 членів парного степеня, не більшого за 36. Доведіть, що в добутку обов'язково знайдуться три подібних члени.

Доведення. Якщо ми перемножимо два даних многочлени, то отримаємо новий многочлен степеня, не більшого за 72, кожний із 81 одночлена якого має парний степінь. Оскільки парних чисел від 0 по 72 є 37, то, згідно з принципом Діріхле, знайдуться принаймні три подіб­них члени.

6. Доведіть, що серед 82 кубиків, кожен із яких помальовано певним кольором, існує 10 кубиків різного кольору або 10 кубиків одного кольору.

Доведення. Якщо для розмалювання 82 кубиків використано не менше ніж 10 кольорів, то зрозуміло, що знайдеться 10 кубиків різного кольору. Якщо ж для розмалювання 82 кубиків використано не більше ніж 9 різних кольорів, то, згідно з принципом Діріхле, знайдеться при­наймні 10 кубиків одного кольору. Тут у ролі предметів виступають кубики, а в ролі ящиків — кольори.

7. Цифри 1, 2, ..., 9 розбили на три групи. Довести, що добуток цифр  в одній із груп не менший за 72.

Доведення. Оскільки

9! = 1 • 2·... • 9 = (8 • 9) • (З • 4 • 6) • (7 • 5 • 2) = 70 •72² = = (71²-1)(71 + 1)=71³ +71²-71-1>71³, то, згідно з принципом Діріхле, добуток цифр в одній із груп не мен­ший за 72.

8. 15 хлопчиків зібрали 100 грибів. Доведіть, що принаймні двоє з них зібрали однакову кількість.

Доведення. Припустімо, що твердження задачі неправильне. Тоді 15 хлопчиків зібрали щонайменше 0 + 1 + 2 + .. . + 14 = 14•15:2 = 105 грибів. Це суперечить умові.

Деколи буває корисним ще таке переформулювання принципу Діріхле:

Якщо одне з кількох чисел більше від їх середнього арифметич­ного, то серед цих чисел знайдеться інше, що є меншим від їх серед­нього арифметичного.

9. У бригаді 7, чоловік і їх сумарний вік складає 322 роки. Дове­діть, що з них можна вибрати трьох осіб, сумарний вік яких не менший за 138 років.

Доведення. Оскільки середній вік членів бригади складає 46 ро­ків, то сумарний вік трьох найстарших людей не менший за 3-46 = 138 років.

Принцип Діріхле можна також сформулювати зовсім "по-науко­вому", не використовуючи кліток і зайців.

Нехай А і В — скінчені множини, причому m — кількість еле­ментів множини А, а n — кількість елементів множини В (m> n). Тоді при будь-якому відображенні множини А в множину В знай­дуться два елементи множини А, що мають той самий образ.

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

Принцип Діріхле в геометрії

Принцип Діріхле для площ можна сформулювати у вигляді такої теореми:

Нехай А1,А2,...,Аn — многокутники або інші фігури, для яких  визначене поняття площі (див.: кн. "Кенгуру-99", Розглянемо площі елементарних фігур, причому А_і  А  (фігура А_і  міститься в А) для і = 1,..., n.

Відомо, що

S(A) < S(A₁)+ S(A₂)+ S(A₃)+…..+ S(A_n)

(тут S(A_s) –  площа фігури A_s).

Тоді принаймні дві з фігур А₁...,А_К мають спільні внутрішні точки. Нагадаймо, що точка X фігури А тоді називається внутріш­ньою, якщо існує такий кружечок із центром у точці X, який цілком належить фігурі А.

Принцип Діріхле для площ допускає також таке узагальнення:

Нехай А,А₁,А₂,...,Аn — фігури, для яких визначене поняття площі, причому А_і  А  для всіх і = 1,..., n. 

 Якщо

kS(A) < S(A₁)+ S(A₂)+ S(A₃)+…..+ S(A_n),

 то принаймні k +1 фігура з фігур А₁,А₂,...,А_n має спільну внутріш­ню точку.

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

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

1.         Доведіть, що рівносторонній трикутник не можна покрити
двома меншими за нього рівносторонніми трикутниками.

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

2.         На газоні у формі правильного трикутника зі стороною 3 м
росте 10 гвоздик. Доведіть, що знайдуться дві гвоздики, що знаходять­
ся одна від одної на відстані, що не перевищує 10 м.

Доведення. Розділімо газон на 9 рів-носторонніх трикутників зі стороною 1 м. Тоді, згідно з принципом Діріхле, принаймні дві точки містяться в одному з них. А тому відстань між цими точками не перевищує 1 м. Зауважмо, що після розміщення 10 гвоз­дик у вершинах розбиття усі відстані між ними дорівнюватимуть 1  м.

3. Доведіть, що в кожного многогранника знайдуться дш і рані і однаковою кількістю сторін.

Доведення. Нехай Г — грань, що містить найбільшу кільки и. сторін. Тоді даний многогранник має принаймні п +1 грань, причому кількість сторін на кожній із них змінюється від 3 до п. Тоді, згідно і принципом Діріхле, знайдуться дві грані з однаковою кількістю сторін.

4.П'ять точок А₁,А₂,...,А₅ лежать в одній площині, і їхні ко­ординати — цілі числа. Доведіть, що серед усіх трикутників із верши­нами в даних точках є принаймні три, площі яких виражаються цілими числами.

Доведення. Нехай А{х₁;у₁), В(х₂;у₂), С(х₃;у₃)—вершини деякого трикутника з цілими координатами. Зауважмо, що якщо одну і координат змінити на парне число, то площа відповідного трикутника зміниться на ціле число. Таким чином, замінивши координати точок А₁,А₂,...,А₅ числами 0 чи 1 залежно від їх парності, згідно з принци­пом Діріхле, деяким двом точкам відповідатимуть однакові координа­ти. Нехай це будуть точки Л, і А2. Тоді площі трикутників А₁А₂А_{3 ,} А₁А₂А₄, А₁А₂А₅ виражаються цілими числами.

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

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

6. На площині дано 25 точок, причому серед довільних 3 із них знайдуться 2 точки, відстань між якими менша від 1. Довели і.  що її нує круг, радіусом 1, що містить не менше ніж 13 з цих точок.

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

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

Доведення. Нехай n — кількість команд, що проводять турнір. Розгляньмо два випадки:

1)у даний момент турніру знайдеться команда, що не провела жодної гри;

2) протилежний.

Припустімо, що у випадку 1) така команда одна. Якби їх було дві, то все доведено. Тому у випадку 1) не буде жодної команди, що зіграла n-1 матч до даного моменту. Тоді, згідно з принципом Дірі­хле, серед n -1 команд (крім тієї, що не зіграла жодного матчу) можна вибрати дві, що зіграли однакову кількість матчів. Тут у ролі зайців виступають n-1 команд, а в ролі кліток — можливі кількості матчів від 1 до n-2, які вони зіграли. У випадку 2) кількість матчів, що провели команди до даного моменту, змінюється від 1 до n-1. І тому знову, за принципом Діріхле, серед n команд знайдуться дві, що зігра­ли однакову кількість матчів.

11.10 друзів відправили один одному святкові листівки. Кожний із них відправив 5 листівок. Доведіть, що якихось двоє друзів відправи­ли листівки один одному.

Доведення. Обчислімо, скільки всього пар людей можна утво­рити з 10 друзів:

10·9:2=45. Оскільки всього було відправлено  10 * 5 = 50  листівок, то, згідно з принципом Діріхле, на якусь пару друзів припадає дві листівки.

12.       У роботі якогось засідання брало участь 200 чоловік, причому кожен із них був знайомий не менше ніж зі 100 присутніми. Дове­діть, що за круглий стіл для 4 осіб можна посадити 4 з присутніх так, щоб кожен із них сидів між своїми знайомими.

Доведення. Припустімо, що серед присутніх є двоє незнайомих А і В, інакше все доведено. Оскільки кожен із А і В знайомий не менше ніж зі 100 присутніми, то вони матимуть принаймні двох спіль­них знайомих (200 > 198). Тоді ці двоє спільних знайомих разом з А і В утворюватимуть шукану четвірку осіб.

13.       У конгресі брало участь 2000 вчених, одні з них були раніше знайомі один з одним, інші — ні. При цьому виявилось: кожні двоє вчених,  які мають однакову кількість знайомих, не мають спільних зна­йомих. Доведіть, що серед присутніх на конгресі вчених знайдеться вчений, що знайомий лише з одним учасником конгресу.

Доведення. Нехай А — це вчений, який має найбільшу кіль­кість знайомих серед присутніх (або одного з них, якщо їх декілька). Усіх знайомих А позначимо А₁, А₂,..., Ак. Згідно з умовою задачі, усі Аі (і = 1,... ,к) мають різну кількість знайомих, що змінюється від 1 до к. Тоді знайдеться такий учений, що має рівно одного знайомого.

14.       Уздовж круглого столу рівномірно розміщено таблички з прізвищами дипломатів, які беруть участь у переговорах. Після почат­ку переговорів виявилось, що кожен із дипломатів не сидить напроти свої таблички. Чи можна повернути стіл так, щоб принаймні двоє дипломатів сиділи напроти своїх табличок?

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

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

15. Картки пронумеровані послідовно цілими числами від 1 до 2n +1. Яку найбільшу кількість карток можна вибрати так, щоб жоден з номерів не дорівнював сумі якихось двох інших номерів карток?

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

Легко перевірити, що для n+ 1 картки з непарними номерами {1,3,5,..., 2n +1} умови задачі вже виконуються.

Рівень А. ВПРАВИ НА ПРИНЦИП ДІРІХЛЕ

1. У мішку лежать 5 чорних і 5 білих кульок. Яку найменшу кількість кульок потрібно взяти з мішка, щоб серед них точно виявило­ся 3 кульки одного кольору?

2°. Учені дослідили, що кількість голок у їжака не перевищує 200 тисяч. Доведіть, що із 250 тисяч їжаків можна вибрати принаймні двох, що мають однакову кількість голок.

3°. У Верховну Раду обрано 336 народних депутатів, причому серед них 123 жінки, 245 — особи — представники правих сил. Дове­діть, що серед правих є не менше ніж 32 жінки.

4°. У школі 30 класів і 1000 учнів. Доведіть, що у школі є клас, у якому не менше ніж 34 учнів.

5°. На Землі більше ніж 4 мільярди людей, вік яких не переви­щує 100 років. Доведіть, що на Землі є двоє людей, що народилися тієї самої секунди.

6°. Яку найменшу кількість карток спортлото "6 із 49" потрібно купити, щоб на одній із них обов'язково було вгадано хоча б один но­мер?

7°. У магазин завезли 25 ящиків із трьома різними сортами яблук (у кожному ящику яблука лише одного сорту). Доведіть, що серед них є принаймні 9 ящиків одного сорту яблук.

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

9°. У темній коморі лежать черевики одного розміру: 10 пар чор­них і 10 пар коричневих. Яку найменшу кількість черевиків потрібно взяти з комори, щоб серед них точно можна було вибрати одну пару одного кольору (у темноті не можна відрізнити не тільки колір чере­вика, але й лівий від правого)?

10°. З повного набору доміно викинули всі кісточки з шістками. Чи можна викласти в ланцюг усі кісточки, що залишилися?

Рівень В. ВПРАВИ на принцип Діріхле

1°. 34 пасажири їдуть автобусом. Автобус робить 9  зупинок, причому на кожній із них нові пасажири не заходять. Доведіть, що знайдуться дві зупинки, на яких вийшла однакова кількість людей.

2°. Дано два многочлени від однієї змінної, кожний із них є су­мою 4 членів непарного степеня, меншого за 25. Чи обов'язково в до­бутку будуть два подібних члени?

3°. Чи можна так пронумерувати вершини куба натуральними числами від 1 до 8, щоб суми номерів на кінцях кожного ребра були різними?

4°. 45 школярів на олімпіаді розв'язали 175 задач, причому ві­домо, що серед них є школярі, які розв'язали лише одну, дві і три за­дачі. Доведіть, що серед них є школяр, який розв'язав не менше ніж 5 задач.

15°. У класі 30 учнів. Кожному подобається рівно к учнів цього класу.

 При якому найменшому к обов'язково знайдеться двоє учнів, які подобаються один одному?

6°. До ліфта вантажопідйомністю 320 кг підійшло 12 чоловік, загальною масою 960 кг. Доведіть, що з них можна підібрати 4 чолові­ки, які разом зможуть піднятися ліфтом.

7°. Чи можна вивезти з каменоломні 50 каменів, маси яких від­повідно дорівнюють 370,372,374,...,468 кг, на 7 трьохтонних маши­нах?

8°. На площині дано скінчену кількість точок. Доведіть, що як­що деякі з них з'єднати відрізками, то завжди знайдуться дві точки, із яких виходить однакова кількість відрізків.

9°. Дано n + 1 різних натуральних чисел, менших від 2п. Доведіть, що серед них можна вибрати таких три числа, що одне з них дорівнює сумі двох інших.

10°. Чи можна шаховим конем попасти з лівого нижнього кута шахової дошки у верхній правий, побувавши в кожному полі тільки один раз?

11°. Яку найменшу кількість полів на дошці 8x8 потрібно зама­лювати чорним кольором, щоб в кожному кутику, який має вигляд Д було принаймні одне чорне поле?