Анализ позиций

Заметим, что если в куче нечетное число камней, то первый игрок гарантирует себе победу, взяв на первом ходу 1 камень: тогда каждым следующим ходом игроки будут забирать по одному камню, и последний камень заберет первый игрок. Когда чётно, тот, кто первым сделает нечетный шаг, проиграет: такой шаг был сделан из четного числа — значит, он не будет последним, а противник заберет один камень, что и обеспечит ему победу.

Если то второй игрок, очевидно, побеждает. Если то побеждает первый игрок, забирая первым ходом 1 камень. Если то побеждает второй игрок: если первый берет 1 камень, то второй возьмет последний камень, а если первый игрок первым ходом берет 2 или 3 камня, то второй игрок первым своим ходом забирает остальные камни.

Докажем по индукции, что для всех четных от до (для натурального ) побеждает первый игрок, а для — второй. База индукции разобрана выше.

Пусть для натурального Тогда первый игрок сводит игру к таковой с камнями (т.е. берет вдвое больше камней, чем взял бы в игре с камнями), где у него есть победная стратегия согласно предположению индукции, поскольку Единственный способ помешать ему — взять нечетное число камней, но, как показано выше, тот, кто первым возьмет нечетное число камней, проигрывает.

Пусть теперь для Тогда уже второй игрок применяет стратегию "половинчатой"игры, т.е. берет в 2 раза больше камней, чем взял бы в игре с камнями. Согласно предположению индукции, это обеспечит ему победу.