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.

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.

share|improve this question
2  
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. –  joriki Mar 30 '13 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.

share|improve this answer

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.