## Paper and Puzzle a Day 5

Today marks another paper and another puzzle so let’s get started.

Fractional Cascading is a pretty awesome idea for speeding up searches for the same value in multiple sorted lists. Given $k$ lists, a naive algorithm would take $O(k\log{n})$ time because it would binary search each of the $k$ lists individually. A faster solution provided by fractional cascading allows the search to be conducted in $O(\log{n})$ time by propagating certain half the elements from one list up to the next list and iteratively propagating the elements so that all lists can be searched from one list by following pointers. A more detailed description of the fractional cascading procedure can be found in a variety of online resources including: Wikipedia article, nice notes and video, and more notes!

Now the puzzle, another prisoner’s hats variant because I cannot get enough of these puzzles:

“As before, there are 10 prisoners and 10 hats. Each prisoner is assigned a random hat, either red or blue, but the number of each color hat is not known to the prisoners. The prisoners are distributed in the room such that they can see the hats of the others but not their own. Now, they must each, simultaneously, say only one word which must be “red” or “blue”. If the word matches their hat color they are released, and if enough prisoners resume their liberty they can rescue the others. A friendly guard warns them of this test one hour beforehand and tells them that they can formulate a plan where by following the stated rules, 5 of the 10 prisoners will definitely be released, so that they are able to rescue the others. What is the plan to achieve the goal?”

Slightly tricky because prisoners can no longer communicate with each other. How will you solve this?

Now the answer to Day 4’s puzzle (highlight to see the answer):

The numbers are written in binary, so the obvious first step is to convert the numbers to text (or decimals). Converting the binary to decimals gives a string of numbers:

212832200031263311822067093100

Now, if you count the number of numbers, you see that the number of numbers is a multiple of 10. What does 10 digit numbers tell you?

Turns out that 10 digit numbers signify phone numbers:

212-832-2000 312-633-1182 206-709-3100

These are not just any phone numbers, they are phone numbers for some pretty famous people. If you type these numbers into Google, you’ll see that they are the phone numbers to:

212-832-2000: Donald Trump

312-633-1182: Oprah Winfrey

206-709-3100: Bill Gates