wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >>  Playing with Chips
        
(Message started by: inexorable on Jan 22^nd, 2006, 9:12pm)

Title: Playing with Chips
Post by inexorable on Jan 22^nd, 2006, 9:12pm

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?

Title: Re: Playing with Chips
Post by towr on Jan 23^rd, 2006, 12:49am

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

Title: Re: Playing with Chips
Post by JocK on Jan 23^rd, 2006, 1:28pm

on 01/23/06 at 00:49:04, 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 n₁, n₂, .. , n_k chips is simply the Nim-sum G(n₁) & G(n₂) & .. & G(n_k). [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... :P )

Title: Re: Playing with Chips
Post by Icarus on Jan 23^rd, 2006, 4:42pm

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.

Title: Re: Playing with Chips
Post by SMQ on Jan 24^th, 2006, 6:27am

According to Mathworld, it's the minimum excluded value (http://mathworld.wolfram.com/Mex.html), so for a set S of non-negative integers Mex(S) is the least non-negative integer not in S.

--SMQ

Title: Re: Playing with Chips
Post by JocK on Jan 24^th, 2006, 9:56am

on 01/23/06 at 13:28:28, 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).

Title: Re: Playing with Chips
Post by JocK on Jan 25^th, 2006, 1:17pm

on 01/24/06 at 09:56:57, JocK wrote:

It is easier than I thought:

It isn't..! :o :-[

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