# 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.

• So there is some time $t$, such that before $t$ the light system is always mode 0, and after $t$ the light system is either always 1 or always 2? – f'' Feb 6 '16 at 5:21
• I've made some substantial edits to improve formatting and break it up a bit - have I changed your intention? (This is a fantastic puzzle, by the way - welcome to Puzzling.SE! I hope to see you around here more!) – Deusovi Feb 6 '16 at 5:42
• After countably infinitely many days, wouldn't the mathematicians be dead? – Joel Reyes Noche Feb 8 '16 at 6:34
• Are the mathematicians asked which mode the warden chose on the same day? As in, all three are asked at once, or are they asked on different days? – DuckTapeAl Feb 8 '16 at 12:54
• The mathematicians must have been very excited to have observed the passing of the countably infinite-th day. – Frentos Feb 8 '16 at 21:01

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.

• very nice solution - I actually didn't know about ultrafilters, so I essentially constructed your filter as explicit as I could (obviously, at some point you need axiom of choice - or in my case Zorn's lemma). your solution is much shorter. – LFH Feb 6 '16 at 7:11
• Lets say that "normal mode" is zero days. Warden then picks a mode and from now on will toggle the light in the first and second prisoner's room every day with exactly one on and the other off. The third prisoner will have their light always on (bright mode) or always off (dark mode). $P1$ and $P2$ see the exact same sequence of lights - on/off/on/off... ad nauseum. The only difference is the light on the first day is different. How do they decide to pick differently? – Trenin Feb 11 '16 at 19:13
• @Trenin On the night before entering prison, the mathematicians get together and agree on a lot of things. For example, maybe they agree that a mathematician who sees lights on all the even days should vote bright, and a mathematician who sees lights on all the odd days should vote dark. This decision is totally arbitrary, but they agree beforehand. – Julian Rosen Feb 11 '16 at 20:34
• (cont.) There are lots of other decisions to make: e.g., who should vote bright if one mathematician sees lights Mondays, Wednesdays, Fridays, and even-numbered Saturdays, and another sees lights Tuesdays, Thursdays, Sundays, and odd-numbered Saturdays? The mathematicians need to agree on infinitely many arbitrary decisions (this is why we needed the axiom of choice), and the ultrafilter records the results of all the arbitrary decisions. – Julian Rosen Feb 11 '16 at 20:34
• "communicating an ultrafilter from one mathematician to another requires an infinite amount of information" Uncountably infinite, I take it? – Acccumulation Feb 7 '18 at 17:16

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.

• I can't imagine this was the intended solution, but actually I don't see why this wouldn't work. What are @furiouscloud and I missing? – Oliphaunt - reinstate Monica Feb 6 '16 at 16:45
• @Oliphaunt: If I were constructing this riddle from scratch, I would exclude this answer by saying that the mathematicians are removed from their cells after countably many days. Since there is no "last day" (omega is a limit ordinal), you cannot just use that, and the mathematicians do not know when neutral mode ends, so they cannot use some arbitrary finite day either. – Kevin Feb 6 '16 at 17:34
• @Kevin Right, got it. For me, a better phrasing would perhaps be to have the mathematicians removed after e.g. two days. The first switch happens after one day, the second half a day later, and so on with the time between successive switches always halved (and assuming time is continuous). For me, that makes the "countably infinite" easier to grasp and it still fits comfortably in a lifetime (be it the mathematicians' or the universe's). – Oliphaunt - reinstate Monica Feb 6 '16 at 17:51
• This has to be the best solution. Perhaps it should however be disqualified on the basis that being mathematicians they would, having been explicitly told the axiom of choice is permitted, undoubtedly choose something far more complicated (see Julian Rosen's answer, for example). – abligh Feb 6 '16 at 17:53
• The statement in the problem is: "After countably infinitely many days have passed, the mathematicians are asked which one the warden picked." Of course, that doesn't sound very realistic, but it should imply that there is no last day as noted by Kevin. However, I also Oliphaunt's suggestion. --- This riddle is often told first in an easier version where one doesn't have a neutral mode. In this case furiouscloud's solution works if they agree on an arbitrary day beforehand. – LFH Feb 6 '16 at 22:43

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.

• I'm worried about basing a guess on the value of the Banach limit. Suppose that two of the mathematicians get a light on alternating days. Each of them computes a Banach limit of $\frac{1}{2}$, so they will make the same guess, which is then necessarily the majority. However, it could be the case either that the mode is bright (so that the third mathematician sees a light every day) or dark (so that the third mathematician never sees a light). – Julian Rosen Feb 6 '16 at 21:52
• @JulianRosen their guesses don't have to be the same; they can agree on voting opposite beforehand. But the point stands that no strategy can deal with this. (I'll take this opportunity to plug my answer again, where I mention this). – Oliphaunt - reinstate Monica Feb 10 '16 at 14:37
• @Oliphaunt How can they agree to be opposite? Would $P1$ say "I will vote dark if $limit=\frac{1}{2}$ and $P2$ say "I will vote bright if $limit=\frac{1}{2}$? If so, then what if warden set $P2$ to be always on (or off) and alternated $P1$ and $P3$? Then it only works if $P3$ agreed the same as $P2$ before hand. So then, what if the warden sets $P1$ to off and toggles the other two? Both would say "bright mode" when the limit is $\frac{1}{2}$ and be wrong. – Trenin Feb 11 '16 at 19:19
• @Trenin Correct. I was just saying that P1 and P2 don't have to vote the same, but I noted that the point stood that there's no strategy to deal with the general case. – Oliphaunt - reinstate Monica Feb 11 '16 at 19:21

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.

