The moderator takes a set of 8 stamps, 4 red and 4 green, known to the logicians, and loosely affixes two...
logic/smullyan/stamps Added material
Problem
The moderator takes a set of 8 stamps, 4 red and 4 green, known to the logicians, and loosely affixes two to the forehead of each logician so that each logician can see all the other stamps except those 2 in the moderator's pocket and the two on her own head. He asks them in turn if they know the colors of their own stamps: A: "No" B: "No" C: "No" A: "No B: "Yes" What are the colors of her stamps, and what is the situation?
Show solution
B says: "Suppose I have red-red. A would have said on her second turn: 'I see that B has red-red. If I also have red-red, then all four reds would be used, and C would have realized that she had green-green. But C didn't, so I don't have red-red. Suppose I have green-green. In that case, C would have realized that if she had red-red, I would have seen four reds and I would have answered that I had green-green on my first turn. On the other hand, if she also has green-green [we assume that A can see C; this line is only for completeness], then B would have seen four greens and she would have answered that she had two reds. So C would have realized that, if I have green-green and B has red-red, and if neither of us answered on our first turn, then she must have green-red. "'But she didn't. So I can't have green-green either, and if I can't have green-green or red-red, then I must have green-red.' So B continues: "But she (A) didn't say that she had green-red, so the supposition that I have red-red must be wrong. And as my logic applies to green-green as well, then I must have green-red." So B had green-red, and we don't know the distribution of the others certainly. (Actually, it is possible to take the last step first, and deduce that the person who answered YES must have a solution which would work if the greens and reds were switched -- red-green.)
Additional material
[ Editor: a proposed clearer solution, mailed to the archive in December
1995 and posted to rec.puzzles in January 1996. ]
Assuming the puzzle has a unique solution, then, by symmetry in
the stamp colors, the answer is obvious: B must have one of each
color.
Still, it is interesting to try to understand _how_ B knows this
on the second time around. (B did not 'know' that there is a
unique 'solution'.)
Let us say that the pair on a person's forehead is a "mix" if the
stamps are of different color and a "match" if they have the same
color. Two matches are the "same" if all four stamps involved
have the same color.
After each player has spoken for the first time, all players know
that none of them sees two matches that are the same.
Furthermore, after C speaks, A and B know that C does not even see
two different matches: Suppose, to the contrary, that A and B both
have matches. If C also had a match, then C's match would be the
same as that of one of A or B, and the other of A and B would have
seen two of the same match. Since that had not happened, C would
have been able to infer that C had a mix. But C did not make that
inference. Therefore, C sees at least one mix.
If, on the second time around, A did not see a mix on B, then A
would know that A had a mix. But A did not know. Therefore B has
a mix.
If the problem had been stated in terms of mixes and matches, then the
answer would no longer be obvious. Unfortunately, stating it that way
probably gets the solver on the right reasoning track more quickly and
thus decreases the problem's apparent level of difficulty.
Incidentally, this puzzle has been a favorite of mine for 30 years.
(I heard it, unattributed, in a bar!) I mentioned it to Martin
Gardner back in the late '60s. He had seen it, and he added that he
had a whole file folder full of "forehead problems"! Smullyan may
have presented it, but I do not think he invented it.
-- David Vanderschel <DvdS@eden.com>