Three mathematicians are forever in Prison

Question

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 1

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.

Answer 2

When the mathematicians are asked for their answers, each answers "light mode" if their light is currently on, or "dark mode" if it is currently off.

Answer 3

I heard this puzzle (or a similar version) from Abraham Neyman. The solution is similar to that of Julian Rosen above. The mathematicians choose a Banach limit. I.e, a linear operator on bounded sequences that extends the usual limit whose value is between the limit superior and limit inferior.

Each mathematician answers "bright" if and only if his limit is strictly greater than a half. Since the Banach limit is linear the sum of the three limits is either one or two.

Answer 4

^{I doubted posting this, because it isn't quite an answer. But I spent some time pondering this puzzle and I wanted to share my insights, such as they are.}

Computing an average... won't work

My initial thought was to have each mathematician compute the "average light state" in their cell; they proclaim "bright mode" if this average is higher than ½, and "dark mode" if it is lower. I believe computations can get a little sketchy with infinities; it might be defined as $$A_i = \lim_{n \rightarrow \infty} \frac1n \sum_{k=1}^n L(i,k)$$ where $L(i,k) \in \{0,1\}$ denotes "in mathematician $i$'s cell on day $k$, the light is switched on/off". I wasn't sure whether this limit would converge; we might have to resolve this by defining a Banach limit as suggested in Ron's answer.

This average would be completely determined by the infinite number of days spent in either bright or dark mode; neutral mode would not influence it at all. We would have $\sum_i A_i \in \{1,2\}$, depending on the mode chosen by the warden.

Big question, however, is: if $A_i = ½$, what should mathematician $i$ do?

I wondered this myself, and it was also pointed out by Julian Rosen in comments. It is easy to show that the warden can give any two mathematicians an average of ½ regardless of the mode he picks; the third one then gets $A_i \in \{0,1\}$. They won't be able to agree on a rule that works in all cases.

The ultrafilter

I was only recently introduced to ultrafilters, by Julian Rosen's answer. At first I thought there was something fishy going on; what if the warden follows the ½-½-0/1 tactic? The answer is that the sets of days where the light is on for both half-mathematicians must be unequal (in fact, on almost all days their states must be different). The ultrafilter leverages this.

To make this more precise:

Let $L_0$ be the set of days where both half-mathematicians have equal lighting states. Because the third mathematician's average light state must be either 0 or 1, $L_0$ is finite. Let $L_1$ be the set of days where the first half-mathematician's light is on and let $L_2$ consist of the days where the second half-mathematician's light is on. Both these sets are infinite, and together with $L_0$ they partition the set of all days spent in prison.

By properties 2 and 3 of a non-principal ultrafilter, either $L_1$ or $L_2$ is "large"; so by property 1, one and only one of the half-mathematicians spends a large number of days in a lit cell. Crisis averted.

Answer 5

Assume that in light or dark mode, the first and second light switch between on/off and off/on, while the third light is either always on, or always off. Obviously the third prisoner will guess right.

The mathematicians will need a strategy that guarantees a different response. If they agreed that in this situation the first mathematician says "dark" and the second says "light", they win. But that doesn't work, since each two of the three mathematicians could be in that situation. So they'd need to give different answers based on the different sequences that they see, which are always or almost always opposite.

I suppose that's where the "ultrafilter" comes in, clearly distinguishing one set with 50% of days chosen at random as "large" and the complement of that set as "small".

Answer 6

From the perspective of a single prisoner, countably infinite days are necessary in order for him to realize that he is no longer in neutral mode. This is because: neutral mode will never have an infinite number of consecutive days without change. Likewise, one of the other two modes can only be recognized after countably infinite days where no change has occurred.

Therefore, after countably infinite days: each prisoner will realize that he is no longer in neutral mode. He will realize that his light has been on (or off) forever. At this point, if it is on, then he will say that they are in bright mode; if off he will state that they are in dark mode (this is the strategy the mathematicians agree upon before entering the cell). Two of the three mathematicians will be correct in their statement, therefore they will escape.

The main thing to realize is that it works because countably infinite days have passed. This answer will not work if only a finite number of days have passed.

EDIT 2/9:

In the above solution I assumed the lighting mode was static, but in the case it's not, the solution is similar.

Each mathematician simply chooses his answer based on the preponderance of on or off days. If he sees a greater number of on (off) days, then he assumes bright (dark) mode. If the mode is distributed randomly among the light bulbs, then all three will choose correctly because each room will have 2 days on (off) for every day off (on). If the mode is not distributed randomly, then two of the three prisoners will choose correctly.

EDIT 2/10: generalizing: let's say the mode is bright. the following is true; one case is where every room has 2 bright days for every 1 dark day. Another case is where two specific rooms have all bright days and one specific room has all dark days. All other cases are in between: that is, a specific room has a bright-to-dark ratio < 2:1 and could even be < 1:1, while the two other rooms always have a bright-to-dark ratio > 1:1. So, again each mathematician when asked what mode they're in replies with whatever he observed to be the preponderance in his cell - two of the three will be right.

EDIT: 2/11 AS others have pointed out, I've been basing my answer on a random distribution, but the problem as stated doesn't restrict it, so I need to rethink my answer. (Answer works for random distribution only).

Answer 7

Each prisoner says "bright" given more days with light or else says "dark"

"Countably infinite" allows us to take a probabilistic approach and make it deterministic.

The puzzle states that a finite number of days pass in "neutral" mode and then a countably infinite number of days pass in either "bright" or "dark" mode. This makes the neutral mode irrelevant.

If you roll a fair six-sided die a thousand times, you'll end up with very close to ⅙ of your results being 6s. (This is quite similar to the example used on Wikipedia's Law of Large Numbers page.) If you add a dozen 1s to that, not much will change: $\frac{⅙ × 1000}{1012} = 16.47\%$ is quite close to $⅙ = 16.67\%$. Given infinite rolls, a fair six-sided die will roll each of its six sides the exact same amount.

