Задача 78687

Темы:    [ Свойства частей, полученных при разрезаниях ] [ Выпуклые многоугольники ] [ Принцип Дирихле (конечное число точек, прямых и т. д.) ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 4+ Классы: 8,9,10

Условие

Правильный треугольник ABC разбит на N выпуклых многоугольников так, что каждая прямая пересекает не более 40 из них (мы говорим, что прямая пересекает многоугольник, если они имеют общую точку, например, если прямая проходит через вершину многоугольника). Может ли быть N больше миллиона?

Решение

Если провести разрезы, близкие к вершинам выпуклого n-угольника, то можно отсечь от него n треугольников и получить выпуклый 2n-угольник. Легко проверить, что при этом любая прямая пересекает не более двух отсечённых треугольников. Отсечём от правильного треугольника 3 треугольника, затем от полученного шестиугольника — 6 треугольников и так далее, до тех пор, пока не получим 3 ^. 2¹⁹-угольник. Любая прямая может пересечь не более двух треугольников, отсекаемых на каждом шаге. Поэтому всего прямая может пересечь не более 1 + 2 ^. 19 = 39 многоугольников. Общее число многоугольников, на которые разбит правильный треугольник, равно 1 + 3 + 3 ^. 2 + ... + 3 ^. 2¹⁸ = 1 + 3(2¹⁹ - 1) > 2²⁰ = (2¹⁰)² > 1000². Ясно, что можно отсекать не все треугольники, чтобы получить ровно 1000000 многоугольников.

Ответ

Да.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	31
Год	1968
вариант
	1
Класс	10
Тур	2
задача
Номер	4