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