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

Предыдущий
вопрос Следующий
вопрос

Пусть n > 1. Рассмотрим клетки на игровом поле как вершины графа. Две вершины будем соединять ребром, если соответствующие клетки имеют общую сторону или общую вершину.

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

Если n - четное, то каждая вершина имеет степень 4 (каждая клетка имеет 4 соседние клетки), поэтому граф обязательно будет эйлеровым и фишка побывает на каждой клетке ровно один раз.

Если n - нечетное, то каждая вершина по краям имеет степень 3, а в середине - степень 4. Граф будет эйлеровым только если все вершины будут иметь степень 4. Поэтому необходимо, чтобы все вершины имели степень 4, то есть n = 4.

Таким образом, единственным подходящим натуральным числом n > 1 является n = 4.