Приклад 2. «Якщо n кроликів сидять в k ящиках, то знайдеться ящик, в якому сидять не менше ніж

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

Твердження «серед 13 осіб знайдуться двоє, які народилися в один місяць» здається очевидним. Його можна довести різними способами, але більш грамотним буде спосіб – доведення від супротивного. Це виглядатиме так:

«Припустимо, що не знайдеться двох таких осіб. Тоді в кожний із 12 місяців народилося не більше однієї людини. Значить, є всього не більше 12 осіб, що суперечить умові задачі: 12 <13.»

Такі міркування дуже часто зустрічаються при розв’язуванні задач, тому їх виділили в окреме твердження, зване принципом Діріхле.

Класичне формулювання звучить так:

«Якщо (n + 1) кроликів сидять в n ящиках, то знайдеться ящик, в якому сидить, принаймні, два кролика».

Доведення цього твердження також будується від протилежного:

Розв’язування задач за допомогою принципу Діріхле зводиться до вибору «кроликів» і «кліток

Приклад 1.

Доведіть, що ніяка пряма не може перетинати всі три сторони трикутника.

Розв’язання: Пряма ділить площину на дві напівплощини, які ми назвемо «клітинами». Три вершини трикутника назвемо «кроликами». За принципом Діріхле, «знайдеться клітка, в якій сидить принаймні два кролика», тобто знайдуться дві вершини, що лежать в одній півплощині відносно даної прямої. Сторона, що з'єднує ці вершини, не перетинає дану пряму.

Приклад 2.

Грані куба пофарбовані в 2 кольори. Доведіть, що знайдуться дві сусідні одноколірні грані.

Розв’язання: Розглянемо три грані куба, що мають загальну вершину. Назвемо їх «кроликами», а дані кольору - «клітинами». За принципом Діріхле, знайдуться дві грані, пофарбовані в один колір. Вони і будуть сусідніми.

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

«Якщо n кроликів сидять в k ящиках, то знайдеться ящик, в якому сидять не менше ніж кроликів».