Author |
Topic: Playing with Chips (Read 633 times) |
|
inexorable
Full Member
Posts: 211
|
 |
Playing with Chips
« on: Jan 22nd, 2006, 9:12pm » |
 Quote  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: 
Posts: 13730
|
|
Re: Playing with Chips
« Reply #1 on: Jan 23rd, 2006, 12:49am » |
Quote 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:
Posts: 877
|
|
Re: Playing with Chips
« Reply #2 on: Jan 23rd, 2006, 1:28pm » |
Quote Modify
|
on Jan 23rd, 2006, 12:49am, towr wrote:
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...  )
|
| « 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:
Posts: 4863
|
|
Re: Playing with Chips
« Reply #3 on: Jan 23rd, 2006, 4:42pm » |
Quote 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:
Posts: 2084
|
|
Re: Playing with Chips
« Reply #4 on: Jan 24th, 2006, 6:27am » |
Quote 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:
Posts: 877
|
|
Re: Playing with Chips
« Reply #5 on: Jan 24th, 2006, 9:56am » |
Quote 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:
Posts: 877
|
|
Re: Playing with Chips
« Reply #6 on: Jan 25th, 2006, 1:17pm » |
Quote Modify
|
on Jan 24th, 2006, 9:56am, JocK wrote:
It is easier than I thought:
|
|
It isn't..!  
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.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print