Олимпиада Туймаада по математике. Старшая лига. 2013 год

На столе лежит 100 куч камней. Два игрока делают ходы по очереди. За один ход разрешается взять со стола произвольное (ненулевое) количество камней из любого числа куч, не превосходящего 99. Проигрывает тот, кто не может сделать ход. Для любого начального положения укажите, кто выиграет при правильной игре — начинающий или его противник. ( К. Кохась )

Комментарий/решение

Понял условие как: для каждого начального положения укажите...

Решение:

Обозначим начинающего как первый игрок и противника как второй игрок.

Если в самом начале в $100$ кучах количество камней поровну то выигрывает второй игрок, в противном случае выигрывает первый игрок.

Допустим, что в самом начале количество камней поровну во всех $100$ кучах.

Если первый игрок после своего хода заканчивает камни хотя бы в одной куче , то остается $99$ или меньше куч, которые второй игрок сможет опустошить за один ход, и одержать победу.

Из-за того, что первый игрок отбирает камни хоть из какой-то кучи и хотя бы одна куча останется нетронутой (из-за ограничения в условии в $99$ куч) то после первого хода хоть в какой-то куче станет меньше камней чем в нетронутой куче. Таким образом, второй игрок может определить кучу с наименьшим количеством камней (таких может быть несколько но не $100$) и своим ходом приравнять количество камней в каждой из остальных куч на это наименьшее количество.

У первого игрока опять $100$ куч с одинаковыми количествами камней и второй игрок может продолжать придерживаться своей стратегии. Таким образом, после каждого хода количество камней в каждой куче будет уменьшаться по крайней мере на 1 камень. Так как камней конечное количество то это дойдет до того, что в какой-то момент первый игрок опустошит хотя бы одну кучу при этом оставив за собой хотя бы одну непустую кучу. И это означает победу для второго игрока, так как он приравняет количество камней в остальных кучах к $0$.

Если же в самом начале количество камней в кучах все таки не поровну, то первый игрок может действовать как второй: Первым ходом определить кучу с наименьшим количеством камней и все остальные кучи приравнять к этому количеству. И теперь у второго игрока проигрышная ситуация описанная выше.