2009-10-30, 14:32 | #1 |
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3×419 Posts |
Very nice strategical puzzle
This is an excellent strategical puzzle to tune up your brains.
There is a box containing n holes. Two players put balls into these holes alternatively. (Assume that the box contains holes along a straight line, so that you cover up these holes in sequence.) Let player 1 start up with the game. Each player can put between min and max balls into the box in one turn. The person who puts the last ball will be the winner or loser, that is decided and fixed prior to the game, randomly. The values of n, min, max are also decided and fixed prior to the game. For simplicity purposes, let us assume that 20 ≤ n ≤ 50 and then that 1 ≤ min < max ≤ 10. If the person who puts the last ball is the winner, then for what values of n, depending upon min and max, will player 1 win the game, and then for what values of n will player 2 do so? Assume that both the players play so cleverly. Thus, what about the case if the person who puts the last ball is the loser? (If there is less than min slots remaining at the end, then the last player can put less than min balls during his last turn. Otherwise, the minimum number of balls that a player can put up within his turn is min only.) Last fiddled with by Raman on 2009-10-30 at 14:34 |
2009-10-30, 15:36 | #2 |
Jun 2003
1001101100000_{2} Posts |
1. compute N mod (min+max)
2. ????? 3. Profit!!!! |
2009-11-01, 10:23 | #3 |
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
4E9_{16} Posts |
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 |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Nice progress! | schickel | FactorDB | 29 | 2012-07-18 17:03 |
Nice pic | Dubslow | Forum Feedback | 0 | 2012-05-02 02:13 |
Let's do another nice big GNFS job! | fivemack | Factoring | 84 | 2011-04-26 10:22 |
Nice Result! M971 | R.D. Silverman | Factoring | 53 | 2004-10-02 08:54 |
Nice link... | Xyzzy | Lounge | 4 | 2003-06-28 13:37 |