Question

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

Answer 1

Ответ:

Нехай є восьмеро друзів, і вони поділили між собою 20 марок. Розглянемо кількість марок, яку отримав кожен з друзів. Якщо у кожного друзя буде різна кількість марок, то отримаємо 8 різних чисел.

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

Отже, ми маємо 8 друзів та не більше 19 можливих варіантів розподілу марок. Застосуємо принцип Дирихле, який стверджує, що якщо n+1 об'єктів розподілено між n контейнерами, то принаймні в одному контейнері буде як мінімум 2 об'єкти.

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

Отже, незалежно від того, як друзі поділили між собою 20 марок, якимось двом друзям дістанеться однакова кількість марок.

Answer 2

Розглянемо кожного друга окремо. Кожен друг може отримати від 0 до 20 марок. Якщо кожен друг отримає різну кількість марок, то це буде означати, що сума кількість марок у кожного друга буде різною і буде дорівнює від 0 до 20. Тобто можливі значення для Суми кількості марок у кожного друга: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20.

Але друзів всього вісім, а значить, якщо кожен з них отримає унікальну кількість марок, то сума всіх цих восьми значень буде дорівнює 0+1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20 = 210.

Тобто всі 20 марок будуть розділені між друзями в сумі на 210. Але 210 не ділиться на 8 без залишку, що означає, що кожен друг не може отримати унікальну кількість марок.

Отже, як би друзі не зробили, якимось двом друзям дістанеться однакова кількість марок.