Використання принципу Діріхле в олімпіадних завданнях з математики

1. Принцип Діріхле

Німецький математик Петер Лежен Діріхле у своїх наукових працях часто користувався міркуваннями, які зараз називають принципом Діріхле.

Знайомство із цим принципом можна розпочати із задачі: «Чи можна розмістити 5 кроликів у чотирьох клітках так, щоб у жодній з кліток не містилося більше одного кролика?»

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

В загальному випадку принцип Діріхле можна сформулювати так:

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

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

Розв’язання

Туристи утворюють 30–20+1=11 вікових груп.

Тому є 11 груп (кліток) і 12 туристів (кроликів). Оскільки 12>11, то принаймні в одній віковій групі знайдеться два туристи, які є однолітками.

Приклад 2. На 5 поличках розміщено 160 книг, причому на одній із них - 3 книги.

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

Розв’язання

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

Приклад 3. У школі навчається 400 учнів. Доведіть, що хоча б двоє з них народилися в один день.

Розв’язання

Роль кроликів у цій задачі відіграють учні, а роль кліток – дні. За умовою задачі маємо 400 учнів і 365 днів.

Оскільки 400 > 365, то принаймні знайдеться два учні, що народилися в один день.

Приклад 4. Хлопчик мав 100 табличок з числами 1, 2, 3, …, 100, але загубив 79 з них. Чи обов’язково серед решти табличок знайдуться чотири такі, що сума чисел на двох із них дорівнюватиме сумі чисел на двох інших?

Розв’язання

У хлопчика залишилася 100 – 79 =21 табличка. Із цих табличок можна утворити: різних пар. (Кроликами є пари, а клітками – суми).

Оскільки усі пари з чисел 1, 2, …, 100 дають 197 різних сум – від 3 до 199 і 197 < 210, то принаймні у двох парах із 210-ти суми співпадатимуть. Отже, серед табличок знайдеться чотири такі, що сума чисел на двох із них дорівнюватиме сумі чисел на двох інших.

Приклад 5. Доведіть, що серед будь-яких шести цілих чисел знайдеться два числа, різниця яких буде кратна 5.

Розв’язання

При діленні на число 5 можна отримати п’ять різних остач: 0, 1, 2, 3, 4.

Шість чисел при діленні на 5 дають шість остач, серед яких може бути найбільше п’ять різних. Оскільки 6 > 5, то серед остач знайдеться дві однакові. Різниця чисел, що дають однакові остачі при діленні на 5, буде кратна 5.

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

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

(Оскільки 100 >15, і 100 можна представити

100 = 15 6 + 10, то принаймні двоє з хлопчиків зберуть однакову кількість грибів. Якби вони всі зібрали б різну кількість, то грибів було б 120 ≠ 100).

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

(З 10 друзів утворити можна 45 пар: 1+2+3+4+5+6+7+8+9=45, а листівок всього 5 і 50>45, тому принаймні двоє надіслали листівки один одному).

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

(Кульки є двох кольорів, тому взяти потрібно 3 кульки. У цьому випадку роль кроликів відіграють кульки, а роль кліток - кольори).

4. На кожній клітинці дошки 5х5 сидить жук. За командою жуки переповзають на сусідні клітинки. Клітинки вважаються сусідніми, якщо вони мають спільну сторону. Довести, що після того, як усі жуки переповзуть, знайдеться клітинка, на якій сидітимуть принаймні два жуки.

(На шахівниці 5х5 є 25 клітинок, серед яких 12 білих і 13 чорних. Оскільки жуки переповзають на сусідні клітинки, тоді на білі клітинки мають переповзти чорні жуки. Але 13 >12, тому на одній білій клітинці сидітиме щонайменше два чорних жуки).

5. У сьомому класі навчається 30 учнів. У диктанті один учень припустився 12 помилок, а решта – менше. Довести, що принаймні троє учнів припустились однакової кількості помилок.

(Оскільки помилок може бути 0, 1, 2, 3, …, 12 і якщо кожну кількість помилок допустили б тільки два учні, то всього учнів було б 2+1=25, але їх 30. 30>25, тому принаймні троє учнів припустились однакової  кількості помилок).

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

(Однаковими цифрами записуються двоцифрові числа, кратні 11. Остачі від ділення на 11 можуть дорівнювати: 0, 1, 2, 3, …, 10, тобто їх 11. Але 12>11, тому хоча б два числа дають однакові остачі. Це значить, що різниця цих чисел ділиться на 11 і є двоцифровим числом, записаним однаковими цифрами).

7. У квадраті зі стороною 1 взяли  51 точку. Довести, що деякі три із цих точок можна накрити квадратом зі стороною 0,2.

(Розіб’ємо квадрат площею 1 на 25 маленьких квадратиків. Площа кожного з них дорівнює 0,04, а сторона – 0,2. Оскільки 2 ·25+1=51, то це значить, що в один квадратик попаде принаймні три точки).

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

         (Роль кроликів відіграють жителі, а роль кліток - усі можливі варіанти кількості волосин на голові.

Оскільки в кожної людини менш ніж 200000 волосин на голові, то це значить, що кількість волосин може бути від  0  до   199999. Тому існує всього  200000  варіантів, а 40 ·200000 = 8000000, і згідно з принципом Діріхле знайдеться принаймні 41 житель, що має однакову кількість волосин на голові).

9. Доведіть, що в будь – якій компанії із 5 чоловік знайдеться двоє, які мають однакову кількість знайомих у цій компанії.

(Число знайомих може бути: 0,1,2,3,4. Якщо у когось четверо знайомих, то ні в кого не може бути 0 знайомих).