In an effort to help me get back in the swing of posting regularly on this blog, I will introduce a new initiative to post one paper which I find to be the most interesting paper I encountered that day. I will also post a puzzle whose solution will be posted the following day. Let’s start with the puzzle.
Paper: I recently read a paper on a dynamic programming approach to finding the optimal prefix-free code for unequal letter costs. The algorithm had some clever components, the most important of which is creating a “full” prefix tree by assigning zero probability to some branches. You can find a link to this paper here. The analysis is somewhat complex but the basic idea is fairly simple. One tests all trees to see which one gives the lowest cost. One may test all the trees by building the trees level by level from the root down.
Puzzle: My favorite types of puzzles are those involving prisoners and hats. Here’s a lesser known variant (direct quote from Wikipedia):
“The jailer puts three of the men sitting in a line. The fourth man is put behind a screen (or in a separate room). He gives all four men party hats (as in diagram). The jailer explains that there are two red and two blue hats; that each prisoner is wearing one of the hats; and that each of the prisoners only see the hats in front of him but not on himself or behind him. The fourth man behind the screen can’t see or be seen by any other prisoner. No communication between the prisoners is allowed.
If any prisoner can figure out and say to the jailer what color hat he has on his head all four prisoners go free. If any prisoner suggests an incorrect answer, all four prisoners are executed. The puzzle is to find how the prisoners can escape, regardless of how the jailer distributes the hats.”
Enjoy, and for the sake of puzzle enjoyment, please don’t look up the solution on Wikipedia.
Sublime Illusions 