## Paper and Puzzle a Day 3

Early post to an early morning of paper reading.

First, the paper: I’ve been reading into the following paper for the past week or so: Parallel Graph Decompositions Using Random Shifts. One of the cool ideas from the paper is the use of sampling from the exponential distribution to determine cluster size. Turns out one can find some pretty strong expected bounds on diameter and number of edges between clusters by doing the analysis over the exponential distribution.

Now for the puzzle, this is another variant of the Prisoners’ Hats puzzles (which I am particularly fond of). I’ve never heard of this variant before, so hopefully, most of you have also not heard of it before:

3 prisoners can see each other and the hats on the other prisoners’ head. One prisoner is behind a screen and cannot see the other prisoners (and the other prisoner also cannot see her). There are 3 hats of one color and 1 hat of the other color. At least one of the prisoners must guess the hat on their head correctly in order for all the prisoners to be released. How can they ensure they go free?

Lastly, the answer to yesterday’s puzzle is given below (highlight to see the answer):

If you’ve seen rot2 or rot3, this is rot13, which replaces each letter with the one that is 13 places in front or in back of it. rot13 is special because it is self-invertible since we have 26 letters in the alphabet. The specific answer to yesterday’s puzzle is then:

well, welcome to the world of encryption