Проблема с монетами: количество способов выиграть, если на входе 7

Question

Я работаю над проблемой классической игры с монетами:
Алиса и Боб играют в игру, используя кучу монет. Игроки по очереди выбирают несколько монет из связки. Каждый раз, когда игрок может выбрать 1, 2 или 4 монеты, и игрок, который получает последнюю монету, становится победителем. Алиса выбирает первое.
Я на самом деле не понимаю, как получается результат.

    coinGame(1)= ('Alice', 1)
    coinGame(2) = ('Alice', 1)
    coinGame(3) = ('Bob', 2)
    coinGame(4) = ('Alice', 3)
    coinGame(5) = ('Alice', 2)
    coinGame(6) = ('Bob', 6)
    coinGame(7) = ('Alice', 8).

Я понимаю результат 1,2,3 ... 6, но я не понимаю7 и далее.
Для ввода 6, поскольку Алиса всегда будет достать монеты 2, 4 и 5. Поэтому Бобу просто нужно выбрать любой из 1, 2 или 4, чтобы выиграть игру. Общий путь составляет 1 + 3 + 2 = 6. Для ввода 7 Боб может набрать 3 и 6, а затем Алиса просто выбрать 4 или 1 монету, чтобы выиграть игру с 2 + 6 = 8 способов выиграть. Чего я не понимаю, так это того, что для ввода 7 Алиса также может набрать 5, тогда Боб просто выбирает 2, чтобы выиграть. Почему мы проигнорировали это дело и считаем Алису победой?

Надеюсь, я смогу получить некоторые разъяснения.

Спасибо!

Answer 1

Один ключевой пункт
Если Боб выигрывает игру, то есть несколько стратегий, когда человек, начинающий игру, может проиграть.
Если Алиса выигрывает игру, выигрывает тот, кто начинает игру.

Таким образом, из каждого N проверяется, есть ли какая-либо выигрышная позиция Боба в N-1, N-2 и N-4. если да, то Алиса собирается выиграть с суммой позиций, на которых выигрывает Боб.

Если Алиса выигрывает с N-1, N-2 и N-4, то Алиса определенно собираетсяпроиграть эту игру от N.
Поскольку человек, начинающий игру с позиций N-1, N-2 и N-4, выигрывает игру. Когда Алиса передаст ход Бобу, Боб получит только один в N-1, N-2 и N-4. И человек, начинающий игру с этих позиций, собирается выиграть игру.

N>=5
sum=0
if Bob wins in N-1
    sum+=coinGame(N-1).count
if Bob wins in N-2
    sum+=coinGame(N-2).count
if Bob Wins in N-4 
    sum+=coinGame(N-4).count

if sum==0
   Bob wins with coinGame(N-1).count + coinGame(N-2).count + coinGame(N-4).count
else
   Alice wins with sum

Поиск coinGame (7)
Данный coinGame (3) = ('Bob', 2) 7-4
coinGame (5) =(«Алиса», 2) 7-2
coinGame (6) = («Боб», 6) 7-1

Боб выигрывает игру с 6 со счетом 6 и с 3со счетом 2
Таким образом, Алиса выиграет игру с 7 счетом 8