Задание №177001: Турнир городов

5. На клетчатой доске лежат доминошки, не касаясь даже углами. Каждая доминошка занимает две
соседние (по стороне) клетки доски. Нижняя левая и правая верхняя клетки доски свободны. Всегда ли

можно пройти из левой нижней клетки в правую верхнюю, делая ходы только вверх и вправо на соседние
по стороне клетки и не наступая на доминошки, если доска имеет размеры
а) [2] 100 × 101 клеток;
б) [4] 100 × 100 клеток?
Николай Чернятьев
а) Ответ: не всегда.
Решение. На рисунке справа вверху показано расположение доминошек на
доске 6×7, которое не позволяет пройти из левой нижней клетки в правую верх-
нюю. Действительно, попасть в (серую) область правее самой нижней доминош-
ки нельзя, поскольку сначала мы должны подняться выше первой доминошки,
и тогда мы уже выше серой полосы (а вниз ходить нельзя). Далее, нельзя по-
пасть в аналогичную серую область правее следующей доминошки и т.д. Эта

конструкция обобщается на любую доску размера 2n × (2n + 1).
Замечание. Для упрощения доказательства можно было бы добавить ещё
горизонтальные доминошки над вертикальными, чтобы оставался единственный
путь по доске, упирающийся в итоге в последнюю вертикальную доминошку
(рисунок справа внизу).
б) Ответ: всегда.
Решение. Начальная и конечная клетки лежат на главной диагонали доски и имеют «координаты»
(1,1) и (100,100). Докажем, что в любую свободную клетку этой диагонали можно попасть.
Действительно, пусть мы дошли до клетки (n,n). Если клетка (n + 1,n + 1) свободна, то хоть одна из

клеток (n,n + 1) и (n + 1,n) не занята и через неё можно пройти на клетку (n + 1,n + 1).
Если же клетка (n + 1,n + 1) занята, то из её соседей занята ровно одна клетка, причём по стороне,
поэтому один из двух путей из (n,n) в (n + 2,n + 2) не закрыт.





2

10 – 11 классы