Author |
Topic: Winning Strategy (Read 2390 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
Winning Strategy
« on: Apr 2nd, 2012, 12:24pm » |
 Quote  Modify
|
A table has two piles of stones, one with m stones in it and another with n stones initially. Two players A and B play a game. In one turn one player can either pick x : 1<= x <= m stones from first pile, or y : 1<= y <= n stones from the second pile, or z : 1 <= z <= min(m,n) stones from both piles. The last player to pick the stone is winner. Device a winning strategy for A if he is starting the game.
|
|
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
nova2358
Newbie
Posts: 3
|
|
Re: Winning Strategy
« Reply #1 on: Apr 3rd, 2012, 9:18am » |
Quote Modify
|
Seems this problem can be solved with Dynamic Programming.
Let F(m,n) denotes whether player A will win with m stones in one pile and n stones in another. So F(m,n) = 1 means A will win and F(m,n) = 0 means B will win.
And we have
F(m,n) = max {
1 - F(m-x,n), 1<=x<= m
1 - F(m,n-y), 1<=y<=n
1- F(m-c,n-c), 1<=c<=min(m,n)
}
The Reason to use 1 - F(m-x, n) is that after A's action, if F(m-x, n) = 1, then B will win, so A will lose. Otherwise F(m-x, n) = 0, so B will lose and A can win.
So we have m*n states, and calculating each states costs roughly O(max(m,n)) time. So the total time Complexity is m*n*O(max(m,n)).
First time to reply a question and I assume you know DP. Tell me if anything is unclear to you.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Winning Strategy
« Reply #2 on: Apr 3rd, 2012, 11:19am » |
Quote Modify
|
on Apr 3rd, 2012, 9:18am, nova2358 wrote:F(m,n) = max {
1 - F(m-x,n), 1<=x<= m
1 - F(m,n-y), 1<=y<=n
1- F(m-c,n-c), 1<=c<=min(m,n)
} |
|
Solving the recurrence relation, the winning strategy can be described pretty easily. WLOG, let m < n.
| hidden: | If you're faced with (m,n) a multiple of (1,2), you lose. If not, you can always put the other player in this losing situation:
- if 2m < n, remove n-2m stones from the larger pile, leaving (m, 2m).
- if 2m > n, remove 2m-n stones from both piles, leaving (n-m, 2n-2m). |
|
|
IP Logged |
|
|
|
nova2358
Newbie
Posts: 3
|
|
Re: Winning Strategy
« Reply #3 on: Apr 4th, 2012, 12:30am » |
Quote Modify
|
on Apr 3rd, 2012, 11:19am, pex wrote:
Solving the recurrence relation, the winning strategy can be described pretty easily. WLOG, let m < n.
| hidden: | If you're faced with (m,n) a multiple of (1,2), you lose. If not, you can always put the other player in this losing situation:
- if 2m < n, remove n-2m stones from the larger pile, leaving (m, 2m).
- if 2m > n, remove 2m-n stones from both piles, leaving (n-m, 2n-2m). |
|
|
How did you come up with this solution?
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Winning Strategy
« Reply #4 on: Apr 4th, 2012, 2:30am » |
Quote Modify
|
on Apr 4th, 2012, 12:30am, nova2358 wrote:| How did you come up with this solution? |
|
The way I always solve this kind of problems  I calculated the first 10*10 values using your recursive formula, noticed the pattern, and then came up with some reasoning to convince myself of the solution.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Winning Strategy
« Reply #5 on: Apr 4th, 2012, 2:32am » |
Quote Modify
|
on Apr 3rd, 2012, 11:19am, pex wrote:
Solving the recurrence relation, the winning strategy can be described pretty easily. WLOG, let m < n.
| hidden: | If you're faced with (m,n) a multiple of (1,2), you lose. If not, you can always put the other player in this losing situation:
- if 2m < n, remove n-2m stones from the larger pile, leaving (m, 2m).
- if 2m > n, remove 2m-n stones from both piles, leaving (n-m, 2n-2m). |
|
|
Looks convincing to me though i haven't verified it yet.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Winning Strategy
« Reply #6 on: Apr 4th, 2012, 5:31am » |
Quote Modify
|
on Apr 4th, 2012, 2:32am, birbal wrote:| Looks convincing to me though i haven't verified it yet. |
|
I don't know exactly where things went wrong, but it's clearly incorrect: (2,4) is winnable by taking 3, leaving (2,1) which loses for player B.
I make the first handful of losing combinations (with everything else winning) to be: (0,0) (1,2) (3,5) (4,7) (6,10) (8,13) (9,15) (11,18) (12,20) where the first number of each pair is the least number not yet listed, and the second number of each pair differs from the first by one more than in the previous pair.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Winning Strategy
« Reply #7 on: Apr 4th, 2012, 5:48am » |
Quote Modify
|
on Apr 4th, 2012, 5:31am, SMQ wrote:| I don't know exactly where things went wrong, but it's clearly incorrect: (2,4) is winnable by taking 3, leaving (2,1) which loses for player B. |
|
:[ That's what I get for considering only half the diagram because of symmetry... Back to the drawing board.
|
| « Last Edit: Apr 4th, 2012, 5:49am by pex » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning Strategy
« Reply #8 on: Apr 4th, 2012, 5:54am » |
Quote Modify
|
on Apr 4th, 2012, 5:31am, SMQ wrote:| I make the first handful of losing combinations (with everything else winning) to be: (0,0) (1,2) (3,5) (4,7) (6,10) (8,13) (9,15) (11,18) (12,20) where the first number of each pair is the least number not yet listed, and the second number of each pair differs from the first by one more than in the previous pair. |
|
Neat. If you're in one of these positions you clearly can't put your opponent into one of them. So if you can get from any other position to one of these that would prove you always win. Since by construction every number occurs once (if we disregard (0,0) ) either as smallest of largest of a pair, you can always get from a position not in the sequence to one in it, by keeping the smallest and making the largest equal to the other in the losing pair.
Now all we need is a quick way to decide if we're in a winning position and how to find the winning move.
|
| « Last Edit: Apr 4th, 2012, 5:55am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning Strategy
« Reply #9 on: Apr 4th, 2012, 6:20am » |
Quote Modify
|
The first number of each pair seems to be part of the Lower Wythoff sequence http://oeis.org/A000201 , a(n) = floor(n*phi)
So we have the pairs ( k*phi , k*phi2) as losing positions.
To find the winning move from (m,n) with m < n we just need to solve m = k*phi or m = k*phi2, then take the number of stones from n to complete the pair.
|
| « Last Edit: Apr 4th, 2012, 6:22am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Winning Strategy
« Reply #10 on: Apr 4th, 2012, 6:52am » |
Quote Modify
|
on Apr 4th, 2012, 6:20am, towr wrote:| The first number of each pair seems to be part of the Lower Wythoff sequence http://oeis.org/A000201 , a(n) = floor(n*phi) |
|
From that OEIS page: Quote:| a(n) is the unique monotonic sequence satisfying a(1)=1 and the condition "if n is in the sequence then n+(rank of n) is not in the sequence" |
|
So, yes, this is what SMQ described. Well done, you both!
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Winning Strategy
« Reply #11 on: Apr 4th, 2012, 6:54am » |
Quote Modify
|
on Apr 4th, 2012, 6:20am, towr wrote:| To find the winning move from (m,n) with m < n we just need to solve m = k*phi or m = k*phi2, then take the number of stones from n to complete the pair. |
|
We need one more case for when m is Lower Wythoff but we would need to add stones to n to make the pair, e.g. (3,4). In that case we need to remove stones from both piles to reach the (n-m)th Wythoff pair.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning Strategy
« Reply #12 on: Apr 4th, 2012, 7:18am » |
Quote Modify
|
So in summary:
if m = k phi2
winning move: (m,n) => (k*phi, m)
if m = k phi and n-m > k
winning move: (m,n) => (m, k phi2 )
if m = k phi and n-m < k
winning move: (m,n) => ((n-m)*phi, (n-m) phi2 )
if m = k phi and n-m = k
you lose.
|
| « Last Edit: Apr 4th, 2012, 7:19am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Winning Strategy
« Reply #13 on: Apr 4th, 2012, 8:03am » |
Quote Modify
|
Here's how I came up with the pattern in the first place: X is a losing position, lines denote legal moves, so everything connected by a line to an X is a winning position. (I used graph paper rather than ASCII art, but you get the idea.)
0 1 2 3 4 5 6 7 8 9
0 X
|\
1 | \
| \
2 | X-\
| |\|\
3 | | \ \
| | |\ \
4 | | | \ \
| | | \ \
5 | | | X-\-\
| | | |\ \|\
6 | | | | \ \ \
| | | | \|\ \
7 | | | | X-\-\-\
| | | | |\|\ \|\
8 | | | | | \ \ \ \
| | | | | |\ \|\ \
9 | | | | | | \ \ \ \
| | | | | | \|\ \ \
etc.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Winning Strategy
« Reply #14 on: Apr 4th, 2012, 9:05am » |
Quote Modify
|
I heard of this problem before, when I was in high school. I think it was in Scientific American's Mathematical Games.
It was presented as a queen on a larger chessboard. She can move down, left or diagonally down and left. The first player places the queen on the top or right border, then each player in turn makes a move. The one to reach the bottom left wins.
With this representations, the relation with SMQ's graphical solution is quite direct.
At that time, I found an empiric rule to compute m(n), the winning m for a given n.
- d = frac(n*phi) (or frac(n/phi) which is the same)
- if d<1/phi2, m(n) = floor(n/phi) is winning
- if d>1/phi2, m(n) = ceil(n*phi) is winning
- if d=1/phi2, then phi is a rational 
Note: frac = fractional part, floor = round down, ceil = round up.
By "winning" I mean that if you can move to that position, you win.
It is curious that you can use the fractional part to discriminate the "high" and "low" positions. I have no idea why it is so.
|
| « Last Edit: Apr 4th, 2012, 9:31am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print