ВсОШ 2025, 9 класс, задача 4
Шахматного короля поставили на клетку доски и сделали им хода так, что он побывал на всех клетках и вернулся в исходную клетку. В каждый момент времени вычислялось расстояние от центра клетки, в которой находился король, до центра всей доски. Назовём сделанный ход приятным, если в результате хода это расстояние стало меньше, чем было до хода. Найдите наибольшее возможное количество приятных ходов. (Шахматный король за один ход передвигается на клетку, соседнюю по стороне или по углу.)
Ответ. хода.
Решение. Докажем, что среди ходов должно было быть хотя бы неприятных (а значит, количество приятных ходов не больше ). Расставим в клетках числа, как показано на рис. ;
клетки с одинаковыми числами удалены на одно и то же расстояние от центра, а клетки с меньшими номерами ближе к центру, чем клетки с большими. Каждый ход из клетки с числом не уменьшает расстояния до центра и потому неприятен — таких ходов . Ход из клетки с числом может быть приятным, только когда он идёт в клетку с числом . Но на доске восемь чисел и только четыре числа , поэтому хотя бы четыре хода из клеток с числом будут неприятными. Рассмотрим теперь ходы, ведущие в клетки с числами, не меньшими . Заметим, что эти ходы не могут идти из клеток с числами и , то есть в рассуждении выше они не учтены. Такой ход может быть приятным, только если он идёт из клетки с номером, не меньшим ; однако таких клеток всего . Значит, среди рассмотренных ходов ещё неприятных, и общее количество неприятных ходов не меньше, чем . Пример обхода, в котором приятных хода, приведён на рис. .
Замечание. По сути, в последней части доказательства оценки показано, что среди ходов, ведущих в клетки, отмеченные зелёным на рис. , есть не менее трёх неприятных. Это можно доказать разными способами, например, проведя небольшой перебор.