Есть две кучи камней, причём в большей — 8 камней. Два игрока по очереди берут либо несколько камней из одной кучи, либо по равному количеству камней из обеих куч. Выигрывает тот, кто возьмёт последний камень. Кто выигрывает при правильной игре?

В условии не указано, сколько камней в меньшей куче, поэтому нужно рассмотреть все возможные варианты. Пусть меньшая куча содержит $a$ камней, где $a<8$. Начальная позиция имеет вид $(a,8)$.

Эта игра является вариантом игры Витхоффа: проигрышные позиции (из которых при правильной игре проигрывает тот, кто ходит) среди небольших куч имеют вид:

То есть позиции, где игрок, делающий ход, не может перевести игру в одну из этих позиций.

Так как большая куча содержит 8 камней, возможные проигрышные позиции с большей кучей меньше 8:

Ни одна позиция вида $(a,8)$, где $a<8$, не является проигрышной. Значит, первый игрок всегда может сделать ход в одну из проигрышных позиций.

Например:

• если кучки $(1,8)$, первый игрок забирает 6 камней из большой кучи и получает $(1,2)$;
• если $(2,8)$, он забирает 1 камень из большей и 1 из меньшей кучи, получая $(1,7)$, что эквивалентно позиции $(1,2)$ после перестановки? Нет — поэтому правильный ход: забрать 1 камень из меньшей кучи, получив $(1,8)$, а затем стратегия уже продолжается. (В общем случае ход подбирается до одной из проигрышных позиций.)
• если $(3,8)$, можно забрать 3 камня из большой кучи и получить $(3,5)$;
• если $(4,8)$, можно забрать 1 камень из большой кучи и получить $(4,7)$.

Аналогично проверяются остальные значения меньшей кучи.

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

0 0 Пожаловаться