Вариация игры "ним" Есть куча из N камней. Два игрока по очереди берут хотя бы по одному камню, но не разрешается взять более чем удвоенное число камней, взятых соперником на предыдущем ходе. Выигрывает тот, кто возьмет последний камень. При этом первым ходом нельзя взять все.

При каких N между 100 и 200 выигрывает второй игрок (при правильной игре) ?

Предыдущий
вопрос Следующий
вопрос

Для того чтобы определить при каких N второй игрок выигрывает при правильной игре, нужно применить стратегию обратной индукции.

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

Для N=3 первый игрок обязан взять 1 камень, тогда второй игрок возьмет 2 камня и выиграет.

Для N=4 первый игрок обязан взять 1 камень, затем второй игрок возьмет 2 камня, значит останется 1 камень и первый игрок проиграет.

Далее продолжаем проверять значения N методом обратной индукции. После небольших вычислений обнаружим, что при N=7, N=15, N=31, N=63, N=127 второй игрок выигрывает при правильной игре, так как в любой ситуации он может заставить первого игрока остаться с последним камнем.

Таким образом, при N=127 второй игрок будет выигрывать при правильной игре.