so I have been working on this problem for several days now. The fact that I can‘t find a solution is driving me crazy. I hope you guys can help me out. Here comes the problem:
Let there be 2022 nuts on the table. Two squirrels, Alice and Bob, take turns eating the nuts. To determine the number of nuts they eat on a given turn, they tip a regular dice over and eat the number that is on top. The last one unable to make a move loses the game. For which starting number a can Bob force a win?
I thank anybody who leaves an answer.
Yours, MathGuy :))))))
We can describe the current game state as $(n,d)$ where $n \in \mathbb{N}$ (including zero) is the number of nuts remaining and $d \in \{1,2,3,4,5,6\}$ is the number on the top face of the die, together with the next player to move. Since the rules are symmetric for Alice and Bob, it will be enough to determine whether each $(n,d)$ is a winning or losing state for the current player, assuming ideal play.
The valid moves are from state $(n,a)$ to state $(n-b,b)$ where $a \neq b$ and $a+b \neq 7$. Note the moves from state $(n,a)$ and $(n,7-a)$ are the same, so those two states are always both winning or both losing. So the discussion below will usually just describe the states $(n,1), (n,2), (n,3)$, since the states $(n,6), (n,5), (n,4)$ respectively act the same. (There are still up to six different possible moves from each state, since they will result in different $n$ values. Just the states before and after moves are combined this way.)
As a base case, $(n,a)$ is a losing state if $n$ is smaller than the minimum possible next die face $b$, meaning there is no valid next move. $(0,a)$ (no nuts left) is always a losing state. If $a=1$ or $a=6$ then $b \geq 2$, so $(1,1)$ is a losing state.
Otherwise, a state is a winning state if ANY next move transitions to a losing state. A state is a losing state if EVERY next move transitions to a winning state.
Now let's look at the set of winning and losing $(n,d)$ for each $n$ value until a pattern is suggested.
$(0,d)$ loses.
$(1,1)$ loses. $(1,2)$ and $(1,3)$ win by stepping to $(0,1)$.
$(2,1)$ and $(2,3)$ win by stepping to $(0,2)$. $(2,2)$ wins by stepping to $(1,1)$.
$(3,1)$ and $(3,2)$ win by stepping to $(0,3)$. $(3,3)$ loses since $(2,1)$ and $(1,2)$ win.
$(4,1)$ and $(4,2)$ win by stepping to $(0,4)$. $(4,3)$ loses since $(3,1)$ and $(2,2)$ win.
$(5,1)$ and $(5,3)$ win by stepping to $(0,5)$. $(5,2)$ loses since $(4,1), (2,3), (1,4)$ all win.
$(6,d)$ can always win by stepping to losing state $(0,6)$ or $(3,3)$. At least one of those must be possible.
$(7,d)$ can always win by stepping to losing state $(1,6)$ or $(3,4)$ or $(4,3)$ or $(5,2)$.
$(8,1)$ and $(8,2)$ win by stepping to $(4,4)$. $(8,3)$ loses since $(2,6), (3,5), (6,2), (7,1)$ all win.
$(9,d)$ loses for any $d$ since $(3,6), (4,5), (5,4), (6,3), (7,2), (8,1)$ all win.
$(10,d)$ can always win by stepping to $(5,5)$ or $(9,1)$.
$(11,d)$ can always win by stepping to $(8,3)$ or $(9,2)$.
$(12,1)$ and $(12,2)$ win by stepping to $(8,4)$ or $(9,3)$. $(12,3)$ loses since $(6,6), (7,5), (10,2), (11,1)$ all win.
$(13,1)$ and $(13,2)$ win by stepping to $(9,4)$. $(13,3)$ loses since $(7,6), (8,5), (11,2), (12,1)$ all win.
$(14,1)$ and $(14,3)$ win by stepping to $(9,5)$. $(14,2)$ loses since $(8,6), (10,4), (11,3), (13,1)$ all win.
$(15,d)$ can always win by stepping to $(9,6)$ or $(12,3)$.
$(16,d)$ can always win by stepping to $(12,4)$ or $(13,3)$ or $(14,2)$.
$(17,1)$ and $(17,2)$ win by stepping to $(13,4)$. $(17,3)$ loses since $(11,6), (12,5), (15,2), (16,1)$ all win.
$(18,d)$ loses for any $d$ since $(12,6), (13,5), (14,4), (15,3), (16,2), (17,1)$ all win.
Looks like the sets of winning $d$ repeat as $n$ increases, with period $9$, starting from $n=3$. Since the future sets of winning $d$ depend only on the previous $6$ sets of winning $d$, the pattern must continue. To be more careful, we could prove by induction that for $n \geq 3$, $(n,d)$ is a losing state if and only if $n \equiv 0 \pmod 9$ or ($n \in \{3,4,8\} \pmod 9$ and $d \in \{3,4\}$) or ($n \equiv 5 \pmod 9$ and $d \in \{2,5\}$).
For the question posed, the initial state before Alice's first move is $(2022, a)$. $2022 \equiv 6 \pmod 9$, so this is a winning state no matter what $a$ is. Alice can always turn the die either to $3$, leaving losing state $(2019,3)$, or to $6$, leaving losing state $(2016,6)$. Unless I've made a mistake or misunderstood the question, Alice can force a win no matter what the value $a$ is, and Bob never can.