Behdad Esfahbod's daily notes on GNOME, Pango, Fedora, Persian Computing, Bob Dylan, and Dan Bern!

Archives

July 2003

August 2003

October 2003

November 2003

December 2003

March 2004

April 2004

May 2004

July 2004

August 2004

September 2004

November 2004

March 2005

April 2005

May 2005

June 2005

July 2005

August 2005

September 2005

October 2005

November 2005

December 2005

January 2006

February 2006

March 2006

April 2006

May 2006

June 2006

July 2006

August 2006

September 2006

October 2006

November 2006

December 2006

January 2007

February 2007

March 2007

April 2007

May 2007

June 2007

July 2007

August 2007

September 2007

October 2007

November 2007

December 2007

January 2008

February 2008

March 2008

April 2008

May 2008

June 2008

July 2008

August 2008

October 2008

November 2008

December 2008

January 2009

March 2009

April 2009

May 2009

June 2009

July 2009

August 2009

November 2009

December 2009

March 2010

April 2010

May 2010

June 2010

July 2010

October 2010

November 2010

April 2011

May 2011

August 2011

September 2011

October 2011

November 2011

November 2012

June 2013

January 2014

May 2015

Current Posts

July 2003

August 2003

October 2003

November 2003

December 2003

March 2004

April 2004

May 2004

July 2004

August 2004

September 2004

November 2004

March 2005

April 2005

May 2005

June 2005

July 2005

August 2005

September 2005

October 2005

November 2005

December 2005

January 2006

February 2006

March 2006

April 2006

May 2006

June 2006

July 2006

August 2006

September 2006

October 2006

November 2006

December 2006

January 2007

February 2007

March 2007

April 2007

May 2007

June 2007

July 2007

August 2007

September 2007

October 2007

November 2007

December 2007

January 2008

February 2008

March 2008

April 2008

May 2008

June 2008

July 2008

August 2008

October 2008

November 2008

December 2008

January 2009

March 2009

April 2009

May 2009

June 2009

July 2009

August 2009

November 2009

December 2009

March 2010

April 2010

May 2010

June 2010

July 2010

October 2010

November 2010

April 2011

May 2011

August 2011

September 2011

October 2011

November 2011

November 2012

June 2013

January 2014

May 2015

Current Posts

Wednesday, July 28, 2004

A Hanoi-like Puzzle
*Someone forced me to write than the solution of this puzzle, so I did. Here it comes: (I wrote in text, not much markup, sorry)*

Part 1. Here is a solution for N=4: (1 means to flip the cup, 0 means not to do)

1111

1111

1010

1111

1100

1111

1010

1111

1000

1111

1010

1111

1100

1111

1010

1111

16 moves

Part 2. We prove that for all powers of 2 there exists a solution and for no other number there exists one. To prove this, we prove three lemmas.

Lemma I. If there exists a solution for n/2, then there exists a solution for n. (n is even)

Lemma II. If there exists a solution for 2n, then there exists a solution for n.

Lemma III. No odd number other than 1 has a solution.

It's easy to see that the three lemmas above result in what we want.

Moreover, it's easy to see that the same sequence always works for all goals, not only the goal with all cups facing up. This is because we can always "xor" the goal with the initial sequence. The point is that, it's always the xor of the goal and the current arrangement which is important. We use this property in our proofs. We consider an arrangement as an array a[0]..a[n-1], and the i'th move of sequence m as m[i][0]..m[i][n-1]. Now the proofs:

Lemma I. If there exists a solution for n/2, then there exists a solution for n. (n is even)

Proof: First, observe that if the initial arrangement is concatenation of two identical length n/2 sequences, then the same winning sequence for n/2 can be used to solve this special n problem, by doubling each move too. In other words, if for the initial sequence we have a[0]..a[n/2-1] == a[n/2]..a[n-1], and m2 is a winning sequence for the problem of a[0]..a[n/2-1], then m is a winning sequence for a[0]..a[n-1] where m has the same number of moves as m2, and each move i of m is composed as:

