The Coloured Stamps Problem

This is a trickier variant of the Coloured Hats problem, due to Raymond Smullyan.

This time a mischievous student has placed two stamps on the foreheads of each of three sleeping philosophers, X, Y, and Z. The student then wakes them and explains that the pairs of stamps were drawn randomly from a set of four green and four red stamps (the remaining pair of stamps being hidden). He proceeds to ask each of the philosophers in turn whether they know which colour stamps are on their forehead:
X: no.
Y: no.
Z: no.
Then the student goes around the group again asking the same question:
X: no.
Y: yes!
How did Y solve the problem?

Solution

Let us write rr, gg, and rg for the three possible stamp combinations (red/red, green/green, and red/green). We will write X is rr to denote X having red/red on his forehead, and so on.

We can immediately reject the X is gg and Z is gg case, since Y would know immediately that he is rr (but doesn't). Similarly for X is rr and Z is rr.

So Y starts by assuming Y is rr.

We can eliminate all possibilities where X is rr (since Z would immediately deduce that he is gg) or Z is rr (since X would immediately deduce he is gg).

This leaves the possibilities

• X is gg and Z is rg, or
  
• X is rg and Z is gg, or
  
• X is rg and Z is rg.

If X is gg, then Z knows he is not rr (since X would know he is gg, but he doesn't), and that he is not gg (since Y would know he is rr, but he doesn't), hence Z would know that Z is rg. He doesn't, hence X cannot be gg.

If Z is gg, then X would know on the second round that he was rg. He doesn't, hence Z cannot be gg.

The remaining possibility is X is rg and Z is rg. In this case, after the first round, X would know he must be rg, but he doesn't. Therefore X cannot be rg.

Y therefore concludes that he cannot be rr.

By symmetry, Y also concludes that he cannot be gg.

Therefore, Y knows he must be rg.