Question

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

a) 100×101 клеток;

б) 100×100 клеток?

Answer 1

Ответ:

а) нет, так как длина и высота клетчатой доски не одинаковы. Следовательно найдётся такой случай, при котором нельзя будет пройти из левой нижней клетки в правую верхнюю, ходя только вправо и вверх.

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