wu :: forums
« wu :: forums - Playing with Chips »

Welcome, Guest. Please Login or Register.
Dec 22nd, 2024, 6:41pm

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





   


Posts: 211
Playing with Chips  
« on: Jan 22nd, 2006, 9:12pm »
Quote Quote Modify Modify

Jack and Jill are playing a game with chips, which are initially kept in K piles. A move in the game consists of selecting any of the existing piles and dividing it into 2 piles having unequal number of chips. Jack and Jill play their moves alternately, with Jack playing the first move. The game ends when no move can be made, and the one who makes the last move wins.
(Note that a move can be made only when there is some pile with more than 2 chips.)
 
Given the initial distribution of chips in the K piles, {a1,a2,a3....ak} how can you determine whether Jack has a winning strategy efficiently?
« Last Edit: Jan 22nd, 2006, 11:49pm by inexorable » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re:  Playing with Chips  
« Reply #1 on: Jan 23rd, 2006, 12:49am »
Quote Quote Modify Modify

Reminds me of nim. But I don't know if the solution is similar.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
JocK
Uberpuzzler
*****






   


Gender: male
Posts: 877
Re:  Playing with Chips  
« Reply #2 on: Jan 23rd, 2006, 1:28pm »
Quote Quote Modify Modify

on Jan 23rd, 2006, 12:49am, towr wrote:
Reminds me of nim.

 
Indeed. Just map the game-configuration on a configuration of Nim heaps. That means that each pile of n chips is mapped onto a Nim-heap of height G(n).  
 
As a result, the Nim-value for k piles of n1, n2, .. , nk chips is simply the Nim-sum G(n1) & G(n2) & .. & G(nk). [Here "&" stands for Nim-addition.]  
 
To calculate for n = 1, 2, 3, ... the Nim-values G(n) for a piles containing n chips, one uses the "Mex rule" applied to all configurations that can result after a move: G(n) = Mex(G(n-1) & G(1), G(n-2) & G(2), .. , G(n-k) & G(k))
 
If the Nim sum for a certain configuration is zero, it is a previous player win.
 
Applying the above to the game at hand, I assume a simple rule will emerge...?
 
(Too lazy to try...  Tongue )
 
 
 
 
« Last Edit: Jan 23rd, 2006, 1:46pm by JocK » IP Logged

solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.

xy - y = x5 - y4 - y3 = 20; x>0, y>0.
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re:  Playing with Chips  
« Reply #3 on: Jan 23rd, 2006, 4:42pm »
Quote Quote Modify Modify

What the heck is the "Mex" rule? I.e., what is Mex(a,b,c,...,d) = ?
 
This is a function notation I have never encountered before.
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
SMQ
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 2084
Re:  Playing with Chips  
« Reply #4 on: Jan 24th, 2006, 6:27am »
Quote Quote Modify Modify

According to Mathworld, it's the minimum excluded value, so for a set S of non-negative integers Mex(S) is the least non-negative integer not in S.
 
--SMQ
IP Logged

--SMQ

JocK
Uberpuzzler
*****






   


Gender: male
Posts: 877
Re:  Playing with Chips  
« Reply #5 on: Jan 24th, 2006, 9:56am »
Quote Quote Modify Modify

on Jan 23rd, 2006, 1:28pm, JocK wrote:

Applying the above to the game at hand, I assume a simple rule will emerge...?

 
It is easier than I thought:
 
G(1) = 0
G(k) = mod(k+1,3)  (k>1)
 
So only Nim-values of G=0, G=1 and G=2 occur. It follows that one has to count the number of G=1 piles (piles with 3k chips, k>0), and the number of G=2 piles (piles with 3k+1 chips, k>0). If there is an even number of both, the position is a 'cold' position (a losing position for the player about to make a move). In all other cases the position is 'hot' (a win for the next player).
 
One can easily check this yields the correct strategy:
 
A G=1 pile can always be formed into two G=0 piles (split 3k into 3k-1 and 1), or into a G=2 and a G=0 pile (split 3k into 3k-2 and 2). Similarly, a G=2 pile can be formed into two G=0 piles (split 3k+1 into 3k-1 and 2), or into a G=1 and a G=0 pile (split 3k+1 into 3k and 1).  
 
It follows that if there is an odd number of G=1 piles and/or an odd number of G=2 piles, the next player can always construct an even number of both. The player who is facing an even number of G=1 and G=2 piles can not leave behind an even number of both piles. (Why?) Hence, the player who is not facing an even number of both piles can always play such that te other player keeps facing an even number of both piles. This continues till the other player is facing piles of size 1 and 2 only (a configuration with zero G=1 and G=2 piles).
 
 
 
 
 
IP Logged

solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.

xy - y = x5 - y4 - y3 = 20; x>0, y>0.
JocK
Uberpuzzler
*****






   


Gender: male
Posts: 877
Re:  Playing with Chips  
« Reply #6 on: Jan 25th, 2006, 1:17pm »
Quote Quote Modify Modify

on Jan 24th, 2006, 9:56am, JocK wrote:

 
It is easier than I thought:
 

 
It isn't..!  Shocked  Embarassed
 
 
 
Sorry folks, made an error in the calculation of the Nim-values. When correcting the error it follows that:
 
1) Nim-values larger than 2 do occur
 
2) The Nim-values no longer repeat with period 3
 
This all makes the problem really tedious. To judge whether a configuration is a win for the next player or not, I doubt whether one can do better than keeping a table of nim-values G(n), and executing a Nim-addition for the G(n)'s. (See my first post)
 
 
For those who want to take this problem further, the corrected Nim-values up to n=30 are:
 
G(1) = G(2) = G(4) = G(7) = G(10) = G(20) = G(23) = G(26) = 0
 
G(3) = G(6) = G(9) = G(12) = G(15) = G(28 ) = 1
 
G(5) = G(8 ) = G(11) = G(14) = G(17) = G(29) = 2
 
G(13) = G(16) = G(19) = G(22) = G(25) = G(30) = 3
 
G(18 ) = G(21) = G(24) = G(27) = 4
 
« Last Edit: Jan 25th, 2006, 1:20pm by JocK » IP Logged

solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.

xy - y = x5 - y4 - y3 = 20; x>0, y>0.
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