Question

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

Answer 1

Ответ:

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

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

Answer 2

Да, можно пройти от левой нижней клетки к правой верхней клетке, не наступая на доминошки, в обоих случаях.

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

Рассмотрим доску. Поскольку она состоит из 100 строк по 101 клетке, и у нас есть свободные клетки в нижнем левом углу и правом верхнем углу, мы можем легко построить маршрут:

1. Идем 100 клеток вверх, затем 100 клеток вправо.

Таким образом, мы покроем всю доску, не касаясь доминошек.

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

В этом случае, даже количество клеток в каждой строке и столбце. Также есть свободные клетки в нижнем левом углу и правом верхнем углу. Мы можем построить маршрут, который пройдет от нижнего левого угла до правого верхнего угла, двигаясь только вверх и вправо:

1. Идем 50 клеток вверх.
2. Затем идем 50 клеток вправо.

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