You are one of k prisoners in a jail with k indistinguishable cells arranged in a circle, so that each cell has exactly two neighbors. Every day the warden re-arranges which cells the prisoners are put in; each prisoner has no information about the rearrangement, even whether they are in the same cell from the previous day or any way of leaving information in their cell for the next occupant. Every night each prisoner can communicate a single bit of information to the occupant of the cell to your right by turning on or off their light; this is done simultaneously. Your goal is determine k. Before the first day you devise a strategy which is distributed to the other prisoners, who will follow your procedure exactly, and to the warden, who will choose re-arrangements to defeat your strategy if possible. Show a strategy which is guaranteed to get the correct value of k in finite time. (Note that your strategy can (and must) distinguish you from the other prisoners, but the other k - 1 prisoners are indistinguishable from each other.) (20 hours)
Variant by Eric (I don't know the answer): What if you are not one of the prisoners (so there is no distinguished prisoner), but each of the prisoners is given access to an independent source of random numbers? Is there a strategy that finds the correct value in expected value finite time?
Given that
equals ln(2), what is
equal to? (2 minutes)