math game help

[zen]

Kolya and Vitya play the following game. There is a pile of 31 stones on the table. The boys take turns making moves and Kolya begins. In one turn a player divides every pile which has more than one stone into two lesser ones. The player who after his turn leaves all piles with only one stone in each wins. Can Kolya win no matter how Vitya plays?

I'm pretty sure that Kolya can't win every game but I would love some help understanding the math behind it. Thanks!

 

[Ishuda]

Kolya and Vitya play the following game. There is a pile of 31 stones on the table. The boys take turns making moves and Kolya begins. In one turn a player divides every pile which has more than one stone into two lesser ones. The player who after his turn leaves all piles with only one stone in each wins. Can Kolya win no matter how Vitya plays?

I'm pretty sure that Kolya can't win all the time but I would love some help understanding the math behind it/strategy involved. Thanks!

Assuming the game is as indicated by Denis, the winner depends on the number of starting stones (or possibly just on parity).

There must be at least three stones to play so start with three stones. The only divisions are equivalent 1,2 [a pile with 1 stone and a pile with 2 stones] or 2,1. In either case player 2 divides the 2 pile and wins. P1 loses

Initially 4 stones. Player 1 divides the stones 1,3 leaving player 2 as the first player in an 'initial 3 stone game' and so player 2 loses. P1 wins

Initially 5 stones. Player 1 can divide the stones [equivalently] only as 2,3 or as 1,4. If the division is 2,3 then player 2 divides the 2 pile leaving player 1 as P1 in a 3 stone game so P1 loses. If player 1 divides the stones 1,4 that leaves player 2 as the first player in a 4 stone game. In either case P1 loses.

Initially 6 stones. Player 1 divides the stones 1,5 leaving player 2 as the initial player in a 5 stone game. P1 wins.
...
So, obviously if P1 must lose the odd numbered stone game, P1 can force a win in the even stone game. Left as an exercise for the interested, P1 must lose the odd numbered stone game.

 

[Ishuda]

P1 : 2........3
P2 :1,1......1, 2
P1 :1,1......1, 1,1
P1 wins

???????Am I missing something?

Sorry, misread the problem. I was thinking only one pile could be divided somewhat like the game of Nim where a player may remove any number of stones provided they come from the same pile.

 

[Limax]

Instead of 31, let's investigate the smallest numbers first and work our way up.

2 stones: WIN

3 stones: LOSE

4 stones: Split into 1 and 3 – WIN

5 stones: Split into 2 and 3 – WIN

6 stones: Split into 3 and 3 – WIN

7 stones: If split into 1 and 6, Vitya splits 6-pile into 3, 3; if into 2 and 5, Vitya splits into 1, 1 and 2, 3; if into 3 and 4, Vitya splits into 1, 2 and 1, 3 – in this case, LOSE

8 stones: Split into 1 and 7 – WIN

9 stones: Split into 2 and 7 – WIN

10 stones: Split into 3 and 7 – WIN

11 stones: Split into 4 and 7 – WIN​

Note that in the last case,, although 4 wins and 7 loses for Vitya, more moves would be needed to clear the pile of 7 than the pile of 4; hence Vitya can never win when presented with piles of 4 and 7. (A pile of 7 takes four moves to be turned into seven 1-stone piles given that the first mover loses.) The same argument applies to the next two cases.

12 stones: Split into 5 and 7 – WIN

13 stones: Split into 6 and 7 – WIN

14 stones: Split into 7 and 7 – WIN

15 stones: LOSE​

If Kolya splits into 8 and 7, Vitya will just split the pile of 8 into 1 and 7. Any other split will not be any better for Kolya: there will always be a lesser pile with more than 7 stones and the other with at most 7 stones, therefore Vitya can always make sure Kolya gets a pile with exactly 7 stones and so loses.

And so the answer to the original question: Can Kolya always win with 31 stones starting first? The answer is NO – it is Vitya who will always win. No matter how Kolya splits the original pile, there will always be a lesser pile with more than 15 stones and the other with at most 15 stones: Vitya can therefore always ensure that Kolya will get a pile of exactly 15 stones and lose.

 

[Limax]

Kolya can always force a win unless the starting number of stones is of the form \(\displaystyle 2^n-1\), n an integer greater than 1. In the latter case, it is Vitya who can always win.