|
|
 |
Условие
На клетчатой доске лежат доминошки, не касаясь даже углами. Каждая доминошка занимает две соседние (по стороне) клетки доски. Нижняя левая и правая верхняя клетки доски свободны. Всегда ли можно пройти из левой нижней клетки в правую верхнюю, делая ходы только вверх и вправо на соседние по стороне клетки и не наступая на доминошки, если доска имеет размеры
а) $100\times101$ клеток;
б) $100\times100$ клеток?
Решение
На рисунке слева показано расположение доминошек на доске $6\times 7$, которое не позволяет пройти из левой нижней клетки в правую верхнюю. Действительно, попасть в (серую) область правее самой нижней доминошки нельзя, поскольку сначала мы должны подняться выше первой доминошки, и тогда мы уже выше серой полосы (а вниз ходить нельзя). Далее, нельзя попасть в аналогичную серую область правее следующей доминошки и т.д. Эта конструкция обобщается на любую доску размера $2n\times (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)$ не закрыт.
Ответ
а) не всегда;
б) всегда.
