ВсОШ 2024, 9 класс, задача 3
Двум мальчикам выдали по мешку картошки, в каждом мешке по клубней. Ребята по очереди перекладывают картошку, каждый своим очередным ходом перекладывает ненулевое количество клубней из своего мешка в чужой. При этом они должны соблюдать условие новой возможности: на каждом ходе мальчик должен переложить больше клубней, чем у него было в мешке перед любым из его предыдущих ходов (если такие ходы были). Так, первым своим ходом мальчик может переложить любое ненулевое количество, а своим пятым ходом мальчик может переложить клубней, если перед его первым, вторым, третьим и четвёртым ходами количества клубней в его мешке были меньше . Какое максимальное суммарное количество ходов могут совершить ребята? (Е. Молчанов)
Ответ
Ответ. .
Решение. Пусть в процессе было ходов. Рассмотрим -й ход. Обозначим через количество клубней у мальчика, делавшего этот ход, сразу после хода. Тогда у другого мальчика после хода клубней. Также обозначим через количество клубней у (любого) мальчика перед первым ходом.
В этих обозначениях перед -м ходом у мальчика, делавшего его, было клубней, а после него - клубней. Значит, на этом ходу он передавал клубней. Если , то это количество должно быть больше, чем количество клубней у этого мальчика перед его предыдущим, то есть -м, ходом: . Итак, . Поскольку все числа целые, получаем при всех .
Теперь можно получить оценки на числа , действуя <<с конца>>. Определим числа условиями и . Докажем, что и , индукцией по . При неравенства очевидны; для перехода достаточно заметить, что
Итак, мы получаем . Приведём таблицу первых значений чисел :
Значит, из условия получаем, что .
Пример. Пример, когда дети могут сделать ходов, следует из построения выше. Изначально у каждого ребёнка по клубней. Пусть дети действуют так, чтобы после -го (с начала) хода у перекладывавшего оставалось ровно клубней; тогда на -м ходе ребёнок перекладывает клубней, а перед любым предыдущим его ходом у него будет клубней при , причём . Значит, этот ход удовлетворяет условию, и дети могут сделать таких ходов.
Замечание. Приведённый алгоритм почти единственен; именно, в любом примере, где делается ходов, ситуация после каждого хода, кроме первого, должна быть такой же, как в приведённом примере.