Размещено 5 лет назад по предмету Математика от gfhgfhdghfhgfh

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

Ответ на вопрос

Ответ на вопрос дан Guerrino
Докажем, что для нечетного $n$ это невозможно, а затем приведем пример для четного.
Доказательство:
Предположим обратное: найдется $n$ при котором требуемое возможно.
Раскрасим доску в шахматную раскраску так, чтобы левый верхний угол был черным. Тогда черных больше. Последовательность ходов будем обозначать цветами. Теперь несколько замечаний
Количество ходов четно.
В силу этого первый и последний ходы разного типа
Без ограничения общности можно считать, что первый ход второго типа (иначе последний ход - первого типа и можно запустить процесс в обратную сторону). Будем считать, что ход первого типа образует доминошку. Причем никакие две доминошки не пересекаются.
Тогда первый ход начинается с черной клетки. Действительно, если бы он начинался с белой, то эта белая клетка не входила бы ни в одну из доминошек, а остальные клетки бы разбились на доминошки. Но в каждой доминошке поровну цветов. Поэтому оказалось бы, что белых больше. Противоречие. Тогда в силу обратимости последний ход тоже на черную клетку.
Итак, убрав первую клетку, получим, что оставшаяся фигура полностью замощена доминошками. Но поэтому она должна быть замощена и "диагональками" (два квадрата с общей вершиной) без пересечений.
Докажем, что это невозможно: будем закрашивать каждую нечетную строку в черный цвет. Тогда черных на $n-1$ больше (одна черная клетка отсутствует). Но если требуемое замощение возможно, то в каждую диагональку попадает ровно 1 черная и 1 белая клетки, а, значит, их поровну. Противоречие здесь завершает доказательство.
Теперь приведем пример для четного: отметим в квадрате путь "змейкой". В каждом квадрате 2х2 будет узор указанный на рисунке. На верхних (выше центра квадрата) горизонтальных путях узор будет совпадать с указанным. На правых вертикалях - пов. на 90 гр. влево.
На левых - пов. на 90 гр. вправо. На нижних - на 180 гр.