Отзывы пользователей

гдз

Олимпиадная задача по математике из коллекции задач Турнира Ломоносова на темы: Шахматные доски и шахматные фигуры, Четность и нечетность, Шахматная раскраска.

Условие

"Крокодилом" называется фигура, ход которой заключается в прыжке на клетку, в которую можно попасть сдвигом на одну клетку по вертикали или горизонтали, а затем на N клеток в перпендикулярном направлении (при N = 2 "крокодил" — это шахматный конь). При каких N "крокодил" может пройти с любой клетки бесконечной шахматной доски на любую другую?

Решение

Будем считать, что рассматриваемая бесконечная шахматная доска, как и обычная, раскрашена в белый и черный цвета в шахматном порядке. Тогда при нечетном N "крокодил" будет ходить только по клеткам одного цвета, и, тем самым не может пройти на любую клетку.

Докажем теперь, что при четном N "крокодил" может пройти с любой клетки на любую. Очевидно, для этого достаточно доказать, что он может пройти с любой клетки на соседнюю (смежную по стороне). Покажем, как пройти из клетки в соседнюю с ней сверху. Первым ходом ходим на одну клетку вправо и N клеток вверх, а вторым — на одну вправо и N вниз. Так мы окажемся на две клетки правее исходной. Повторим эту пару ходов N/2 раз (тогда мы окажемся на N клеток правее исходной), после чего пойдем на одну клетку вверх и N влево. Мы оказались в клетке, соседней с исходной.

 
Поделиться: