Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
1  
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 at 5:21
2  
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 at 5:42
3  
After countably infinitely many days, wouldn't the mathematicians be dead? – Joel Reyes Noche Feb 8 at 6:34
1  
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 at 12:54
1  
The mathematicians must have been very excited to have observed the passing of the countably infinite-th day. – Frentos Feb 8 at 21:01
up vote 27 down vote accepted

The night before their first day in prison, the 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 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.

share|improve this answer
1  
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 at 7:11
1  
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 at 19:13
    
(See also the discussion in comments on my answer - perhaps you can explain more clearly?) – Oliphaunt Feb 11 at 19:24
1  
@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 at 20:34
1  
(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 at 20:34

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.

share|improve this answer
8  
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 Feb 6 at 16:45
9  
@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 at 17:34
4  
@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 Feb 6 at 17:51
17  
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 at 17:53
4  
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 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. Ie, 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" iff 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.

share|improve this answer
2  
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 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 Feb 10 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 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 Feb 11 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.

share|improve this answer
    
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 at 18:55
    
@Trenin The same reasoning applies: exactly one of $L_1$ and $L_2$ is "large". – Oliphaunt Feb 11 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 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 Feb 11 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 at 19:15

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

share|improve this answer
    
you should add spoiler in the answer using >! – manshu Feb 8 at 20:16
1  
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 Feb 8 at 21:05
    
yes I interpreted to say the lighting is static. – Michael Martinez Feb 9 at 4:38
    
@manshu I don't know what you mean! – Michael Martinez Feb 9 at 14:51
    
let me do it for you... – manshu Feb 9 at 14:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.