Задача из журнала «Квант» (выпуск №2, 1998).

Условие

Каждая сторона правильного треугольника разбита на $n$ равных отрезков, и через все точки деления проведены прямые, параллельные сторонам. Данный треугольник разбился на $n^{2}$ маленьких треугольников-клеток. Треугольники, расположенные между двумя соседними параллельными, образуют полоску.
1. Какое наибольшее число клеток можно отметить, чтобы никакие две отмеченные клетки не принадлежали одной полоске ни по одному из трёх направлений, если $n=10$?
2. Тот же вопрос для $n=9$.

Решение

1. На рисунке 1 показан способ отметить 7 треугольников. Чтобы доказать, что при $n=10$ нельзя отметить 8 треугольников, разрежем исходный треугольник средними линиями на четыре треугольника. Каждый из них состоит из 25 треугольничков. Обозначим количества отмеченных треугольничков в угловых треугольниках буквами $k,l,m$, а в центральном — $n$. Тогда $k+l+n \leq 5$, поскольку два угловых треугольника вместе с центральным состоят из 5 полос. Аналогично,$l+m+n \leq 5$ и $m+k+n \leq 5$.
   Сложим эти три неравенства: $2k+2l+2m+3n \leq 15$. Следовательно, $k+l+m+n \leq \frac{1}{2} \cdot (2\cdot k+2\cdot l+2\cdot m+3\cdot n)\leq \frac{15}{2} < 8$.
2. Решим задачу для произвольного $n$. Рассмотрим одну из сторон исходного треугольника и пронумеруем полоски соответствующего направления следующим образом: полоска, прилегающая к стороне, пусть будет иметь номер 1; следующая за ней — номер 2;…; полоска, состоящая из одного треугольника, примыкающего к вершине исходного большого треугольника, получит номер $n$.
   Теперь положение любого из $n^{2}$ треугольничков можно задать тройкой чисел — номеров полосок, в которых он лежит.
   
   Уточнение о номерах полосок

   Тройки номеров являются дискретным аналогом барицентрических координат, при которых положение любой точки, лежащей внутри правильного треугольника, определяется расстояниями до трёх его сторон. Сумма этих расстояний, как легко проверить, равна высоте треугольника.

   [свернуть]
   
   Введённые нами тройки номеров = «координаты» треугольничков — не могут принимать произвольные значения. Их сумма равна $n+2$, если треугольничек расположен «остриём вверх» (т.е. ориентирован так же, как исходный большой треугольник), и равна $n+1$, если «остриём вниз».
   Предположим, отмечены $k$ треугольников, никакие два из которых не попали в одну полоску. Оценим сумму $S$ всех их координат двумя способами. С одной стороны, сумма координат любого треугольника не превышает $n+2$, поэтому $S\leq k\cdot (n+2)$. С другой стороны, сумма значений одной из координат по всем отмеченным треугольникам не меньше чем $1+2+3+\cdots +k=\frac{k\cdot (k+1)}{2}$. Значит, $3\cdot \frac{k\cdot (k+1)}{2}\leq S\leq k\cdot (n+2)$, откуда $3\cdot \frac{k+1}{2}\leq n+2$, т.е. $k+1\leq \frac{2\cdot n+4}{3}$. Итак, $k\leq \frac{2\cdot n+1}{3}\cdots$.
   Отметить $[\frac{2\cdot n+1}{3}]$ треугольничков можно следующим образом. Рассмотрим число $m=[\frac{n+1}{3}]$. На основании исходного треугольника отметим $(m+1)-й$ слева треугольничек, расположенный остриём вверх. В этой же вертикали отметим и все остальные треугольнички, ориентированные остриём вверх (рис.2).
   
   Всего в этой вертикали отмечено $(m+1)$ треугольничков. На второй горизонтальной полосе большого треугольника отметим $(2\cdot m+1)-й$ (считая слева) треугольничек, расположенный остриём вверх. Отметим и все остальные треугольнички этой вертикали, ориентированные остриём вверх. Всего в этой вертикали будет отмечено $n-1-2\cdot m$ треугольничков.
   Общее количество отмеченных треугольничков есть $m+1+n-1-2\cdot m=n-m=n-[\frac{n+1}{3}]=[\frac{2\cdot n+1}{3}]$.
   Чтобы проверить последнее равенство, достаточно разобрать три случая: $n$ равно $3\cdot a, 3\cdot a+1$ и $3\cdot a+2$.