|
|
 |
Условие
Каждая сторона правильного треугольника разбита на n равных отрезков, и
через все точки деления проведены прямые, параллельные сторонам. Данный
треугольник разбился на n² маленьких треугольников-клеток.
Треугольники, расположенные между двумя соседними параллельными прямыми,
образуют полоску.
а) Какое наибольшее число клеток можно отметить, чтобы никакие
две отмеченные клетки не принадлежали одной полоске ни по одному из трёх
направлений, если n = 10?
б) Тот же вопрос для n = 9.
Решение
а) Примеры показаны на рисунках.
Второй способ. Пусть нам удалось отметить k клеток. Проведём через каждую отмеченную клетку все три полоски, в которых она лежит, и подсчитаем общее количество M попавших в эти полоски клеток (если клетка попадает в несколько полосок, то будем считать ее с соответствующей кратностью).
С одной стороны, каждая из 30 возможных полосок участвует в подсчёте столько раз, сколько в ней отмеченных клеток (то есть не более одного раза). Все полоски, взятые по разу, покрывают треугольник трижды, следовательно, M ≤ 300.
С другой стороны, три полоски, проходящие через одну отмеченную клетку, “закрывают” (с учетом кратности) не менее 39 клеток. (Действительно, если отмеченная клетка находится в левой вершине треугольника, то соответствующие полоски закрывают 19 + 19 + 1 = 39 клеток. При сдвиге отмеченной клетки вправо в соседнюю клетку, одна из полосок удлиняется на 2, а две другие не меняются; при следующем сдвиге одна из полосок сокращается на 2 и т. д. Поскольку сдвигами, параллельными сторонам треугольника, можно попасть в любую клетку, то количество клеток, закрытых соответствующими тремя полосками, всегда будет равно 39 для треугольничков, расположенных остриём вверх, и 41 для треугольничков, расположенных остриём вниз). Поэтому полоски, соответствующие всем отмеченным клеткам, закрывают не менее 39k клеток, то есть M ≥ 39k.
Итак, 39k ≤ 300, то есть k ≤ 7.
б) Примеры получаются из примеров к пункту а) отрезанием нижней полоски.
Оценка. Первый способ. Пусть нам удалось с соблюдением условий отметить некоторое количество клеток. При этом только одна из клеток, обозначенных на рисунке черными точками, может быть отмечена. В силу симметричности их расположения можно считать, что нижняя из этих клеток не отмечена. Разрежем оставшуюся часть треугольника на четыре куска (см. рис.).
Второй способ. Повторив рассуждения второго способа пункта а), получим неравенство 35k ≤ 243, откуда k ≤ 6.
Ответ
а) 7; б) 6 клеток.
Замечания
1. Первый способ оценки переносится на случай разбиения на n² треугольников, но приводит к завышенной оценке k ≤ 3n/4 для чётного n и к чуть лучшей оценке k ≤ 3n–1/4 для нечётного n. Эти оценки не точны даже для "маленьких" n (например, для n = 8, 11). Второй способ приводит к еще более завышенной оценке k ≤ 3n²/4n–1 Правильный же ответ [2n+1/3]. Докажем это.
Пример. Заметим, что достаточно привести пример только для чисел n вида 3m + 1 (при этом ответ 2m + 1), ибо он годится и для n = 3m + 2 (ответ тоже 2m + 1), а пример для n = 3m (ответ 2m) получается из него отрезанием нижней полоски.
Итак, пусть n = 3m + 1. На основании большого треугольника возьмём (m+1)-й (считая слева) треугольник, расположенный остриём вверх; отметим его. В этой же вертикали отметим и все остальные треугольники, ориентированные так же. Всего в этой вертикали будет отмечен m + 1 треугольник. На второй горизонтали большого треугольника возьмём (2m+1)-й (считая слева) треугольник, расположенный остриём вверх; отметим его. В этой же вертикали отметим и все остальные треугольники, ориентированные так же. Всего в этой вертикали отмечено n – 1 – 2m треугольников. Очевидно, что расположение всех отмеченных треугольников удовлетворяет требованиям задачи (в случае m = 3 получается правый рисунок пункта а); в случае m = 1 второй столбик отсутствует). Их число равно m + 1 + n – 1 – 2m = n – m = n – m = 2m + 1.
Оценка. Пронумеруем полоски треугольников, параллельные каждой стороне. Полоска, прилегающая к стороне, будет иметь номер 1, следующая за ней – номер 2 и т. д., последняя полоска, состоящая из одного треугольника, примыкающего к вершине исходного большого треугольника, имеет номер n. Таким образом, положение каждого треугольника задаётся тройкой чисел – номеров полосок, в которых он лежит. Эти координаты не могут принимать произвольные значения. Сумма всех координат каждого треугольника равна n + 2, если он расположен остриём вверх, и n + 1 в противном случае.
Предположим, мы отметили k треугольников так, что выполняются требования задачи. Оценим сумму S координат всех отмеченных треугольников двумя способами. С одной стороны, сумма координат каждого треугольника не превышает n + 2, поэтому S ≤ k(n + 2).
С другой стороны, сумма всех координат по всем отмеченным треугольникам не меньше чем 3(1 + 2 + ... + k) = ½·3k(k + 1)).
Из полученных оценок следует, что 3k(k + 1) ≤ k(n + 2), то есть k ≤ 2n+1/3.
2. Баллы: 7 + 7
