Predict Winner and Optimal Strategy in Substraction Game of 3 Towers

Question

Given the following game, what is the strategy to win?

• There are 3 heaps with m, n, k stones respectively. m, n, k must all be >1 and can be the same.
• At each turn, each player can take either 1 from a single tower or 2 stones from 2 different towers (1 from each tower)
• EDIT: The winner is the person to take the last stone(s). Thus, (0, 1, 1) or (0, 0, 1) are winning positions.

I need to know given a position who is predicted to win and what's the best move to take.

I've been trying to compare this problem with Nim, Substraction Games, Grundy Numbers etc., but the problem is that they are all based on taking an amount larger than 1 from a single tower.

Any help is appreciated. Thanks in advance!

Answer 1

Unfortunately, it turns out simply.
Losing positions are where $(m,n,k)$ are either all even or all odd.
It is more complicated if the last stone loses, I don't have a formula for that.

Answer 2

My reflections up to now : a position is coded $(p,q,r)$, with $p\le q\le r$.

• $(0,0,n)$ leads only to $(0,0,n-1)$, so it's a wining position if $n$ is odd, a loosing one if $n$ is even.
• $(0,1,n)$ leads to $(0,0,n)$, $(0,0,n-1)$ or $(0,1,n-1)$. At least one of this positions is a loosing one, so $(0,1,n)$ is a winning position for all $n\ge1$.
• $(0,2,n)$ can lead to $(0,1,n)$ or $(0,1,n-1)$, one of which is a loosing position, so $(0,2,n)$ is winning for all $n\ge2$.
• $(0,3,n)$ leads to $(0,2,n)$ or $(0,2,n-1)$ which are both winning position, or $(0,3,n-1)$. As $(0,3,3)$ is loosing, $(0,3,n)$ is winning if $n$ is even, loosing if $n$ is odd.
• $(1,1,n)$ can lead to $(0,1,n)$ or $(0,1,n-1)$, one of which is loosing, so $(1,1,n)$ is winning for all $n\ge2$. But $(1,1,1)$ is loosing.

I'll continue until I find a more general result.

Very interesting problem, I'll try it with my classes :-)