Раскраски

Оценка. Пронумеруем строки и столбцы числами от до Покрасим клетки доски в четыре цвета и следующим образом: клетки вида при некоторых натуральных и — в цвет , — в цвет — в цвет и — в цвет

Из клетки цвета ладья должна перейти в клетку цвета или В первом случае порядок цветов посещенных ячеек задается во втором случае это Поскольку маршрут замкнут, он должен содержать одинаковое количество клеток каждого цвета. Существует всего клеток цвета Далее мы покажем, что ладья не может посетить все клетки цвета на своем маршруте и, следовательно, максимально возможное количество клеток в маршруте равно

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

Пусть ладья пройдет следующий путь

Без ограничения общности клетка покрашена в цвет (иначе поменяем роли столбцов и строк).

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

Но пересечение возможно только в том случае, если ячейка посещена дважды. Это противоречие. Следовательно, количество посещенных ячеек не превышает

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