mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   Very nice strategical puzzle (https://www.mersenneforum.org/showthread.php?t=12639)

 Raman 2009-10-30 14:32

Very nice strategical puzzle

[SIZE=3]This is an excellent strategical puzzle to tune up your brains.
[/SIZE]
[SIZE=3]There is a box containing [COLOR=Red][B]n[/B][/COLOR][COLOR=Black] 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 [COLOR=Red][B]min[/B][/COLOR] and [COLOR=Red][B]max[/B][/COLOR] balls into the box in one turn.[/COLOR] The person who puts the last ball will be the [B][COLOR=Red]winner[/COLOR][/B] or [B][COLOR=Red]loser[/COLOR][/B], that is decided and fixed prior to the game, randomly.[/SIZE]

[SIZE=3]The values of [B][COLOR=Red]n[/COLOR][/B], [B][COLOR=Red]min[/COLOR][/B], [B][COLOR=Red]max[/COLOR][/B] are also decided and fixed prior to the game. For simplicity purposes, let us assume that 20 ≤ [B][COLOR=Red]n[/COLOR][/B] [/SIZE][SIZE=3]≤ 50 and then that 1 [/SIZE][SIZE=3]≤ [COLOR=Red][B]min[/B][/COLOR] < [COLOR=Red][B]max[/B][/COLOR] [/SIZE][SIZE=3]≤ 10.

If the person who puts the last ball is the [B][COLOR=Red]winner[/COLOR][/B], then for what values of [COLOR=Red][B]n[/B][/COLOR], depending upon [COLOR=Red][B]min[/B][/COLOR] and [COLOR=Red][B]max[/B][/COLOR], will player 1 win the game, and then for what values of [COLOR=Red][B]n[/B][/COLOR] 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 [COLOR=Red][B]loser[/B][/COLOR]? (If there is less than [COLOR=Red][B]min[/B][/COLOR] slots remaining at the end, then the last player can put less than [COLOR=Red][B]min[/B][/COLOR] balls during his last turn. Otherwise, the minimum number of balls that a player can put up within his turn is [COLOR=Red][B]min[/B][/COLOR] only.)
[/SIZE]

 axn 2009-10-30 15:36

1. compute N mod (min+max)
2. ?????
3. Profit!!!!

 Raman 2009-11-01 10:23

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).

[B]Here is the explanation:[/B]
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 [I]N mod (min+max)[/I] 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?

 All times are UTC. The time now is 17:35.