A two player game is played on a 5×5 grid. A token starts in the bottom left corner of the grid. On each turn, a player can move the token one or two units to the right, or to the leftmost square of the above row. The last player who is able to move wins.Two wise men decide that they want to make the game more interesting and instead of playing with a single token, they will play with two tokens, one red, and one blue, and on a turn a player moves either of the tokens. They also decided that the tokens will start in random positions on the board. Of the 25×25=625 possible starting positions for the 2 tokens, how many of these are winning positions for the first player if he plays optimally?note:Both tokens are allowed to be on the same square at any point during the game.

  • 3
    $\begingroup$ We often get titles that don't correspond to the body of the question, and tags that have nothing to do with the question, but I think this is the first time that I see the title, the tag and the body taken from three different fields and being entirely unrelated. $\endgroup$
    – joriki
    Mar 30, 2013 at 14:50

1 Answer 1


This can be solved using Sprague–Grundy theory. The nimbers for the game with a single token can be filled in starting from the top right and moving left, then down:

$$ \begin{array}{ccccc} \\ 1&0&2&1&0\\ 2&0&3&2&0\\ 1&0&3&1&0\\ 2&0&3&2&0\\ 1&0&3&1&0 \end{array} $$

There are $10$, $6$, $5$ and $4$ of the four different nimbers, and a starting position in the game with two tokens is a losing position iff the XOR of the nimbers for the two tokens is $0$, that is if they are equal, and this is the case for $10^2+6^2+5^2+4^2=177$ positions, so there are $625-177=448$ winning positions.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .