Высшая проба 2026, 11 класс, задача 4
(17 баллов) Зафиксировано натуральное число . В пространстве выбрана система прямоугольных координат и размещен куб с ребром , разбитый на кубики с ребром (ребра куба параллельны осям координат). Изначально в некоторых кубиках записаны натуральные числа от до , каждое по одному разу. Назовем -, - или -координатой кубика соответствующую координату его центра. За одно действие разрешается выбрать кубик, в котором записано число , и в любой из пустых кубиков, соседних с выбранным кубиком по грани и имеющих хотя бы одну большую координату, записать число , а затем стереть число из кубика, в котором оно было записано ранее. При этом нельзя записывать число в кубик, если это число уже когда-то было в нем записано. Найдите наименьшее , для которого можно гарантировать, что нельзя сделать больше таких действий.
Ответ. .
Решение. Оценка. Посчитаем вначале, сколько разных кубиков может посетить каждое из чисел . Для этого введем несколько обозначений.
Зафиксируем число . Назовем запись числа в некоторый кубик имеющей прародителя , если число было получено цепочкой действий из начального положения числа . Иными словами, число перешло в , затем в , и так далее, пока не получилось . Обозначим через множество кубиков, в которых могло побывать число с прародителем .
Лемма. Всякий кубик из является сдвигом из кубика, в котором изначально было , на векторы вида , где и .
Доказательство леммы. При каждом действии какая-то из координат кубика, в котором находится число, увеличивается на , а остальные две координаты не меняются. Значит, после действий суммарный сдвиг от начального кубика числа имеет вид , где и . Лемма доказана.
Из леммы следует, что
Значит, число может посетить не более
кубиков. Поэтому всего посещенных кубиков не больше
Так как в это число входят начальных положений, количество действий не превосходит .
Пример. Покажем, что такая оценка достигается. Вначале расставим числа в кубики с координатами соответственно. Будем действовать следующим образом. Для каждого разрешим числу посетить все кубики, координаты которых имеют вид
где и , .
Переходы выполняются в порядке возрастания . Каждый раз, когда нужно записать , выбираем соседний кубик с одной большей координатой так, чтобы пройти все новые кубики, которые получаются из уже посещенных кубиков для числа прибавлением одного из векторов , , . Запрет на повторную запись того же числа в один и тот же кубик не нарушается, поскольку каждый новый кубик для фиксированного появляется ровно в тот момент, когда он должен быть впервые посещен этим числом.
Если при попытке записать в нужный соседний кубик там уже стоит число , то при получилось бы нарушение порядка посещения больших чисел, а при получилось бы обратное нарушение порядка удаленности. Значит, препятствием может быть только то, что число уже раньше было в этом кубике.
Пусть — множество кубиков, которые посетит число . По построению
где , , . Индукцией получаем, что для всех . Поэтому всего посещенных кубиков
Вычитая начальных положений, получаем ровно действий. Оценка достижима, что и требовалось
Верное решение.
О1. Доказана верная оценка сверху на количество действий.
А1. Предъявлена начальная расстановка чисел и сформулирован корректный алгоритм, позволяющий сделать наибольшее количество действий.
А2. Только заявлена расстановка чисел на главной диагонали куба, дальнейших продвижений нет.
Б1. Доказана корректность алгоритма, реализующего наибольшее количество действий из.
В1. Подсчитано число действий в алгоритме.
Решение не соответствует ни одному из критериев выше.
Комментарии. Реализовать алгоритм измогут помешать два препятствия. Обоснование отсутствия каждого препятствия веситбалла. Баллы за критерии с разными литерами суммируются.