Nim variant with two piles where in each turn the sum of their sizes gets reduced by three

Question

So in this game we have two piles of size n and m respectively. Two players take turns, in each turn the player chooses one pile to reduce its size by 2 and the other gets reduced by 1. For example for n=4 and m=5 the only valid moves are: (n=2, m=4) or (n=3, m=3). The player that cannot make a valid move wins (can't reduce the sum of the sizes by 3). What is the winning strategy based on n and m?.

I've created a 8 by 7 table where i mark each position as P (losing move) or N (winning move). I came up with these winning positions:

• (1, X), for X in [2, 7].
• (4, 5), (4, 6), (4, 7).
• (5, 5), (5, 6).
• (7, 4).
• (8, 4), (8, 7).

I've been trying to find the pattern. I tried checking their difference or their parities but there doesn't seem to be any true pattern there. I also tried converting each coordinate into binary and XOR but that didn't give me anything.

Answer 1

You had the right idea filling out a 10 by 10 table. Everything you said is a winning position is indeed winning. However, you did not list all of the winning positions in the $8\times 7$ table, so you either made mistakes, or have not shown all your work. I cannot tell what you have done so far, so I will start from the ground up.

Recall the rules:

• If all of a position's options are winning, or there are no options, then that position is losing. This is because you either have no moves, or your are forced to hand your opponent a winning position. A losing position is also called a $P$-position, meaning that it favors Previous player.

• If a position has at least one losing option, then it is winning. The winning strategy is to select that losing option, which forces your opponent to lose. A winning position is also called an $N$-position, meaning it favors the Next player.

Let me explain. You were correct that $(1,x)$ is winning when $x\ge2$. Furthermore, $(1,1)$ is losing, as there are no options.

• Next, look at (2,2). Both of its options, (1,0) and (0,1), are losing. Therefore, (2,2) is winning.

• Similarly, $(2,x)$ is winning when $x\ge 3$. The winning move is to $(0,x-1)$.

• Next, we look at $(3,3)$. Its options are $(1,2)$ and $(2,1)$, which we previously determined are losing.

• Similarly, you can see that $(3,x)$ is losing when $x\ge 4$, because both $(1,x-1)$ and $(2,x-2)$ were both determined to be winning.

• Next, we look at $(4,4)$. The two options are $(2,3)$ and $(3,2)$. Both of these are winning, so $(4,4)$ is losing.

• Next, we look at $(4,5)$. This has a winning move to $(3,3)$, because $(3,3)$ is losing, so $(4,5)$ is winning. Similarly, you can show that $(4,x)$ is winning for all $x\ge 5$.

Here is the correctly filled out table, so far. I have also included the cases where one of the piles is zero, as these arise in the game.

$$ \begin{array}{c|cccccccccc} & 0&1&2&3&4&5&6&7&8&9&10 \\\hline 0 & P&P&P&P&P&P&P&P&P&P&P& \\ 1 & P&P&N&N&N&N&N&N&N&N&N& \\ 2 & P&N&N&N&N&N&N&N&N&N&N& \\ 3 & P&N&N&P&P&P&P&P&P&P&P& \\ 4 & P&N&N&P&P&N&N&N&N&N&N& \\ 5 & P&N&N&P&N \\ 6 & P&N&N&P&N \\ 7 & P&N&N&P&N \\ 8 & P&N&N&P&N \\ 9 & P&N&N&P&N \\ 10 & P&N&N&P&N \end{array} $$

Now, here is the task for you:

1. Fill out the rest of this table. Remember, for each entry, you need to check its two options. For the entry $(x,y)$, you need to check $(x-1,y-2)$ and $(x-2,y-1)$. If these are both winning (both $N$), then $(x,y)$ is losing ($P$). If at least one is losing (at least one $P$), then $(x,y)$ is winning ($N$).

2. Find a pattern in the table entries. Describe it in words, or mathematically.

3. Prove that the pattern holds forever, by giving a winning strategy for all $(x,y)$ which the pattern says are $N$. This is the hard part. You need to find some "property" that all of the $P$-positions have, but none of the $N$-positions do. You then need to prove two things:

   • Every $N$-position has a $P$ option. That is, for every posiiton without the "property", one of its options does have the "property".

   • Every $P$ position has no $P$ options. That is, for every position with the property, none of its options have the "property".

Solution

I encourage you to attempt to solve the question without reading below, and then use below to check your work, or if you are horribly stuck.

The pattern that emerges is this: a square $(x,y)$ is a $P$-position if and only if $\min(x,y)$ is a multiple of $3$, or if $(x,y)$ is of the form $(3k+1,3k+1)$ for some $k\in \mathbb Z$.

Suppose that $\min(x,y)$ is not a multiple of $3$, and $(x,y)\neq (3k+1,3k+1)$. WLOG, $x\le y$, so $x$ is not a multiple of $3$, and the remainder of $x$ when divided by $3$ is $1$ or $2$. The winning move is the one which reduces $x$ by its remainder. This obviously leaves a multiple of $3$ for the new $x$. Furthermore, the new $y$ will still be greater than or equal to $x$ (here is where we need to use the fact that $(x,y)\neq (3k+1,3k+1)$ for some $k\in \mathbb Z)$.

We have now shown that all positions without the property are $N$-positions. Conversely, suppose we have a position $(x,y)$ with the property. These are two cases:

• If $\min(x,y)$ a multiple of $3$, then any move will make it so $\min(x,y)$ is not a multiple of $3$. Furthermore, it is impossible to move from somewhere where $\min(x,y)$ is a multiple of $3$ to somewhere of the form $(3k+1,3k+1)$.

• If $(x,y)=(3k+1,3k+1)$, you can similarly check that you cannot move to any square $(x',y')$ where $\min(x',y')$ is a multiple of $3$ or $(x',y')=(3k+1,3k+1)$.