[Math] Stone picking puzzle

combinatorial-game-theorycombinatoricspuzzle

Two players are playing a stone picking game. The players pick a stone from two pile of stone in turn. One can choose to pick any number of stones from either pile, or pick the same number of stone from both piles in one turn. The one who picks the last remaining stone is the winner. For given $m$ and $n$ denoting the number of stones in piles $A$ and $B$, respectively, at the initial positions, determine whether the one who picks the stones first will win the game.

NOTE: The two players are very smart; they both make the optimal decisions.

Best Answer

This is known as Wythoff's game.

The losing positions are $(\lfloor n \varphi\rfloor, \lfloor n \varphi^2\rfloor)$ where $\varphi$ is the golden ratio.

An interesting way of presenting this game is to have the players move a Queen on a chessboard, which you can find at cut-the-knot here.