ВсОШ 2024, региональный этап, 9, 11 классы, задача 9
( баллов) Правильный треугольник со стороной разбит прямыми, параллельными его сторонам, на правильные треугольники со стороной . Все вершины этих треугольников, кроме центра треугольника , отмечены. Назовём множество из нескольких отмеченных точек линейным, если все эти точки лежат на одной прямой, параллельной стороне . Сколько существует способов разбить все отмеченные точки на линейных множеств? (Способы, отличающиеся порядком множеств, считаются одинаковыми.)
(И. Богданов)
Ответ
Ответ. .
Решение. Рассмотрим равносторонний треугольник со стороной , разобьём его на правильные треугольнички со стороной и отметим все вершины этих треугольничков; полученную конструкцию назовём -треугольником. В дальнейшем под прямыми мы всегда будем понимать прямые, параллельные сторонам этого треугольника и проходящие через хотя бы одну отмеченную точку.
Лемма. Пусть — отмеченная точка в -треугольнике. Тогда существует единственный способ провести прямых так, что все отмеченные точки, кроме, возможно, , покрыты этими прямыми. А именно, для каждой стороны -треугольника надо провести все прямые, параллельные ей и лежащие между этой стороной и точкой (включая саму сторону, но исключая прямую, содержащую , см. рис. ).
Доказательство. Индукция по . База при проверяется легко: надо провести прямую, содержащую две оставшихся точки, кроме .
Для перехода рассмотрим сторону -треугольника, на которой не лежит . Если прямая, содержащая эту сторону, не проведена, то все отмеченных точек на этой прямой должны быть покрыты различными прямыми; это невозможно, так как прямых . Значит, эта прямая проведена. Выкинув её и точки -треугольника, лежащие на ней, получаем -треугольник, в котором проведено прямых с теми же условиями. Осталось применить предположение индукции.
Перейдём к задаче. Рассмотрим одно из разбиений на линейные множества. Для каждого множества проведём прямую, его содержащую. Тогда эти прямые покрыли все отмеченные точки -треугольника, кроме, возможно, его центра . Значит, эти прямые устроены так, как описано в лемме, и для любого разбиения этот набор прямых один и тот же.
Заметим, что наш -треугольник разбился на областей: три «ромба» в углах, состоящих из точек, покрытых нашими прямыми дважды, и три «трапеции» у сторон, в которых каждая точка покрыты одной прямой (см. рис. ). Тогда каждая точка в «трапеции» относится к множеству, лежащему на этой прямой; каждую же точку в «ромбе» можно отнести к любому из двух множеств, лежащих на проходящих через неё прямых. Все такие выборы можно сделать независимо друг от друга. Поскольку в каждом из трёх «ромбов» всего точек, получаем, что требуемых разбиений ровно .
Замечание. Вариант доказательства леммы можно получить, показав сначала, что такое покрытие невозможно осуществить при помощи менее, чем прямых.