Question

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

Answer 1

Елок больше, чем иголок на каждой из них. Чтобы не было елок с одинаковым количеством иголок их так же должно быть 600000. В нашем случае елок миллион, а это значит, что 2 елки с одинаковым количеством иголок наверняка найдутся. 

Answer 2

Для решения данной задачи воспользуемся принципом Дирихле.

Предположим, что в лесу есть миллион елок, и на каждой из них не более 600000 иголок. Рассмотрим количество возможных различных комбинаций иголок на этих елках. Максимальное количество различных комбинаций будет достигаться в случае, если на каждой елке будет по одной иголке, то есть 1, 2, 3, ..., 600000 иголок. В данном случае количество различных комбинаций будет равно сумме первых 600000 натуральных чисел:

1 + 2 + 3 + ... + 600000 = (600000 * 600001) / 2 = 180000300000

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

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