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

Решение:

Данная задача является классической проблемой о 'закрытом' и 'открытом' маршруте (турне) на графе. Шахматная доска 4x4 может быть представлена в виде графа, где поля — это вершины, а возможные ходы коня — рёбра.

Рассмотрим раскраску шахматной доски в чёрно-белые цвета. Конь, делая ход, всегда перемещается с поля одного цвета на поле другого цвета (с чёрного на белое или с белого на чёрное).

На доске 4x4 всего 16 полей. Из них 8 полей чёрные и 8 полей белые.

Если бы конь мог обойти всю доску, побывав на каждом поле ровно один раз, то он сделал бы 15 ходов. Последовательность цветов полей, на которых побывал бы конь, выглядела бы так: Чёрное → Белое → Чёрное → Белое ... или Белое → Чёрное → Белое → Чёрное ...

Если маршрут начинается с чёрного поля, то последовательность будет: Ч, Б, Ч, Б, Ч, Б, Ч, Б, Ч, Б, Ч, Б, Ч, Б, Ч, Б. Итого 8 чёрных и 8 белых полей. Длина маршрута — 16 полей.

Если маршрут начинается с белого поля, то последовательность будет: Б, Ч, Б, Ч, Б, Ч, Б, Ч, Б, Ч, Б, Ч, Б, Ч, Б, Ч. Итого 8 белых и 8 чёрных полей. Длина маршрута — 16 полей.

Однако, для доски 4x4, количество ходов равно 15. Это означает, что конь должен посетить 16 полей. Последовательность ходов будет такая:

• Если начинаем с Чёрного: Ч (1) -> Б (2) -> Ч (3) -> Б (4) -> Ч (5) -> Б (6) -> Ч (7) -> Б (8) -> Ч (9) -> Б (10) -> Ч (11) -> Б (12) -> Ч (13) -> Б (14) -> Ч (15) -> Б (16). В конце окажемся на белом поле.
• Если начинаем с Белого: Б (1) -> Ч (2) -> Б (3) -> Ч (4) -> Б (5) -> Ч (6) -> Б (7) -> Ч (8) -> Б (9) -> Ч (10) -> Б (11) -> Ч (12) -> Б (13) -> Ч (14) -> Б (15) -> Ч (16). В конце окажемся на чёрном поле.

Проблема возникает в том, что на доске 4x4 конь не может посетить все поля, оставаясь на полях одного цвета, или посетить все поля, начиная и заканчивая на полях противоположного цвета, если общее число полей нечётное. В нашем случае, 16 полей — чётное число. Но есть другая проблема:

На доске 4x4, поля, откуда конь может сделать ходы, имеют следующую конфигурацию:

• Углы (A1, A4, D1, D4) - 2 хода
• Соседние с углами (A2, B1, C1, D2, A3, B4, C4, D3) - 3 хода
• Центральные (B2, C2, B3, C3) - 4 хода

Всего 16 полей.

Рассмотрим пример: начнём с поля A1 (чёрное).

A1(Ч) -> B3(Б) -> A1 - зацикливание, поле B3 имеет 4 выхода. Попробуем другой ход.

A1(Ч) -> C2(Б) -> A3(Ч) -> B1(Б) -> D2(Ч) -> C4(Б) -> D2 - зацикливание.

Более строгим доказательством является то, что любую доску $$m \times n$$ с $$mn$$ клетками можно обойти конём ровно один раз (закрыть маршрут) если $$m$$ и $$n$$ оба четные, или если одно из чисел $$m, n$$ равно 1 или 2, или если $$m=3$$ и $$n$$ нечетное и $$n \ne 1, 3$$, или если $$m=4$$ и $$n$$ нечетное и $$n \ne 1$$.

На доске 4x4, $$m=4$$ и $$n=4$$ оба четные. Теоретически, такой обход возможен.

Однако, для доски 4x4, существует классическое доказательство, основанное на раскраске и свойствах графа. Разобьем доску на 4 квадрата 2x2. Конь, перемещаясь, может переходить из одного квадрата в другой. На доске 4x4, при каждом ходе конь меняет цвет клетки. Чтобы посетить все 16 клеток, конь должен совершить 15 ходов. Последовательность цветов будет Ч-Б-Ч-Б... или Б-Ч-Б-Ч... В любом случае, если начать с чёрной клетки, то после 15 ходов (16-е поле) конь окажется на белой клетке. Если начать с белой, то окажется на чёрной.

Основная трудность для доски 4x4 заключается в том, что конь не может добраться до некоторых полей из других, используя только ходы коня. На доске 4x4, поля, которые находятся на расстоянии 2 шагов друг от друга по диагонали (например, A1 и D4), оказываются в