Given infinite days,

• "bright" mode will result in exactly ⅔ days of light for each mathematician
• "dark"   mode will result in exactly ⅓ days of light for each mathematician.

 

---

We don't even need infinite days

The only essential piece of this puzzle is that the time in "neutral" mode is rendered irrelevant by the overwhelmingly larger time in either "bright" or "dark" mode.

We're given a huge buffer here since the two choices are P=⅓ vs P=⅔ and only two answers need to be correct. The odds of the group being wrong are close to zero even with a month (31 days) entirely without light in "neutral" mode and the next three months (89 days, pessimistically) in "bright" mode:

Given "bright" mode, our base probability p of light is ⅔. The number of random days n is 89, plus the warden's time w of 31 days in darkness. The number of days with light needed to be wrong k is between 0 and 44 (from $\lceil\frac{89}{2}\rceil - 1$, the largest possible minority). We'll need to use a summation to combine that range and we'll use a binomial coefficient since any combination will suffice. This is multiplied by the number of desirable outcomes ^{_{${{{\left(\frac1p - 1\right)^{n-k}}}}$}} (I subtract one to prevent overlap). Only two prisoners need to be right, so the whole thing is divided by ⅔:

$$ \frac{p^{n+w} \sum_{k=0}^{\lceil\frac n2\rceil - 1} \left[ {n\choose k} \left(\frac1p - 1\right) ^{n-k} \right]}{⅔} $$

Each prisoner has 1:287,704 odds of being wrong and the team of them has 1:431,556 odds of being wrong, which translates to 99.999768% odds of being right.

Three months of "neutral" and 9 months would be even better, with one error in $2.4 × 10^{16}$. Winning their freedom is about twice as likely as failing to win the Powerball lottery's grand prize.

 

The mathematicians can further improve their odds in the non-infinite version by planning to ignore a certain number of days plus as long as it takes to see the next change of a light's state. If pulled out before twice the ignored time, they'd revise and count some or all of the previously ignored time.