Условие
Можно ли разрезать правильный треугольник на 1000000 выпуклых
многоугольников так, чтобы любая прямая имела общие точки не
более чем с 40 из них?
Решение
Если провести разрезы, близкие к вершинам выпуклого
n-угольника, то можно отсечь от него
n треугольников и
получить выпуклый 2
n-угольник. Легко проверить, что при этом
любая прямая пересекает не более двух отсеченных треугольников.
Отсечем от правильного треугольника 3 треугольника, затем от
полученного шестиугольника — 6 треугольников и так далее, до
тех пор, пока не получим
3
. 2
19-угольник. Любая прямая
может пересечь не более двух треугольников, отсекаемых на каждом
шаге. Поэтому всего прямая может пересечь не более
1 + 2
. 19 = 39 многоугольников. Общее число многоугольников, на которые
разбит правильный треугольник, равно
1 + 3 + 3
. 2 + ... + 3
. 2
18 = 1 + 3(2
19 - 1) > 2
20 = (2
10)
2 > 1000
2. Ясно, что
можно отсекать не все треугольники, чтобы получить ровно 1000000
многоугольников.
Источники и прецеденты использования
