Paper and Puzzle Day 2

Day 2 of my paper and a day promise…

First, a paper: Peter Shor’s contradiction to the triangle conjecture. Recently saw this paper that also conveniently disproved a long standing conjecture that every uniquely decodable code is commutatively equivalent to a prefix-free code (the motivation behind this is to the find a polynomial scheme to the unequal letter cost code problem). The reasons I like this paper are that it is very concise (slightly more than 2 pages) and because I am curious about how the counterexample was found. (If you read the paper, you can see that it’s not at all a trivial example to find.)

Now a relatively simple puzzle:

jryy, jrypbzr gb gur jbeyq bs rapelcgvba.

And as promised the solution to the previous day’s problem is given below (highlight the blank space below to see the solution).

4 prisoners and hats (highlight the blank space below to see the answer):

The solution to this puzzle basically boils down to timing. If the prisoner in the back of the line sees two hats of the same color in front of her, then she would say the opposite color. The next to last prisoner would wait for a response from the last prisoner. If the last prisoner does not say anything, then the second to last prisoner would know that the last prisoner sees hats of different colors in front of her. Then, the second to last prisoner would see the color of the hat of the prisoner in front of him. From this, he may deduce the color of his own hat and guess correctly.

Advertisements
This entry was posted in Paper and Puzzle and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s