ПВГ 2023, 7–9 классы, задача 4 (7–8), задача 3 (9)
Петя и Вася играют в интересную игру. В начале игры у каждого по карт. Петя и Вася ходят по очереди (Петя ходит первым), каждым ходом один отдает другому некоторое количество карт, причем количества переданных карт не могут повторяться — если кто-то, скажем, передал карты, то дальше по карты передавать никому нельзя. Проигрывает тот, кто не может сделать ход по правилам. Есть ли у кого-либо из игроков выигрышная стратегия (способ всегда выигрывать)? Если у Пети, то в ответе укажите , если у Васи, то в ответе укажите , а если такой стратегии нет, то в ответе укажите .
Ответ
Ответ: .
Решение: Стратегия Васи — давать минимально допустимое кол-во карт. Покажем, что при такой стратегии у Васи будет всегда ответный ход.
Заметим, что Петя на каждом ходу, начиная со второго, отдает, по крайней мере, на больше, чем дал ему Вася на предыдущем ходу. Если на первом ходу Петя дал карт, то после -го хода Пети (и ходов Васи) у Васи будет не менее карт. Предположим, что Вася не может сделать ход, значит ходы уже были сделаны, т.е. было сделано ходов. Поскольку , то . Получается, что было ходов Васи и ходов Пети, но в диапазоне (всего у игроков карт) нельзя выбрать различных чисел. Противоречие.