Question

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

Answer 1

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

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

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

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

• Количество ходов четно.  

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

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

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

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

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

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

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

Answer 2

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

Мы можем представить клетчатое игровое поле размерами n * n как граф, в котором вершины представляют клетки поля, а ребра соединяют вершины, если клетки имеют общую сторону. Поскольку фишка должна посетить каждую клетку ровно один раз и закончить в другой клетке, можно сказать, что граф должен быть эйлеровым.

Теперь нам нужно найти все натуральные числа n > 1, при которых такой эйлеров граф существует.

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

Теперь рассмотрим два типа ходов:

1. Фишку можно передвинуть на произвольную клетку, которая имеет общую сторону с текущей клеткой.
2. Фишку можно передвинуть на произвольную клетку, которая имеет с текущей клеткой общую вершину, но не общую сторону.

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

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

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

1. Если N = 0, то все вершины имеют четные степени, и граф является эйлеровым.
2. Если N = 2, то две вершины имеют нечетные степени, и мы можем начать цикл в одной из этих вершин и закончить в другой, получив тем самым эйлеров цикл.

Случай N > 2 не подходит, так как при этом у нас будет больше двух нечетных вершин, и невозможно будет посетить их все ровно один раз, закончив цикл в другой вершине.

Итак, нам интересны только случаи N = 0 и N = 2.

1. N = 0: В этом случае все вершины имеют четные степени, и граф является эйлеровым. Этот случай возможен для любых натуральных чисел n > 1, поскольку каждая вершина клетчатого поля имеет 4 соседа (четное количество), и граф всегда будет эйлеровым.

2. N = 2: Здесь у нас есть две вершины с нечетными степенями. Такой случай возможен только для некоторых значений n. Например, для n = 3 мы можем нарисовать граф с двумя вершинами степени 3 и остальными вершинами степени 4. В этом случае у нас получится эйлеров цикл.

Таким образом, мы получаем два возможных ответа: n > 1, где n принимает значения 3 и любое другое нечетное число.

Итак, ответ: n = 3 и n - любое нечетное число, где n > 1.