M1635. О разбиении сторон правильного треугольника на $n$ равных отрезков.

Задача из журнала «Квант» (выпуск №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$.

M1635. О разбиении сторон правильного треугольника на $n$ равных отрезков.: 1 комментарий

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *