Again, I’ve been slightly lax on posting a puzzle and paper a day. Here I am picking up the slack once again. First, a paper. I’ve been reading up on cache-oblivious algorithms recently. Cache-oblivious algorithms are optimal algorithms that do not depend on hardware parameters such as cache size. The paper that introduced such algorithms was presented at FOCS 1999. The paper presents among other popular cache-oblivious algorithms, funnelsort, which stands out the most in my mind. The paper is somewhat math intensive but is a pretty easy read.
Now, the puzzle:
One hundred prisoners just arrived in prison. The warden tells them that starting tomorrow, each of them will be placed in an isolated cell, unable to communicate amongst themselves. Each cell has a window so the prisoners will be able to count the days. Each day, the warden will choose one of the prisoners uniformly at random with replacement, and place him in a central interrogation room containing only a light bulb with a toggle switch. The light bulb is initially switched off. The prisoner may observe the current state of the light bulb. If he wishes, he may toggle the light bulb. He also has the option of announcing that he believes all prisoners have visited the interrogation room at some point in time. If this announcement is true, then all prisoners are set free, but if it is false, all prisoners are executed. The warden leaves, and the prisoners huddle together to discuss their fate. Can they agree on a strategy that will guarantee their freedom?
The answer to Day 7’s puzzle is the following (highlight to show the answer):
The prisoner who is determined first to go will declare “Red” if she sees 4 blue hats. Otherwise, she declares “Pass.” If she declares “Pass,” then the rest of the prisoners will know that at least one of them has a red hat. Then, the next prisoner will declare “Red” if the prisoner sees all blue hats among the remaining prisoners. Otherwise, the prisoner will declare “Pass.” In this way, only the first prisoner will declare wrong for the only case when all prisoners have blue hats.