Решение задачи 463

Условие:

Может ли ладья обойти все клетки доски 10×10, побывав на каждой клетке ровно по разу, чередуя ходы длиной в одну и в две клетки? (Считается, что, делая ход длиной в две клетки, ладья не проходит по промежуточной клетке.)

Решение:

Покрасим доску в крупную шахматную раскраску (квадраты 2х2 в шахматном порядке). Всего получилось 52 белых клетки, 48 черных. Заметим, что делая длинный ход, ладья меняет цвет клетки на которой стоит. Делая короткий ход, ладья может менять цвет, может не менять. Пусть ладья смогла обойти доску. Выпишем последовательность цветов клеток, на которые ладья встает на своем пути. Белую клетку обозначим через "б", черную — через "ч". Получится последовательность длины 100 из букв "б" и "ч".

Рассмотрим два случая:

1) Первый ход длинный. Разобьем нашу последовательность на пары соседних букв: (* *) (* *) .... (* *). Звездочка это либо "б", либо "ч". Каждая пара (их 50) отвечает за длинный ход, значит в каждой паре ровно одна буква "ч". Получается, всего в последовательности ровно 50 букв "ч", но на доске всего 48 черных клеток.

2) Первый ход короткий. Разобьем нашу последовательность на пары чуть по-другому, вторую букву с третьей, и так далее: * (* *) (* *) ... (* *) *. В каждой паре (их 49) опять ровно одна буква "б". Первая и последняя буквы в принципе могут быть "б". Получается, в этой последовательности максимум 51 буква "б", а должно быть 52.

Приходим к выводу, что так обойти доску невозможно.

Ответ: Нет.