Всесиб 2024, отборочный этап, 11 класс, задача 5

Ответ. б) .

Решение. А) Занумеруем все коробки по порядку слева направо целыми числами в естественном порядке. Считаем, что сначала единственный камень лежит в коробке с номером . В каждый момент времени будем рассматривать сумму чисел камней в каждой из коробок с коэффициентом, который (1) равен , если номер коробки делится на , (2) равен , если остаток от деления номера коробки на равен или , (3) и равен , если этот остаток равен или . То есть, знаки идут в таком порядке с периодом . Формально эта сумма содержит бесконечное количество слагаемых, однако ясно, что в каждый момент только конечное число из них отлично от нуля, поэтому данная сумма корректно определена. Заметим, что на каждом ходу эта сумма не меняется: если камень забирается из коробки с коэффициентом , то его исчезновение не замечается, а добавление по камню в две соседние коробки компенсируется их разными знаками. Если же камень забирается из коробки с ненулевым коэффициентом, то один из добавленных в соседние коробки камней компенсирует его пропажу, так как имеет тот же коэффициент, а второй — игнорируется. В начальный момент времени сумма равна , а в момент, когда в нескольких стоящих подряд коробках лежат по камней в каждой, а в остальных камней нет, равна сумме нескольких слагаемых, каждое из которых равно или , то есть делится на . Следовательно, .

Б) Докажем, что единственный ответ . Вот как за хода получаются пять идущих подряд единиц:

В данном пункте считаем для симметрии, что сначала единственный камень лежит в коробке с номером . Предположим, что после некоторой последовательности ходов получилось идущих подряд коробок, содержащих по одному камню каждая, а остальные пусты. Обозначим номер самой левой из этих коробок за , а самой правой — за , при этом . За один ход общее количество камней в коробках увеличивается на один, следовательно, всего был сделан ход.

1) Сначала докажем, что все ходы были сделаны только в коробки с номерами из интервала от до . Пусть самая левая коробка из всех, в которые был сделан хотя бы один ход, имела номер и в неё было сделано ходов. Тогда коробка с номером в итоге будет содержать камней, забрать которые можно было бы только ходами в эту коробку, но таковых у нас не было. Следовательно, , то есть . Аналогично, номер самой правой коробки из всех, в которые был сделан хоть один ход, удовлетворяет неравенству , то есть . Таким образом, мы доказали, что ходов были сделаны не более, чем в коробки. Учитывая, что в коробку с номером был сделан самый первый ход, справедливы неравенства , .

2) Докажем, что в каждую из коробок с номерами от до был сделан хотя бы один ход. Действительно, рассмотрим самую левую коробку из этого интервала, в которую не было сделано ни одного хода, пусть она имеет номер . Не умаляя общности, в силу симметрии можно считать, что . Ввиду наличия камня в коробке следует, что в коробку был сделан ход и . Рассмотрим самый первый по номеру ход , который был сделан в коробку с номером, меньшим . Для этого в ней должен был уже содержаться хотя бы один камень, чего быть не могло, так как коробка с отрицательным номером не может содержать начальный камень, и камень не мог там появиться ранее, так как появиться он может только ходом в коробку с номером, не большим . Последнее невозможно, так как в коробку ходов не было вообще, а в коробки с меньшими номерами не было ходов, предшествующих .

Следовательно, в каждую из коробок с номерами от до был сделан хотя бы один ход. Аналогично, в каждую из коробок с номерами от до тоже был сделан хотя бы один ход. В коробку с номером был сделан самый первый ход. Таким образом, мы показали, что во все, кроме одной, из коробок с номерами от до был сделан ровно один ход, а в одну из них — два хода. Если это не одна из крайних коробок с номерами и , то в ней в результате ходов в соседние с ней коробки должно добавиться камня и убавиться в результате ходов в неё камня. В итоге в ней должен остаться камень, значит, это начальная коробка с номером . Если это одна из крайних коробок, то в ней должно убавиться камня и добавиться всего один. Даже если бы это была коробка с номером , то в результате в ней не оказалось бы камней — противоречие. Следовательно, два хода были сделаны в начальную коробку с номером .

3) Теперь посмотрим на три самых левых коробки с номерами , где в итоге окажется по камню. Если , то в коробки с номерами были сделаны по одному ходу, значит, в коробке номером в итоге останутся камней, что противоречит условию. Следовательно, . Аналогично, , а , и всего было сделано не более ходов. Окончание решения делается перебором тех расположений камней, которые можно получить из исходного за не более, чем хода. С точностью до симметрии, за два хода можно получить только одно расположение

Из него можно получить за один ход три расположения , , , а из них за один ход расположения , , , , , , , , с точностью до симметрии. Среди них только одно расположение пяти камней в ряд отвечает условию задачи. Следовательно, ответом является единственное значение .