wu :: forums « wu :: forums - Southeast » Welcome, Guest. Please Login or Register. May 28th, 2024, 6:54am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Grimbal, ThudnBlunder, william wu, Icarus, SMQ, Eigenray, towr)    Southeast « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Southeast  (Read 883 times)
william wu

Gender:
Posts: 1291
 Southeast   « on: Mar 31st, 2003, 10:34am » Quote 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

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

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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »