Question

В лесу растёт миллион ёлок. Известно, что на каждой из них не более чем 800000 иголок. Докажите, что в лесу найдутся две ёлки с одинаковым количеством иголок

Answer 1

Количество елок больше, чем количество игл на каждой из них. На одной елке может быть от 1 до 600000 игл. Для того, чтобы не было елок с одинаковым количеством игл, их должно быть 600000 штук.

А их миллион. Следовательно, наверняка есть две елки с одинаковым количеством игл.

Answer 2

Это задача, которая может быть решена с использованием принципа Дирихле (или принципа ящиков и шаров). Принцип Дирихле гласит, что если n объектов размещаются в более чем n контейнерах, то как минимум один из контейнеров будет содержать более одного объекта.

В данном случае, деревья в лесу - это контейнеры, а количество иголок на каждом дереве - это объекты. У нас есть миллион деревьев (контейнеров) и каждое дерево имеет не более 800,000 иголок (объектов). Если мы предположим, что все деревья имеют разное количество иголок, то это означает, что у нас есть миллион различных "контейнеров" и миллион различных "объектов", которые мы распределяем по этим контейнерам.

Однако, по принципу Дирихле, если мы размещаем миллион объектов в миллионе контейнерах (по одному объекту в каждом контейнере), то как минимум в одном контейнере должно быть больше одного объекта. Это означает, что как минимум на двух деревьях в лесу будет одинаковое количество иголок.

Таким образом, мы доказали, что в лесу найдутся как минимум два дерева с одинаковым количеством иголок.