wu :: forums
« wu :: forums - Southeast »

Welcome, Guest. Please Login or Register.
Oct 11th, 2024, 4:31am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: SMQ, ThudnBlunder, Icarus, Grimbal, william wu, Eigenray, towr)
   Southeast
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Southeast  (Read 924 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Southeast  
« on: Mar 31st, 2003, 10:34am »
Quote Quote Modify Modify

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
*****





   
Email

Gender: male
Posts: 949
Re: Southeast  
« Reply #1 on: Apr 1st, 2003, 1:47pm »
Quote Quote Modify 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: male
Posts: 4863
Re: Southeast  
« Reply #2 on: Apr 1st, 2003, 7:02pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board