Всесиб 2026, 11 класс, задача 5
( баллов) В таблице размера на клеток отмечены некоторые клеток так, что в каждой строке и каждом столбце отмечена ровно одна клетка. Кроме того, в некоторых клетках таблицы расставлены фишек так, что в каждой строке и каждом столбце стоит ровно одна фишка. За один ход можно переставить одну из фишек в любую соседнюю с ней по стороне пустую клетку. Найти минимальное такое, что при любых допустимых расстановке фишек и отметке клеток в таблице все фишки можно переставить на отмеченные клетки не более, чем за ходов. Некоторые фишки могут изначально стоять в отмеченных клетках.
Ответ
Ответ. .
Решение. Покажем, что не меньше .
Пример 1. Занумеруем клетки таблицы как в шахматах, вертикали - слева направо латинскими буквами от до , горизонтали - снизу вверх цифрами от до . Отметим все клетки главной диагонали таблицы из нижнего левого угла в правый верхний: , а фишки расставим на клетках побочной диагонали таблицы из левого верхнего угла в правый нижний: . Несложно убедиться в том, что для того, чтобы попасть на главную диагональ, фишкам с полей и потребуется не менее ходов, фишкам с полей и - не менее ходов, фишкам с полей и - не менее ходов, фишкам с полей и - не менее хода. Итого, чтобы передвинуть все фишки на отмеченные поля в данной конфигурации потребуется не менее хода. Подсчёт сделан даже без учёта возможных помех со стороны других фишек при движении.
Пример 2. Отметим все клетки главной диагонали таблицы из нижнего левого угла в правый верхний: , а фишки расставим на клетках . В этом случае для того, чтобы попасть на главную диагональ, каждой фишке нужно сделать не меньше ходов, а всем вместе хода. Все приведённые участниками примеры были только как в примерах и .
Теперь докажем, что ходов всегда хватит, причём достаточно просто переставить каждую фишку в отмеченную клетку, расположенную с ней в одном столбце. Фишки, уже стоящие в отмеченных клетках, мы не трогаем, и они не влияют на оценку потому, что в столбцах и строках, их содержащих, нет других фишек и отмеченных клеток. Каждую из остальных фишек переставим последовательными ходами в отмеченную клетку того столбца, в котором она стоит.
Способ 1. Заметим, что при этом линию сетки, разделяющую первую и вторую горизонтали, могли пересечь не более двух фишек - уходящая с первой строки и приходящая на неё. Аналогично, линию сетки, разделяющую вторую и третью строки, могли пересечь не более четырёх фишек - уходящие с первой и второй строк и приходящие на первую и вторую строки. Продолжая так далее, получим, что следующие горизонтальные линии сетки могли соответственно пересечь не более фишек. Каждое пересечение горизонтальных линий сетки - это ход некоторой фишки, и каждый ход в нашем алгоритме - это пересечение горизонтальных линий сетки, поэтому всего при любом начальном расположении фишек и клеток будет сделано не более ходов, и все фишки окажутся на отмеченных клетках.
Способ 2. Обозначим за и номер фишки и номер отмеченной клетки в -ом столбце, , соответственно. Тогда количество ходов только по вертикали, требующихся для постановки фишек на отмеченные клетки, не превосходит максимума суммы . Среди чисел и , , по одному разу встречаются все числа от до . При раскрытии модулей получатся из этих чисел со знаком плюс и восемь из этих чисел со знаком минус. Сумма восьми чисел со знаком плюс не превосходит суммы восьми максимальных чисел из множества , то есть , а сумма восьми чисел со знаком минус не меньше суммы восьми минимальных чисел из множества , то есть . Следовательно, количество ходов только по вертикали, требующихся для постановки фишек на отмеченные клетки, не превосходит разность этих сумм, не превосходящую . Заметим, что для многих расположений клеток и фишек минимальное число ходов достигается только при использовании и горизонтальных и вертикальных ходов, правда, оно при этом меньше .
Ответ. .