FORTNIGHT'S PUZZLE 12

PUZZLE 12: 22nd-28th March (to be e-mailed by the 29th March)
POSTED BY IES CAMPANAR

A BALL GAME
A box holds 40 juggling balls. Two friends are playing a game in which they alternate to pick up balls from the box. When it is their turn each player can take out as many balls as wanted but never more than half the number of balls in the box. The player that cannot take any more balls from the box will lose. Who will be the winner, the first or the second friend to play? And which will be the right strategy to win the game?

SOLUTION
Let us see if there is a winning strategy. If there is one, the winner in his/ her last turn, should leave the other person only one ball as that would make it impossible for the other player to pick up any balls.
And so, going backwards, the winner in the previous movement, should have left the other player with 3 balls. This way the “loser” could only have picked up 1 ball and leave the other 2. (W(n-1) = 2·1 + 1 = 3).
In the same way, in the last-but-one movement, the winner should have left W(n-2) = 2·3 + 1 =7,and in previous turns he/she should have left: W(n-3) = 2·7 +1 = 15, W(n-4) = 2·15 +1 = 31.
However, only the person playing FIRST can get to do that by picking up 9 balls on his/her first movement and leaving in the following 15, 7, 3 y 1 balls.
The winner thus will be the first person to play and to use the strategy explained above.