Условие
Петя разрезал прямоугольный лист бумаги по прямой. Затем он разрезал по прямой один из получившихся кусков. Затем он проделал то же самое с одним из трёх получившихся кусков и т.д. Докажите, что после достаточного количества разрезаний можно будет выбрать среди получившихся кусков 100 многоугольников с одинаковым числом вершин (например, 100 треугольников или 100 четырёхугольников и т.д.).
Решение
При Петиных разрезаниях получаются только выпуклые многоугольники. При разрезании треугольника одна из частей тоже будет треугольником, поэтому число треугольников не уменьшается. Разрез может увеличить число сторон многоугольника только на 1, и при этом будет отрезан треугольник. Если мы увеличим число сторон 100 раз, то уже получим 100 треугольников. Иначе мы увеличили число сторон не более 99 раз, поэтому у каждого многоугольника не более 4+99=103 сторон. Значит, у нас есть не более 100 типов многоугольников. Но после того, как у нас станет 9901 часть, многоугольников какого-то типа станет по принципу Дирихле не менее 9901:100>99, то есть не менее 100.
Источники и прецеденты использования
