На столе лежит 55 кучек конфет. В одной кучке лежит 1 конфета, в другой — две, в третьей — 3, …, в последней — 55. Петя и Вася играют в следующую игру, делая ходы по очереди; начинает Петя. За один ход игрок берёт одну конфету из любой кучки. Если игрок забрал из кучки последнюю конфету, то он её съедает, а иначе выбрасывает. Игра продолжается до тех пор, пока все конфеты из кучек не будут съедены или выброшены. Какое наибольшее количество конфет может гарантированно съесть Петя?
1 Ответ
Решение:
Понятно, что Петя может съесть 1 конфету, например, если самым первым ходом заберёт конфету из кучки с 1 конфетой. Докажем, что Вася может помешать Пете съесть больше 1 конфеты. Для этого Вася будет действовать следующим образом. Если в какой-то кучке осталась ровно 1 конфета, он заберёт её и съест. Если же кучек с 1 конфетой нет, он будет брать конфету из любой кучки, в которой более 2 конфет. Для начала поймём, почему Вася всегда сможет сделать ход по такой стратегии. Предположим, что в какой-то момент Вася не может сделать ход, то есть в каждой кучке не больше 2 конфет, при этом нет кучек с 1 конфетой. Тогда в каждой кучке ровно 2 конфеты, и перед ходом Васи осталось чётное количество конфет. С другой стороны, изначально на столе конфет было 1 + 2 + … + 55 = 55 ⋅ 56/2 = 1540, т. е. чётное количество. Значит, после хода Пети должно оставаться нечётное количество конфет, а после хода Васи — чётное количество, противоречие.
Теперь докажем, что при такой стратегии Васи Петя не сможет съесть больше 1 конфеты.
Заметим, что если после какого-то хода Пети нет кучек из 1 конфеты, то их больше никогда и не будет. Действительно, кучки, из которых берёт конфеты Вася, после его хода не могут состоять только из 1 конфеты, а все кучки из 1 конфеты, которые оставляет Петя, Вася сразу же съедает следующим ходом.
Таким образом, если Петя на первом ходу съест кучку из 1 конфеты, больше он конфет никогда не съест. Если же он не будет этого делать, её следующим ходом съест Вася, а Петя успеет за свой первый ход сделать не более одной новой кучки из 1 конфеты. Если она всё-таки появится (из кучки с 2 конфетами), и Петя не съест её на своём втором ходу, то он не съест вообще ничего, так как новой кучки из 1 конфеты на втором ходу он образовать не сможет. А если съест, то, как и ранее, больше ничего съесть не сможет. Итак, у Васи есть стратегия, позволяющая не дать Пете съесть более 1 конфеты.