While three logicians were sleeping under a tree, a malicious child painted their heads red.

logic/smullyan/painted.heads

Problem

While three logicians were sleeping under a tree, a malicious child
painted their heads red.  Upon waking, each logician spies the child's
handiwork as it applied to the heads of the other two.  Naturally they
start laughing.  Suddenly one falls silent.  Why?

Show solution

The one who fell silent, presumably the quickest of the three, reasoned
that his head must be painted also.  The argument goes as follows.
Let's call the quick one Q, and the other two D and S.  Let's assume
Q's head is untouched.  Then D is laughing because S's head is painted,
and vice versa.  But eventually, D and S will realize that their head
must be painted, because the other is laughing.  So they will quit
laughing as soon as they realize this.  So, Q waits what he thinks is a
reasonable amount of time for them to figure this out, and when they
don't stop laughing, his worst fears are confirmed.  He concludes that
his assumption is invalid and he must be crowned in crimson too.

This puzzle has been attributed to Alonzo Churchin the 1930s.

This puzzle can be scaled up to any number of logicians and then is
analogous to the "common knowledge" problem.

SEE ALSO "priest"