7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have replaced the game-theory tag with the combinatorics tag. $\endgroup$ – Aryabhata Apr 21 '11 at 0:19
  • $\begingroup$ @Moron, why? It is a game.... $\endgroup$ – Gerry Myerson Apr 21 '11 at 0:32
  • 1
    $\begingroup$ @Gerry: Feel free to add it back :-) I was under the impression game-theory dealt with nash equilibria etc, but the wiki says more. $\endgroup$ – Aryabhata Apr 21 '11 at 0:35
  • 2
    $\begingroup$ @Moron: More specifically, it's comb'l game theory. $\endgroup$ – Yuval Filmus Apr 21 '11 at 1:02
10
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.