Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

1 Answer

up vote 8 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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