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.

Here is a variation of a Nim game : consider a full set of cuisenaire rods - 10 rods of all integer lengths between 1 and 10. Set a number N between 1 and 54. Player 1 choose one of the 10 rods and place it between the two players. Player 2 choose one of the remaining 9 rods and put it following the first one. Player 1 choose one of the remaining 8 rods and place it following the second one, and so on. The loser of the game is the player that place a rod such that the sum of the lengths is greater than N.

Quite strangely, determining whether player 1 wins or loses may be very easy or quite difficult with respect to N. Do you know anything about this game? I can't say that I invented it as I am sure that someone else has already studied it but I don't know where to search. Thanks by advance for your comments :)

share|improve this question
    
Where do the $44$ come from? –  Christian Blatter Jul 29 '13 at 15:17
    
I think it's supposed to be $54$. $1+2+3+\ldots+10=55$, so for $N>54$ there's no win condition. –  Daniel Franke Jul 29 '13 at 15:44
    
Sorry, the upper bound is actually 54 –  Julien Jul 29 '13 at 15:48
    
This looks hard in general, because a position depends not only on the sum of the lengths already played, but on the exact subset of rods that remain unplayed. But with only ten rods, there are just 1024 possible positions, which could easily be handled by a computer search. –  TonyK Jul 29 '13 at 15:54
    
Of course this is a finite game with not so many possibilities for a computer, but it seems to be not so easy for a human player to deal with those... –  Julien Jul 29 '13 at 16:56

1 Answer 1

Clearly the first player wins any game with $N \lt 11$. The second player wins $11, 12$ ($12$ by playing $10$ if the first player starts with $1$). First wins $13,14$ by playing $1$.

First wins $54$. Second wins $53$ by playing $1$ and $52,51$ by playing $1,2,3$

In between it gets harder.

share|improve this answer
    
It's still easy for multiples of 11 as the second player can always play the complement to 11. I think your guess works fine for 50 too. –  Julien Jul 29 '13 at 16:33
    
That is right for multiples of 11. And for 50 second has to play 4 in addition, but can do so. –  Ross Millikan Jul 29 '13 at 16:48
    
Just one additional comment concerning 12 : as you mention it, it's a losing position, but one has to consider the case where the first player plays 6 and the second player cannot play the complement to 12, its only winning move is 3. –  Julien Jul 29 '13 at 16:54
    
As far as I have studied the problem, the only "easy algorithms" not studied yet are 14 and 18 that gives a win for the first player as he can play 7 (resp. 9) and then reply a complement to 7 (9). This idea does not work with 16 as the second player can play 4 in reply to 8 and first player cannot end the game with 4. –  Julien Jul 29 '13 at 17:02
    
If you want to experiment with it, I wrote a program (just for fun) that you can download here simulating the game. (In addition to being able to change the length limit, you can also change the number of rods it uses.) –  AJMansfield Jul 29 '13 at 18:14

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.