m[i][0]..m[i][n-1] = m2[i][0]..m2[i][n/2-1],m2[i][0]..m2[i][n/2-1].

This is because after applying such *doubled* moves, and rotation, all the time the first half of the sequence always looks exactly like the second half.

Now, for an arbitrary initial sequence, what do is to do moves that at some time makes the first half and second half of the sequence (table) look the same. This is particularly easy too. All we need to do is to pad the moves from m2 with zeros:

m[i][0]..m[i][n-1] = m2[i][0]..m2[i][n/2-1],000...0(n/2 times)

Note that no matter what the rotation, this move always has the same effect on *the xor of first and second half of the sequence*, and as we noted earlier, that's all that matters. So, at some time between one of these moves, or before the first move or after the last move, we get a sequence with first and second halfs equal. Now we can use the strategy we described before to solve the problem. So, what we do, is to run the second strategy, doing the first strategy completely once between each (and before the first and after the last) move of the second strategy. All we need to check is that none of the moves of the first strategy alter the "xor" of the first and second halfs, so does not conflict with our running second strategy at all. We are done.

The following Python code uses this strategy to solve the problem for powers of 2:

It's easy to see that for n, it takes 2^n moves.

Lemma II. If there exists a solution for 2n, then there exists a solution for n.

Proof: Let m2 be a winning sequence for 2n, then m constructed in the following way is a winning sequence for n:

m[i][j] = m[i][2j] xor m[i][2j+1]

Let's see how it works. For initial arrangement a[0]..a[n-1], we construct the following 2n arrangement, called b, by interleaving the n arrangement with zeros:

b[0]..b[2n-1] = a[0],0,a[1],0,a[2],0,...,a[n-1],0

Now, m2 is a winning sequence for 2n and so wins the game started with this long sequence b too. We play the two games for a and b in parallel, with the exception that we make the move of the genie for the simulated game on sequence b too. This is how we do it: If genie of table a (the real game) rotates the table x turns, we rotate the table b, 2x times. (of course we don't know how much genie turns the table, but we just need to consider this to prove the correctness, the algorithm doesn't need us to know.) Now all we do is to sit back and observe that the following invariant holds for all j, allthe time, for arrangements on table a and b before/after all moves, rotations, etc:

a[j] = b[2j] xor b[2j+1]

For rotations it's obvious, for moves we get because the way we designed our moves. Means, if a.old and b.old are the arrangement of table before i'th move, and a and b are the arrangements for after move i, we know:

a[j] = a.old[j] xor m[i][j]

b[2j] = b.old[2j] xor m2[i][2j]

b[2j+1] = b.old[2j+1] xor m2[i][2j+1]

And:

m[i][j] = m[i][2j] xor m[i][2j+1]

And by induction have:

a.old[j] = b.old[2j] xor b.old[2j+1]

Mixing the all we get what we want:

a[j] = a.old[j] xor m[i][j]

= b.old[2j] xor b.old[2j+1] xor m[i][2j] xor m[i][2j+1]

= b.old[2j] xor m[i][2j] xor b.old[2j+1] xor m[i][2j+1]

= b[2j] xor b[2j+1]

Initially the condition holds, because of the way we constructed b. Since m2 is a winning sequence, at some point b becomes all zero (000000...00), which by our invariant, means that a should be all zeros (000...0) too. We are done.

Lemma III. No odd number other than 1 has a solution.

Proof: Assume by way of contradiction that there exists a finite sequence of moves that guarantees a win. Then there also exists a minimal such sequence, ie. A winning sequence that removing any of its moves will result in a sequence that does not guarantee a win anymore.

