Author |
Topic: Southeast (Read 849 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
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.
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 31st, 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 1st, 2003, 1:47pm » |
 Quote  Modify
|
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:
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 ...
|
|
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 1st, 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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print