Есть ли способ упростить мое мышление о N башнях игры M высот?

Question

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

Например, если N=2,M=2, то первый игрок проиграет, потому что единственные шаги, которые он может сделать, - это уменьшить одну из башен до высоты 1, после чего единственный ход, который может сделать другой игрок, - уменьшить другую башню до высоты 1 и теперь у первого игрока нет ходов.

Я начал писать об этом, но мне становится слишком сложно увидеть «шаблон» на нестандартном M s, таком как 4. Есть ли лучший способ, я должен думать об этом?

1 --> Lose 
1 1 --> Lose 
1 1 1 --> Lose 
etc. 

2 --> Win 
2 2 --> Lose 
2 2 2 --> Win 
2 2 2 2 --> Lose 
etc. 

3 --> Win 
3 3 --> Lose 
3 3 3 --> Win 
3 3 3 3 --> Lose 
etc. 

4 --> Win 
4 4 --> Lose (see tree below) 

        4,4      1's turn 
       / \ 
       / \ 
       /  \ 
      /  \ 
      /   \ 
      2,4   1,4     2's turn 
     /\ \  /\ 
     / \ \  / \ 
     / \ \ / \ 
     1,4 2,2 1,2 1,1  1,2   1's turn   
    /\ \  \   \ 
    / \ \  \   \ 
    1,1 1,2 1,2 1,1  1,1   2's turn 
     / \ 
     /  \ 
     1,1  1,1       1's turn 

Мой способ расчета ли игрок 1 или 2 победит, как

static int Winner(int n, int m) 
{ 
    if(m == 1) 
     return 2; 
    else if(IsPrime(m)) 
     return n % 2 == 0 ? 2 : 1; 
    else 
    { 
     // ... ?? 
    } 
} 

EDIT: Ничего себе, я только что сделал дикое предположение с

static int Winner(int n, int m) 
{ 
    if(m == 1) 
     return 2; 
    else 
     return n % 2 == 0 ? 2 : 1; 
} 

и прошло все тестовые примеры проблемы вызова. Поэтому я «решил» это, не понимая почему.

Answer 1

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

Итак, возьмите случай, когда m не 1, а не просто. Самая быстрая игра заключается в том, чтобы уменьшить все высоты до 1, которые пройдут n ходов. Если количество ходов, оставленных в конце хода, равно и тогда игрок, который двигался, выиграл. Здесь первый игрок выигрывает, если n нечетно.

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

Answer 2

Первое, что следует учитывать, заключается в том, что когда вы уменьшаете башню, разделение ее высоты на один из ее делителей (1 в сторону) подобно удалению одного или нескольких его основных факторов. Если вы представляете высоту каждой башни по списку ее основных факторов, то игра просто становится вариантом Nim. На каждом шагу игрок удаляет один или несколько номеров в одном из этих списков, и игрок выигрывает, когда он удаляет последний (ы).

Пример игры с 2 башнями высотой 6:

Tower 1 (height 6) : 2 3 <- First player removes one 
Tower 2 (height 6) : 2 3 

Tower 1 (height 2) : 2 
Tower 2 (height 6) : 2 3 <- Second player removes one 

Tower 1 (height 2) : 2 <- First player removes one 
Tower 2 (height 2) : 2 

Tower 1 (height 1) : 
Tower 2 (height 2) : 2 <- Second player removes one and wins 

После того, как вы понимаете, что вам просто необходимо знать, как выиграть игру Nim с N куч объектов M. And Nim has been mathematically solved for any number of initial heaps and objects.

Поскольку в вашей игре игрок выигрывает, удаляя последний первичный коэффициент, он похож на «обычную игру» Нима, где игрок выбирает последний объект. В этом случае выигрышная стратегия состоит в том, чтобы закончить каждое движение с помощью nim-sum 0, причем nim-sum является исключительной или количеством объектов в каждой куче. Прочтите страницу Wikipedia для получения дополнительной информации и примеров. Когда nim-sum игры не равно 0, всегда можно сделать ход, который делает его 0. В противном случае это невозможно. Поэтому, начиная игру с 0-й суммой означает, что побеждает первый игрок, иначе побеждает второй игрок.

В вашем случае, если количество башен в начале игры четное, тогда сумма nim-sum равна 0, потому что башни имеют одинаковую высоту, и побеждает первый игрок. В противном случае, если количество башен нечетное, выигрывает второй игрок. Единственное исключение - для высоты 1 (что было бы пустой игрой Nim), что делает второй игрок выигрышным по умолчанию.

Именно поэтому ваше «дикое предположение» сработало.