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