Author 
Topic: Southeast (Read 883 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Southeast
« on: Mar 31^{st}, 2003, 10:34am » 
Quote Modify

The southeast puzzle is played on a semiinfinite chessboard, starting at its northwest (top left) corner. There are three rules: 1. In the starting position, one piece is placed in the northwestmost 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. 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: What does this puzzle have to do with data compression? Hint 2: Symbol codes. Author: Physicist David MacKay, from his book Information Theory, Inference, and Learning Algorithms.

« Last Edit: Mar 31^{st}, 2003, 10:34am by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Southeast
« Reply #1 on: Apr 1^{st}, 2003, 1:47pm » 
Quote Modify

Here is perhaps a better question: Can you clear the first six NorthWesterly squares? A proof that you can't clear the first ten is given below: 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 NorthWesterly squares is 3.25. Thus, even with all the other squares filled, you couldn't possibly clear the ten NorthWesterly squares. However, the sum of the first six NorthWesterly squares is only 2.75 ...


IP Logged 
Doc, I'm addicted to advice! What should I do?



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Southeast
« Reply #2 on: Apr 1^{st}, 2003, 7:02pm » 
Quote Modify

Good question, but the answer is still no. Proof: 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. Everyone will breath a sigh of relief to know that you CAN empty the NW most 3 squares!


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



