Задача: Камни

Условие:

На столе изначально лежат $N$ камней. За ход игрок может взять

• $1$ или $2$ камня, если текущее число камней делится на $3$;
• $1$ или $3$ камня, если текущее число камней при делении на $3$ дает остаток один;
• $1$, $2$ или $3$ камня, если текущее число камней при делении на $3$ дает остаток два.

Каждый ход можно сделать при наличии достаточного количества камней. Проигрывает тот, кто хода сделать не может.

Разбор решения:

Это один из примеров игровых задач на динамику. Чтобы понять принцип решения, давайте решим сначала более простую задачу, разновидностью которой являются «Камни»:

На столе лежит $N$ палочек. Каждый из двух игроков ходит по очереди. В свой ход игрок берет одну или две палочки. Проигрывает тот, кто взял последнюю палочку. По заданному числу палочек $N$ выведите номер игрока, у которого есть выигрышная стратегия.

Рассмотрим саму концепцию этой игры. Если первым ходит игрок $1$, то задача игрока $1$ – поставить игрока $2$ в такую ситуацию, в которой сам игрок $1$ проиграет. Для большего понимания рассмотрим ситуацию:

На столе лежат четыре палочки. Игрок $1$ точно знает, что если бы на столе лежало три или две палочки, он бы выиграл сам, но сейчас он проиграет. Он может взять только одну или две палочки, и тогда на столе останется три или две соответственно. Но после того, как игрок $1$ сделал свой ход, ход делает игрок $2$, и уже он игрок $1$. В зависимости от ситуации новый игрок $1$ берет одну или две палочки и оставляет игроку $2$ последнюю палочку, так как он на выигрышной позиции.

Составим выражение, значение которого – правда, если игрок $1$ выигрывает, и ложь иначе:

\[M_N = \neg M_{N - 1} \lor \neg M_{N - 2}\]

То есть игрок $1$ выигрывает только в том случае, если он проигрывает при количестве палочек, меньшем на $1$ или $2$, и проигрывает, если при количестве палочек, меньшем на $1$ или $2$, выигрывает.

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

\[\begin{equation} M_N=\begin{cases} \neg M_{N - 1} \lor \neg M_{N - 2}, & \text{$N \mod 3 = 0$}.\\ \neg M_{N - 1} \lor \neg M_{N - 3}, & \text{$N \mod 3 = 1$}.\\ \neg M_{N - 1} \lor \neg M_{N - 2} \lor \neg M_{N - 3}, & \text{$N \mod 3 = 2$}. \end{cases} \end{equation}\]

($mod$ – остаток от деления левого операнда на правый, $\neg$ – логическое не, $\lor$ – логическое или)

Выходит, что заолненная по этой формуле таблица выглядит так:

$n$	1	2	3	4	5	6	…
решение	true	true	false	true	true	false	…

Из формулы следует, что нам нужно три проверки на делимость $N$ на $3$. В таблицу запишем значения для $N = 1$ и $N = 2$.

memory = {1: True, 2: True}

Напоминаю, что функция вернет true, если при заданном количестве палочек выигрывает игрок $1$. Дальше просто программируем выведенную формулу:

    memory = {1: True, 2: True}
    
    def win(n):
        if n in memory:
            return memory[n]
        else:
            if n % 3 == 0:
                    if not win(n - 1) or not win(n - 2):
                        memory[n] = True
                        return memory[n]
            if n % 3 == 1:
                    if not win(n - 1) or not win(n - 3):
                        memory[n] = True
                        return memory[n]
            if n % 3 == 2:
                    if not win(n - 1) or not win(n - 2) or not win(n - 3):
                        memory[n] = True
                        return memory[n]
        return False

Если окажется, что ни одно из условий не будет удовлетворено (у игрока $1$ нет никакой выигрышной стратегии), то функция вернет false (последняя строка).