Узагальнений принцип Діріхле

Запитання  від математичного "духа" нашого математичного гуртка:

У конверті лежать вирізані із паперу квадрати, круги, трикутники – всього сім штук. Квадратів у три  рази більше, ніж трикутників. Скільки в конверті кружків і других фігур?

Відповідь: три квадрата, три круги, один трикутник.

Мотивація вивчення нових знань.

«Що  почуття  часто  заводять  нас  в  оману — це, звичайно, правда, але такий закид може бути адре­сований математикам менше, ніж   будь-кому. Адже саме математика передусім захищає нас від оманливості почуттів і навчає, що одна річ — як насправді влаштовані ті предмети, які сприймаються  почуття­ми,   а інша річ — якими   вони   здаються; ця наука дає найнадійніші правила, хто керується ними, того почуття не заведуть в оману.»

                                                      Л. Ейлер

Осмислення нових знань.

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

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

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

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

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

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

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

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} умови задачі вже виконуються.