mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2009-10-30, 14:32   #1
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default 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
Raman is offline   Reply With Quote
Old 2009-10-30, 15:36   #2
axn
 
axn's Avatar
 
Jun 2003

112548 Posts
Default

1. compute N mod (min+max)
2. ?????
3. Profit!!!!
axn is online now   Reply With Quote
Old 2009-11-01, 10:23   #3
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

125710 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
Reply

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

All times are UTC. The time now is 03:06.

Sat Nov 28 03:06:45 UTC 2020 up 79 days, 17 mins, 3 users, load averages: 1.04, 1.10, 1.09

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.