Задача 10. Слои треугольника

Множества превращаем в прямые

Отмеченные точки — это все вершины сетки, кроме центра $T$. На стороне $BC$ лежит $112$ вершин, всего вершин $\frac{112\cdot 113}{2}=6328$, отмеченных — $6327$. Центр $T$ является вершиной сетки именно потому, что $111$ делится на $3$.

Прямыми будем называть только прямые, параллельные сторонам $T$ и проходящие через отмеченные точки. У них три направления: параллельно $BC$, параллельно $CA$ и параллельно $AB$. В каждом направлении $112$ прямых: сама сторона, затем следующая «полка» сетки и так далее до противоположной вершины.

Пусть точки разбиты на $111$ линейных множеств. Для каждого множества проведём прямую, на которой оно лежит (если в множестве одна точка, возьмём любую прямую через неё). Получится не больше $111$ прямых, и вместе они накрывают все отмеченные точки: каждая точка лежит в своём множестве, а значит, и на его прямой.

Зачем это нужно: множеств может быть очень много, а наборы прямых, как сейчас увидим, устроены жёстко.

Сторону нельзя пропустить

Посмотрим на сторону $BC$. На ней $112$ отмеченных точек: центр на стороне не лежит. Прямая другого направления пересекает $BC$ ровно в одной точке, а прямая, параллельная $BC$ и не совпадающая с ней, не пересекает её вовсе. Значит, каждая прямая, кроме самой $BC$, накрывает на стороне $BC$ не больше одной точки.

Если прямой $BC$ среди наших прямых нет, то $112$ точек стороны накрыты «по одной», и прямых нужно не меньше $112$. А их не больше $111$ — противоречие. Поэтому прямая $BC$ обязательно есть среди наших прямых. Точно так же среди них обязательно есть прямые $CA$ и $AB$.

Как это увидеть в модели: при стороне $6$ выбери любые шесть прямых, не беря сторону $AB$, — на ней останутся ненакрытые точки, и модель назовёт, сколько именно и почему их нельзя добрать.

Снимаем слой за слоем

Три стороны накрывают ровно границу треугольника. Внутри остаются вершины, удалённые от каждой стороны хотя бы на один шаг сетки, — это снова правильный треугольник, только со стороной $111-3=108$, и его центр совпадает с центром $T$. На него осталось не больше $111-3=108$ прямых. Прямая, не проходящая ни через одну внутреннюю точку, ничего там не накрывает — такие прямые можно не считать.

Для внутреннего треугольника повторяем шаг 2: его сторона содержит $109$ отмеченных точек, любая другая прямая берёт с неё не больше одной, а прямых не больше $108$. Значит, все три стороны внутреннего треугольника тоже среди наших прямых. Снимаем и этот слой: остаётся треугольник со стороной $105$ и не больше $105$ прямых.

Так снимаем слой за слоем: стороны $111,\ 108,\ 105,\ \ldots,\ 3$. Слоёв $111:3=37$, в каждом три обязательные прямые — ровно $3\cdot 37=111$. Последний слой — треугольник со стороной $3$: его три стороны накрывают все его точки, кроме центра, а центр и не нужен.

Вывод: набор прямых один и тот же для любого разбиения — это $111$ сторон вложенных треугольников, и все эти прямые различны. Поэтому все $111$ множеств лежат на разных прямых: если бы два множества лежали на одной прямой, различных прямых было бы меньше $111$, а мы показали, что меньше нельзя. Каждому множеству соответствует своя прямая набора.

Какие точки можно отдать двум множествам

Теперь разбиение — это ответ на вопрос «к какой из $111$ прямых набора отнести каждую точку». Точка, лежащая только на одной прямой набора, выбора не даёт: она попадает в множество этой прямой. Точка на двух прямых набора может попасть в любое из двух множеств.

Какие точки лежат на двух прямых набора? Прямые набора — это $37$ ближайших к каждой стороне прямых: от самой стороны до $36$-й. Измерим расстояние от точки до стороны в «полках» сетки. Точка лежит на прямой набора, параллельной $BC$, если её расстояние до $BC$ не больше $36$; так же для $CA$ и $AB$. Три расстояния точки до сторон в сумме всегда равны $111$: это видно по вершине $A$ (расстояния $111$, $0$, $0$), а шаг сетки вдоль любой стороны увеличивает одно расстояние на $1$ и уменьшает другое на $1$.

Все три расстояния не больше $36$ быть не могут: сумма была бы не больше $108$. А два — могут: если расстояния до $BC$ и до $CA$ оба не больше $36$, то расстояние до $AB$ не меньше $111-72=39$. Такие точки заполняют «ромб» у вершины $C$: $37$ значений расстояния до $BC$ и $37$ значений расстояния до $CA$, всего $37^2=1369$ точек. У вершин $A$ и $B$ по такому же ромбу, итого точек на двух прямых $3\cdot 37^2=4107$. Остальные $6327-4107=2220$ точек лежат на одной прямой набора — это три «трапеции» вдоль сторон.

Считаем разбиения

У каждой из $4107$ точек ромбов два варианта, и варианты для разных точек выбираются независимо: выбор для одной точки не ограничивает выбор для другой. Значит, наборов выборов ровно $2^{4107}$.

Осталось убедиться, что каждый набор выборов даёт настоящее разбиение и разные наборы дают разные разбиения. На каждой прямой набора есть точки, не лежащие больше ни на одной прямой набора, и их хотя бы две: например, на $36$-й прямой от $BC$ это точки с расстояниями до $CA$ и $AB$, равными $37$ и $38$ или $38$ и $37$. Поэтому множество каждой прямой непусто, содержит не меньше двух точек и, конечно, линейно. Два разных набора выборов отличаются хотя бы в одной точке $X$: в одном разбиении $X$ лежит в множестве одной прямой, в другом — в множестве другой; эти множества не совпадают, потому что множество из двух и более точек лежит только на одной прямой.

Ответ: $2^{4107}$ способов.