ВсОШ 2025, 8 класс, задача 9
( баллов) Новая шахматная фигура гусь может ходить либо на одну клетку влево, либо на две клетки вправо и одну вверх, либо на две клетки вверх и одну вправо. Возможные ходы гуся, стоящего в клетке Г, отмечены на рисунке крестиками. Гусь бьёт так же, как и ходит.
Несколько гусей стоят в клетках доски так, что никакой гусь не бьёт другого гуся, при этом любая незанятая клетка бьётся хотя бы одним гусём. Сколько гусей может стоять на доске? Укажите все возможные варианты в любом порядке.
Ответ
Ответ: .
Решение. Покажем, что существует единственная расстановка гусей, удовлетворяющая условию. Введём стандартные шахматные обозначения для горизонталей и вертикалей: горизонтали нумеруются числами от до снизу вверх, вертикали нумеруются буквами от до слева направо (см. рис.)
Заметим, что любая клетка может биться только гусями, расположенными ниже этой клетки, либо правее. Рассмотрим клетку (клетку в правом нижнем углу). Эта клетка не может биться никаким гусём (так как не существует клеток ниже или правее), поэтому в ней обязательно должен стоять гусь. Отметим буквой Г, а также отметим крестиками все клетки, которые бьёт гусь, расположенный в (это только клетка ).
Теперь рассмотрим клетку . Она не может биться никаким гусём, так как ниже неё нет клеток, а правее есть только гусь , который не бьёт . Поэтому в клетке обязательно должен стоять гусь. Отметим буквой Г, а также отметим крестиками клетки , и , которые бьёт гусь, расположенный в .
Будем дальше по одной определять клетки, в которых обязательно стоят гуси. Для этого докажем следующую лемму.
Лемма. Пусть мы знаем про некоторые клетки, что в них обязательно стоят гуси. Отметим все эти клетки буквами Г, а клетки, которые бьют такие гуси — крестиками. Пусть клетка не отмечена, при этом все клетки правее в той же строке отмечены, и все клетки в строках ниже отмечены (синяя область на рисунке). Тогда в клетке обязательно стоит гусь.
Доказательство леммы. Клетка может биться только гусями, расположенными в синей области. Однако в этой области есть только отмеченные клетки. В клетках, отмеченных крестиками, гусей быть не может, а гуси, расположенные в остальных клетках, не бьют клетку (так как все побитые ими клетки отмечены крестиками, а не отмечена). Поэтому клетка не может биться никаким гусём, а значит в ней стоит гусь. Лемма доказана.
Доказанная лемма позволяет последовательно отметить все клетки доски (см. рис.)
Проделав это, убеждаемся, что клетки, занятые гусями, и свободные от гусей, образуют шахматную раскраску, и что гусей на доске обязательно .
Верное решение.