|
|
 |
Условие
В некоторых клетках квадрата 200×200 стоит по одной фишке – красной или синей; остальные клетки пусты. Одна фишка видит другую, если они находятся в одной строке или одном столбце. Известно, что каждая фишка видит ровно пять фишек другого цвета (и, возможно, некоторое количество фишек своего цвета). Найдите наибольшее возможное количество фишек.
Решение
Пример. Выделим у квадрата 200×200 "каёмку" ширины 5. Эта каёмка состоит из четырёх угловых квадратов 5×5 и четырёх прямоугольников 5×190. Поставим 3800 фишек в эти четыре прямоугольника: в левый и в верхний – красные, а в правый и в нижний – синие. Нетрудно видеть, что все требования выполнены.
Оценка. Рассмотрим произвольную расстановку фишек, удовлетворяющую требованиям. Назовём ряд (строку или столбец) разноцветным, если в нём есть фишки обоих цветов.
По условию каждая фишка видит какую-то фишку другого цвета, поэтому каждая фишка лежит хотя бы в одном разноцветном ряду. Кроме того, поскольку разноцветный ряд содержит красную фишку, в нём стоит не более пяти синих фишек. Аналогично в разноцветном ряду стоит не более пяти красных фишек, то есть всего не более 10 фишек.
Если есть 191 разноцветная строка, то в них не более 191·10 = 1910 фишек, а в оставшихся девяти строках не более 9·200 = 1800 фишек, итого не больше 1900 + 1800 = 3700 фишек. Аналогично в случае, когда есть 191 разноцветный столбец. Если же и тех и других не более чем по 190, то они содержат не более 190·10 + 190·10 = 3800 фишек, а все фишки содержатся в этих рядах.
Ответ
3800 фишек.
Замечания
Можно показать, что при любом n ≥ 30 наибольшее число фишек, которые можно разместить на доске n×n согласно условиям, равно 20(n – 10).
