wu :: forums
« wu :: forums - Winning Strategy »

Welcome, Guest. Please Login or Register.
Oct 31st, 2024, 4:09pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Eigenray, towr, william wu, Grimbal, Icarus, SMQ, ThudnBlunder)
   Winning Strategy
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Winning Strategy  (Read 2399 times)
birbal
Full Member
***





   


Gender: male
Posts: 250
Winning Strategy  
« on: Apr 2nd, 2012, 12:24pm »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 880
Re: Winning Strategy  
« Reply #2 on: Apr 3rd, 2012, 11:19am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 880
Re: Winning Strategy  
« Reply #4 on: Apr 4th, 2012, 2:30am »
Quote Quote Modify 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 Wink 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: male
Posts: 250
Re: Winning Strategy  
« Reply #5 on: Apr 4th, 2012, 2:32am »
Quote Quote Modify 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: male
Posts: 2084
Re: Winning Strategy  
« Reply #6 on: Apr 4th, 2012, 5:31am »
Quote Quote Modify 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: male
Posts: 880
Re: Winning Strategy  
« Reply #7 on: Apr 4th, 2012, 5:48am »
Quote Quote Modify 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: male
Posts: 13730
Re: Winning Strategy  
« Reply #8 on: Apr 4th, 2012, 5:54am »
Quote Quote Modify 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: male
Posts: 13730
Re: Winning Strategy  
« Reply #9 on: Apr 4th, 2012, 6:20am »
Quote Quote Modify 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: male
Posts: 880
Re: Winning Strategy  
« Reply #10 on: Apr 4th, 2012, 6:52am »
Quote Quote Modify 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: male
Posts: 2084
Re: Winning Strategy  
« Reply #11 on: Apr 4th, 2012, 6:54am »
Quote Quote Modify 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: male
Posts: 13730
Re: Winning Strategy  
« Reply #12 on: Apr 4th, 2012, 7:18am »
Quote Quote Modify 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: male
Posts: 2084
Re: Winning Strategy  
« Reply #13 on: Apr 4th, 2012, 8:03am »
Quote Quote Modify 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: male
Posts: 7527
Re: Winning Strategy  
« Reply #14 on: Apr 4th, 2012, 9:05am »
Quote Quote Modify 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 Smiley
 
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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board