This
puzzle requiring inductive reasoning about other people's
knowledge exists in several forms with the same basic pattern. Here
is one:
In a certain monastery, ten of the monks have a disease which causes
them to have blue spots on their foreheads but has no other
symptoms. All the monks have taken a vow of silence, and there are
no mirrors in the monastery, so nobody knows whether he has a blue
spot on his forehead or not. If a monk discovers that he has a blue
spot on his forehead, he will have to leave the monastery by the end
of the day. All the monks are perfect logicians - that is, they can
instantly deduce all the logical consequences of any statement made
to them - and they all know that all the other monks are perfect
logicians. One day, the Guru, who is known to be truthful,
gathers all the monks together and announces "At least one monk in
this monastery has a blue spot on his forehead." Nothing happens for
nine days, but on the tenth day, all the monks with blue spots leave.
Why?
Another version of this problem involves a small town some of whose
inhabitants are commiting adultery, and whenever this happens
everyone except the wronged spouse hears about it within an hour. The
law in this town is that if your spouse can prove that you have been
unfaithful you will be put to death that day. The town's priest
wishes to stop the problem without accusing anyone, so he makes a
proclamation which everyone can hear: "There is adultery in this
town." Note that if the proclamation is made through the unreliable
postal service rather than being broadcast for everyone's ears
simultaneously, nothing will happen.
Why is there a delay before the monks leave? Well, start by
considering the case of one monk with a blue spot. When the guru
makes his statement, the monk will look around, notice that no-one
else has a blue spot, deduce that he is the one, and leave that
day.
With two monks with blue spots, A and B, A will think that B is the
only monk with a blue spot, and will expect him to leave. When this
hasn't happened by the end of the first day, A will realise that B saw
someone else with a blue spot, and that this someone else must be
him. B will be making the same deductions, and they will both leave
on the second day.
With three monks with blue spots, each monk with a blue spot will
think that the other two are in the situation described in the
previous paragraph, will expect them to leave on the second day for
the reasons described above, and when they haven't left by the third
day, will realise that he also has a blue spot. And so on - if N
monks have blue spots, they will all leave on the Nth day.
One puzzling aspect of this problem is what extra information the
guru's statement provides. The monks already knew that at
least one monk has a blue spot on his forehead, because they could
see each other. Again, this is easier to understand if there are
fewer monks with spots. If we go back to the case of two monks with
spots, A knows that at least one monk (namely, B) has a blue spot, but
he doesn't know that B knows this. With three monks with spots (A,
B and C):
- A knows that at least 2 monks (B and C) have blue spots
- A knows that B knows that at least one monk (C) has a blue spot
- A does not know that B knows that C knows that at least one monk
has a blue spot.
The effect of the guru's statement is that afterwards, everyone knows
that everyone knows that ... at least one monk has a blue spot, for
any number of
repetitions of "everyone knows that".