Условие
Перед Шариком лежит бесконечное число котлет, на каждой сидит по мухе.
На каждом ходу Шарик последовательно делает две операции:
1) съедает какую-то котлету вместе со всеми сидящими на ней мухами;
2) пересаживает одну муху с одной котлеты на другую (на котлете может быть сколько угодно мух).
Шарик хочет съесть не более миллиона мух. Докажите, что он не может действовать так, чтобы каждая котлета была съедена на каком-то ходу.
Решение 1
Предположим противное. Пронумеруем котлеты в том порядке, в каком Шарик будет их есть. За первый миллион шагов Шарик переложит некоторых мух на какие-то котлеты. Пусть $n$ – наибольший среди номеров этих котлет. Рассмотрим первые $n$ котлет. За первый миллион шагов суммарное количество мух на них не уменьшалось (не считая мух, которые Шарик съел). Значит, перед тем, как съесть последнюю из $n$ котлет, Шарик успеет переложить на котлеты с большими номерами максимум $n-1-1\,000\,000$ мух, и потому за первые $n$ шагов он съест хотя бы 1 000 001 муху.
Решение 2
Пусть Шарик съел не более 1 000 000 мух, съев все котлеты. Тогда каждую не съеденную муху он перемещал бесконечное число раз, иначе он не съел котлету, на которой она остановилась. Рассмотрим момент, когда он переместил какую-то муху $M$ в 1 000 002-й раз. Пусть до этого он съел $N$ котлет (и переместил максимум $N-1$ мух). Хотя бы с $N-1\,000\,000$ из них он переместил муху, которая там была изначально, и лишь одна из них могла быть $M.$ Значит, до этого он перемещал мух хотя бы $(N-1\,000\,000))+1\,000\,000=N$ раз, что невозможно
Решение 3
Предположим противное. Заметим, что тогда с какого-то момента Шарик будет есть только котлеты без мух.
С этого момента число котлет без мух не может увеличиться после хода Шарика:
если он и образовал какую-то новую котлету без мух (переложив с неё муху), то перед этим съел какую-то котлету без мухи.
Тогда с какого-то дальнейшего момента число котлет без мух стабилизируется.
Далее Шарик каждым ходом съедает котлету без мухи и перекладывает муху с котлеты, на которой ровно одна муха, на котлету, где уже есть мухи. Тем самым появится котлета, на которой хотя бы две мухи, и эту котлету Шарик уже никогда не съест (с таких котлет он мух уже не снимает, а котлеты с мухами уже не ест).
Источники и прецеденты использования
