View Single Post
Old 2009-11-01, 10:23   #3
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

4E916 Posts
Default

Yeah. Here is the secret of the game.
If the player who puts the last ball is the winner, then
player 1 wins if N = 1 to max (mod min+max)
player 2 wins if N = max+1 to min+max (mod min+max)

If the player who puts the last ball is the loser, then
player 1 wins if N = min+1 to min+max (mod min+max)
player 2 wins if N = 1 to min (mod min+max)

In either case, player 1 wins with probability (max)/(min+max)
player 2 wins with probability (min)/(min+max).

Here is the explanation:
If the player who puts the last ball is the winner, then that player who wins must reach N mod (min+max). Maintaining N mod (min+max) is the secret behind the game. If a player puts x balls, (between min and max), then the opponent will put the complement min+max-x, thus maintaining constant. If N mod (min+max) is between min & max, player 1 will acquire it within the first turn itself. If it is 0, then player 1 trivially loses up as player 2 will put complement in first turn itself. If it is max+1, then player 1 should play greater than or equal to max-min+2, otherwise player 2 will acquire max+1 (mod min+max). Player 2 will have to again keep up less than or equal to min (mod min+max) to avoid player 1 seeking max+1 (mod min+max). Going this way, player 2 wins. Also, similar case between max+1 and min+max-1, where player 1 plays higher, player 2 keeps up lower. If N (mod min+max) is less than or equal to min, then similarly player 1 keeps up lower, player 2 keeps up higher. Player 1 wins, within this case.

If the player who puts the last ball is the loser, then the winner must acquire between N-1 and N-min (mod min+max). For N (mod min+max) = min+1 and max+1, player 1 can acquire N-1 within the first turn itself. Between max+2 and max+min, player 1 can acquire something between N-1 and N-min during the first turn. For N = 1 (mod min+max), player 2 will acquire N-1 during the first turn itself, by putting up the complement of whatever player 1 puts. For N between 2 and min (mod min+max), player 2 always wins up, as putting complement will give up something between N-1 and then N-min only, thus.

Nice?

Last fiddled with by Raman on 2009-11-01 at 10:25
Raman is offline   Reply With Quote