• What if the "normal" period is zero days, so the warden selects immediately. For the rest of the days, $P1$ and $P2$ always alternate, and $P1 \ne P2$ and $P3$ is either always on (bright mode) or always off (dark mode). From $P3$ perspective, the answer is easy. For the other two, half the days are bright and half are dark, alternating. How do they choose? – Trenin Feb 11 '16 at 18:55
• @Trenin The same reasoning applies: exactly one of $L_1$ and $L_2$ is "large". – Oliphaunt - reinstate Monica Feb 11 '16 at 18:58
• So in this case, $L_0$ is empty because the light is always on in either $P1$ or $P2$, but not both. $L_1$ is the odd numbered days, $L_2$ is the even numbered days. I don't see how one is large and the other is not. – Trenin Feb 11 '16 at 19:01
• @Trenin That's by definition of the ultrafilter: given a partitioning of the countably infinite set, exactly one set in that partitioning is large. I don't pretend to understand how ultrafilters work exactly, but given those properties, this follows. – Oliphaunt - reinstate Monica Feb 11 '16 at 19:08
• Hmm... I'm not seeing it. I will post the same comment on JR's answer and see if he replies, because the same problem will happen for him. – Trenin Feb 11 '16 at 19:15

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".

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).

• you should add spoiler in the answer using >! – manshu Feb 8 '16 at 20:16
• The way I read the puzzle, during bright/dark mode individual lights may still switch off and on from day to day, it's just guaranteed that the ratio is 1:2. If I read your solution correctly, it seems to assume that in these modes, the lighting is static. – Oliphaunt - reinstate Monica Feb 8 '16 at 21:05
• yes I interpreted to say the lighting is static. – Michael Martinez Feb 9 '16 at 4:38
• @manshu I don't know what you mean! – Michael Martinez Feb 9 '16 at 14:51
• let me do it for you... – manshu Feb 9 '16 at 14:52

### 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.

• There's no guarantee that the lights are chosen randomly. – f'' Jun 4 '16 at 2:59
• I'm not sure that matters, except insofar as one mathematician will probably be wrong and two will be right (whereas if it is actually a random selection of which lights toggle, all three mathematicians will be right). – Adam Katz Jun 4 '16 at 4:32
• What happens if two mathematicians each see exactly 50% on and 50% off? – f'' Jun 4 '16 at 5:12
• In bright mode: one has the light always on, the other two alternate light and dark. In dark mode: one has the light always off, the other two alternate light and dark. – f'' Jun 4 '16 at 18:26
• Nice hypothetical; I hadn't considered an evil warden (especially given "dark" mode); the chance of going 50/50 unintentionally approaches zero as the number of days approaches infinite. I'm more of a statistician than a set theorist; noting that I don't fully understand ultrafilters, it seems that your argument here would invalidate any answer to this question except for furiouscloud's answer. – Adam Katz Jun 5 '16 at 23:34