Условие
Доказать, что никакую прямоугольную шахматную доску шириной в 4 клетки нельзя
обойти ходом шахматного коня, побывав на каждом поле по одному разу и последним
ходом вернувшись на исходную клетку.
Решение
Мы представляем себе доску
n×4, имеющую 4 вертикали и
n горизонталей. "Крайними" мы
будем называть клетки, расположенные на первой и четвертой вертикалях;
остальные клетки назовём "средними".
Заметим, что с любой из крайних вертикалей конь за один ход может попасть
только на среднюю клетку.
Значит, если бы конь мог требуемым способом обойти доску, то клетки,
находящиеся на крайних вертикалях, были бы расположены в последовательности
ходов коня не подряд (именно,
никакие две такие клетки не идут
подряд).
С другой стороны, крайних клеток столько же, сколько средних, а конь, по
условию, обходит все клетки по одному разу и возвращается на исходную клетку.
Ясно поэтому, что крайние клетки расположены не реже, чем через одну, в
требуемой последовательности ходов коня. (Если бы где-нибудь встретились
подряд две средние клетки, то в качестве "компенсации" должны
были бы найтись и две крайние, идущие подряд; последнее, однако, невозможно).
Мы видим, что крайние клетки должны быть расположены в требуемой
последовательности ходов строго через одну.
Но в этом случае они все были бы одного цвета, а это противоречит устройству
шахматной доски.
Источники и прецеденты использования
