ВсОШ 2023, 9 класс, задача 7
( баллов) Перед сладкоежкой лежат пять коробок с конфетами: в первой коробке конфет, во второй — конфеты, в третьей — конфеты, в четвёртой — конфеты, в пятой — конфет. За один ход сладкоежка может взять из одной коробки четыре конфеты и разложить их по одной конфете в оставшиеся четыре коробки.
В любой момент сладкоежка может забрать конфеты из любой коробки и уйти. Какое наибольшее количество конфет он сможет забрать?
Ответ
Ответ: .
Решение. Рассмотрим количества конфет в коробках. Изначально это натуральных чисел, дающих различные остатки при делении на . Докажем, что пока сладкоежка не заберёт конфеты из какой-либо коробки, эти чисел всегда дают различные остатки при делении на . Для этого достаточно понять, что разность любых двух из этих чисел никогда не делится на .
Пусть в какой-то момент в каких-то двух коробках лежало и конфет, причём разность не делится на . После того, как сладкоежка как-то переложит конфеты, эта разность будет принимать одно из значений
Очевидно, что все они по-прежнему не делятся на .
Пусть сладкоежка в какой-то момент забрал все конфеты из одной из коробок. Посмотрим на оставшиеся четыре коробки: общее количество конфет в них не меньше, чем сумма остатков при делении на соответствующих чисел. Таким образом, в них осталось хотя бы конфет. Соответственно, сладкоежка забрал не более конфет.
Теперь приведём пример, как сладкоежка может забрать ровно конфет. Пусть он перекладывает по конфеты из первых четырёх коробок, пока это возможно (то есть пока хотя бы в одной из этих коробок есть хотя бы конфеты). Этот процесс рано или поздно закончится, ведь с каждым таким ходом общее количество конфет в первых четырёх коробках уменьшается ровно на (в одной коробке количество конфет уменьшается на , а в трёх оставшихся — увеличивается на ).
В тот момент, когда такой процесс закончится, в каждой из первых четырёх коробок будет от до конфет. Но мы доказали ранее, что количества конфет в этих четырёх коробках должны давать разные остатки при делении на . Отсюда следует, что в одной коробке лежит конфет, в другой — , в третьей — , в четвёртой — конфеты. Значит, остальные конфет лежат в пятой коробке, их сладкоежка и заберёт.
Верное решение.