wu :: forums - Print Page


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

        riddles >> hard >> Southeast
        
(Message started by: william wu on Mar 31^st, 2003, 10:34am)

Title: Southeast
Post by william wu on Mar 31^st, 2003, 10:34am

The southeast puzzle is played on a semi-infinite chessboard, starting at its northwest (top left) corner. There are three rules:

1. In the starting position, one piece is placed in the northwest-most square, as shown in (a).

2. It is not permitted for more than one piece to be on any given square.

3. At each step, you remove one piece from the board, and replace it with two pieces, one in the square immediately to the East, and one in the the square immediately to the South, as illustrated in (b). Every such step increases the number of pieces on the board by one.

After move (b) has been made, either piece may be selected for the next move. (c) shows the outcome of moving the lower piece. At the next move, either the lowest piece or the middle piece of the three may be selected; the uppermost piece may not be selected, since that would violate rule 2. At move (d) we have selected the middle piece. Now any of the pieces may be moved, except for the leftmost piece.

http://www.ocf.berkeley.edu/~wwu/images/riddles/southeast.gif

Puzzle: Is it possible to obtain a position in which all of the ten squares closest to the northwest corner, marked in the rightmost figure (z), are empty?

Hint 1: [hide]What does this puzzle have to do with data compression?[/hide]

Hint 2: [hide]Symbol codes.[/hide]

Author: Physicist David MacKay, from his book Information Theory, Inference, and Learning Algorithms.

Title: Re: Southeast
Post by James Fingas on Apr 1^st, 2003, 1:47pm

Here is perhaps a better question: Can you clear the first six North-Westerly squares?

A proof that you can't clear the first ten is given below:
[hide]
Give each square a value, starting with 1 for the North West square, 1/2 for the two squares south east of it, 1/4 for the three squares south east of those, etc.

It should be obvious that the sum of the values of the filled squares is always 1. The sum of the values of all the squares is 4, and the sum of the values of the ten North-Westerly squares is 3.25. Thus, even with all the other squares filled, you couldn't possibly clear the ten North-Westerly squares. However, the sum of the first six North-Westerly squares is only 2.75 ...[/hide]

Title: Re: Southeast
Post by Icarus on Apr 1^st, 2003, 7:02pm

Good question, but the answer is still no.

Proof:[hide] Note that there is no way to get more than one dot in the top row or in the leftmost column. Using James' valuation of the squares, this means that in addition to the 2.75 value of the six corner positions, there are empty positions on the top row and the leftmost column that add up to at least .125 each. So the minimum possible total value of the empty squares is 3. Since the total valuation of filled squares is 1, every remaining square must be filled. Since there are an infinite number of squares, that state can never be reached.[/hide]

Everyone will breath a sigh of relief to know that you CAN empty the NW most 3 squares!