Now consider the last move in this minimal winning sequence that contains both zeros and ones, ie. the last move which is not of form 111...1 (the last move cannot be all zeros, otherwise we can remove it, which contradicts the minimality assumption.) This last non-trivial move, by assumption of minimality, cannot be removed. Means that, there are situations that the game is actually played until this particular move; in other words, it is not the case that the game is always finished before this particular move. Consider a game path arriving at this move. Since this sequence guarantees a win, and this is the last non-trivial move, the arrangement of the cups after this moves should be either 000...0 or 111...1; or otherwise we lose the game.

So, no matter how much the genie rotates the table before this move, after the move we get a trivial sequence of 000...0 or 111...1. Now all we need to do is to observe that the ONLY sequences that when xor'ed with another sequence after an arbitrary rotation result in either 000...0 or 111...1 are the 101010...10 or 010101...01. In other words, since the number of cups is odd, the genie can always rotate the table such that after the last non-trivial move, we have an arrangement which is not 000...0 or 111...1, and so we lose. Done.

Part 1. Here is a solution for N=4: (1 means to flip the cup, 0 means not to do)

1111

1111

1010

1111

1100

1111

1010

1111

1000

1111

1010

1111

1100

1111

1010

1111

16 moves

Part 2. We prove that for all powers of 2 there exists a solution and for no other number there exists one. To prove this, we prove three lemmas.

Lemma I. If there exists a solution for n/2, then there exists a solution for n. (n is even)

Lemma II. If there exists a solution for 2n, then there exists a solution for n.

Lemma III. No odd number other than 1 has a solution.

It's easy to see that the three lemmas above result in what we want.

Moreover, it's easy to see that the same sequence always works for all goals, not only the goal with all cups facing up. This is because we can always "xor" the goal with the initial sequence. The point is that, it's always the xor of the goal and the current arrangement which is important. We use this property in our proofs. We consider an arrangement as an array a[0]..a[n-1], and the i'th move of sequence m as m[i][0]..m[i][n-1]. Now the proofs:

Lemma I. If there exists a solution for n/2, then there exists a solution for n. (n is even)

Proof: First, observe that if the initial arrangement is concatenation of two identical length n/2 sequences, then the same winning sequence for n/2 can be used to solve this special n problem, by doubling each move too. In other words, if for the initial sequence we have a[0]..a[n/2-1] == a[n/2]..a[n-1], and m2 is a winning sequence for the problem of a[0]..a[n/2-1], then m is a winning sequence for a[0]..a[n-1] where m has the same number of moves as m2, and each move i of m is composed as:

m[i][0]..m[i][n-1] = m2[i][0]..m2[i][n/2-1],m2[i][0]..m2[i][n/2-1].

This is because after applying such *doubled* moves, and rotation, all the time the first half of the sequence always looks exactly like the second half.

Now, for an arbitrary initial sequence, what do is to do moves that at some time makes the first half and second half of the sequence (table) look the same. This is particularly easy too. All we need to do is to pad the moves from m2 with zeros:

m[i][0]..m[i][n-1] = m2[i][0]..m2[i][n/2-1],000...0(n/2 times)

Note that no matter what the rotation, this move always has the same effect on *the xor of first and second half of the sequence*, and as we noted earlier, that's all that matters. So, at some time between one of these moves, or before the first move or after the last move, we get a sequence with first and second halfs equal. Now we can use the strategy we described before to solve the problem. So, what we do, is to run the second strategy, doing the first strategy completely once between each (and before the first and after the last) move of the second strategy. All we need to check is that none of the moves of the first strategy alter the "xor" of the first and second halfs, so does not conflict with our running second strategy at all. We are done.

The following Python code uses this strategy to solve the problem for powers of 2:

#### BEGIN PYTHON CODE ####

#!/usr/bin/python

import sys

n = int(sys.argv[1])

def solve(n):

if n == 1:

return ['1']

if n%2:

print "impossible"

sys.exit(1)

n2 = n / 2

m2 = solve(n2)

m = []

for x in m2+['']:

for y in m2:

m.append(y*2)

if x:

m.append(x + '0'*n2)

return m

moves = ['1'*n]+solve(n)

