mathematics - Three mathematicians are forever in Prison

I'm excited to share the following riddle. It was given to me more than two years ago and I finally solved it last summer (after not thinking about it for a long time). In my desperation, I tried to find a solution online, but couldn't even find the riddle anywhere else. I'm excited to see if somebody knows the riddle or if not, how you approach the solution.

Three mathematicians are in prison. Each of them is in a single cell and they are not able to communicate in any way. They are imprisoned for an arbitrary number of days.

Each cell has a single light bulb that is either on or off on a given day. The warden tells the mathematicians that the light system of the prison has three modes:

• neutral mode, where each lightbulb is independent of the others


• bright mode, where two bulbs turn on every day and the other turns off


• dark mode, where two bulbs turn off every day and the other turns on

(All distributions are not necessarily uniform.)

The prison starts in neutral mode. After an unknown but finite number of days, the warden will select either bright mode or dark mode, which is locked in permanently.

After countably infinitely many days have passed, the mathematicians are asked which one the warden picked. They may discuss strategy before going into the cells, but there will be no communication afterwards. They have unlimited capacities to communicate and remember strategies that they come up with. Two of the three need to guess correctly to escape; how can they ensure this? You may assume that the axiom of choice holds.

Answer

The night before their first day in prison, the three mathematicians choose a non-principal ultrafilter on the set of days they are in prison. A non-principal ultrafilter is a rule for classifying some sets of days as large, and the rest as small, subject to the following conditions:

1. Every set of days containing a large set is large,


2. If the set of all days is partitioned into finitely many sets, exactly one set is large, and


3. No finite set of days is large.

Constructing a non-principal ultrafilter requires the axiom of choice, and communicating an ultrafilter from one mathematician to another requires an infinite amount of information. These mathematicians have unlimited mental capacity though, so maybe this is possible.

After the countably infinite number of days has passed, each mathematician guesses dark mode if the set of days when their light was off is large, and guesses bright mode if the set of days their light was on is large (property 2 above guarantees that exactly one of these conditions is met).

Suppose warden eventually selects dark mode. Consider the following four sets of days:

• neutral mode days,


• dark mode days when the first mathematician's light is on,



• dark mode days when the second mathematician's light is on,


• dark mode days when the third mathematician's light is on.

Again, property 2 of the ultrafilter says that exactly one of these sets of days is large. By property 3, it cannot be the first, because that set is finite. This means exactly one of the mathematicians saw a light for a large set of days, so that mathematician guesses bright mode and the other two guess dark mode. Success!

The argument in the case the warden selects bright mode is identical.