Subtraction Game with Two Piles of Stones

137 Views Asked by At

In this subtraction game, there are two piles of stones, and a player can take between 1 and 4 stones from the first pile or between 1 and 5 from the second. I am trying to determine which positions are in the set $P$. This is my attempt so far:

Denote $X$ as the number of stones in the first pile and $Y$ the number of stones in the second. Denote a position in the game as $(X, Y)$. $(0, 0) \in P$ is the terminal position (this is normal play).

Case 1: $X, Y \in P$. Then $X = 5k$ and $Y = 6l$ for $k, l \in \mathbb{N}$. So $(X, Y) \in P$.

Case 2: $X \in P$, $Y \in N$, or vice versa. Then $(X, Y) \in N$.

(I can prove these using induction, I'm just leaving that part out, because here is where I'm stuck):

Case 3: $X, Y \in N$. What I've done is draw out a grid of possible $(X, Y)$ positions and labeled them as $N$ or $P$. This is what my list looks like: $(1, 1), (2, 2), (3, 3), (4, 4), (6, 1), (7, 2), (8, 3), (9, 4), (1, 7), (2, 8), (3, 9), (4, 10), (6, 7), (7, 8), (8,9), (9, 10)$ are all in $P$. I'm trying to generalize this somehow and am struggling to proceed. Any assistance/comments would be much appreciated!