for x in moves:

print x

print len(moves), 'moves'

#### END PYTHON CODE ####

It's easy to see that for n, it takes 2^n moves.

Lemma II. If there exists a solution for 2n, then there exists a solution for n.

Proof: Let m2 be a winning sequence for 2n, then m constructed in the following way is a winning sequence for n:

m[i][j] = m[i][2j] xor m[i][2j+1]

Let's see how it works. For initial arrangement a[0]..a[n-1], we construct the following 2n arrangement, called b, by interleaving the n arrangement with zeros:

b[0]..b[2n-1] = a[0],0,a[1],0,a[2],0,...,a[n-1],0

Now, m2 is a winning sequence for 2n and so wins the game started with this long sequence b too. We play the two games for a and b in parallel, with the exception that we make the move of the genie for the simulated game on sequence b too. This is how we do it: If genie of table a (the real game) rotates the table x turns, we rotate the table b, 2x times. (of course we don't know how much genie turns the table, but we just need to consider this to prove the correctness, the algorithm doesn't need us to know.) Now all we do is to sit back and observe that the following invariant holds for all j, allthe time, for arrangements on table a and b before/after all moves, rotations, etc:

a[j] = b[2j] xor b[2j+1]

For rotations it's obvious, for moves we get because the way we designed our moves. Means, if a.old and b.old are the arrangement of table before i'th move, and a and b are the arrangements for after move i, we know:

a[j] = a.old[j] xor m[i][j]

b[2j] = b.old[2j] xor m2[i][2j]

b[2j+1] = b.old[2j+1] xor m2[i][2j+1]

And:

m[i][j] = m[i][2j] xor m[i][2j+1]

And by induction have:

a.old[j] = b.old[2j] xor b.old[2j+1]

Mixing the all we get what we want:

a[j] = a.old[j] xor m[i][j]

= b.old[2j] xor b.old[2j+1] xor m[i][2j] xor m[i][2j+1]

= b.old[2j] xor m[i][2j] xor b.old[2j+1] xor m[i][2j+1]

= b[2j] xor b[2j+1]

Initially the condition holds, because of the way we constructed b. Since m2 is a winning sequence, at some point b becomes all zero (000000...00), which by our invariant, means that a should be all zeros (000...0) too. We are done.

Lemma III. No odd number other than 1 has a solution.

Proof: Assume by way of contradiction that there exists a finite sequence of moves that guarantees a win. Then there also exists a minimal such sequence, ie. A winning sequence that removing any of its moves will result in a sequence that does not guarantee a win anymore.

Now consider the last move in this minimal winning sequence that contains both zeros and ones, ie. the last move which is not of form 111...1 (the last move cannot be all zeros, otherwise we can remove it, which contradicts the minimality assumption.) This last non-trivial move, by assumption of minimality, cannot be removed. Means that, there are situations that the game is actually played until this particular move; in other words, it is not the case that the game is always finished before this particular move. Consider a game path arriving at this move. Since this sequence guarantees a win, and this is the last non-trivial move, the arrangement of the cups after this moves should be either 000...0 or 111...1; or otherwise we lose the game.

So, no matter how much the genie rotates the table before this move, after the move we get a trivial sequence of 000...0 or 111...1. Now all we need to do is to observe that the ONLY sequences that when xor'ed with another sequence after an arbitrary rotation result in either 000...0 or 111...1 are the 101010...10 or 010101...01. In other words, since the number of cups is odd, the genie can always rotate the table such that after the last non-trivial move, we have an arrangement which is not 000...0 or 111...1, and so we lose. Done.

Comments:

Links to this post:

<< Archive

<< Home

We had been blogging trying to find how our world sees game. It has been a lifeline for us. Your site provides some of the best examples of this sort and we will bookmark yours. Another one we found was and appears to be related to yours is game site/blog. It pretty much covers game related stuff.

Post a Comment
Links to this post:

<< Archive

<< Home