Question

Дано клетчатое игровое поле размерами n * n. на какую-то клетку игрового поля ставят фишку, которой можно совершать ходы двух типов: фишку можно передвинуть на произвольную клетку, которая имеет общую сторону с текущей клеткой, или же на произвольную клетку, которая имеет с текущей клеткой общую вершину, но не общую сторону. два последовательных хода всегда должны быть различных типов. найти все натуральные числа n > 1, при которых можно выбрать начальную клетку и последующие ходы так, чтобы фишка побывала на каждой клетке игрового поля ровно один раз и закончила в клетке, отличной от начальной.

Answer 1

Докажем, что для нечетного $n$  это невозможно, а затем приведем пример для четного.  

Доказательство:  

Предположим обратное: найдется $n$  при котором требуемое возможно.  

Раскрасим доску в шахматную раскраску так, чтобы левый верхний угол был черным. Тогда черных больше. Последовательность ходов будем обозначать цветами. Теперь несколько замечаний  

Количество ходов четно.  В силу этого первый и последний ходы разного типа

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

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

Итак, убрав первую клетку, получим, что оставшаяся фигура полностью замощена доминошками. Но поэтому она должна быть замощена и "диагональками" (два квадрата с общей вершиной) без пересечений.

Докажем, что это невозможно: будем закрашивать каждую нечетную строку в черный цвет. Тогда черных на $n-1$  больше (одна черная клетка отсутствует). Но если требуемое замощение возможно, то в каждую диагональку попадает ровно 1 черная и 1 белая клетки, а, значит, их поровну. Противоречие здесь завершает доказательство.

Теперь приведем пример для четного: отметим в квадрате путь "змейкой". В каждом квадрате 2х2 будет узор указанный на рисунке. На верхних (выше центра квадрата) горизонтальных путях узор будет совпадать с указанным. На правых вертикалях - пов. на 90 гр. влево.

На левых - пов. на 90 гр. вправо. На нижних - на 180 гр.