## Monday, September 27, 2010

### Eight Stamps

Image via Wikipedia
The Grand Master 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 Grand Master's pocket and the two on her own forehead. 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 color stamps does B have?

1. B has Red and Green.. in fact they all do!

2. We can denote possible stamp combinations in the form of (AA BB CC MM) where each letter designates a stamp color held by logician A, B, C, or the Master.

When A says she doesn't know, she is saying that she does not observe all red (GG RR RR GG) or all green (RR GG GG RR), because if she saw all red or all green, then she and the master would have to have the other color.

When B says she does not know, she similarly eliminates the following possibilities:
A B C M
(RR GG RR GG)
(GG RR GG RR)
because if she saw A and C both had the same color, she could easily deduce her own color. In addition to this, she can also rule out the following:
(GG RG RR RG) - A has all Green, C has all red.
(RR RG GG RG) - A has all Red, C has all green.
This is because A eliminated the possible cases of (GG RR RR GG) and (RR GG GG RR). If B actually observed that A and C had the colors (GG XX RR XX), then she would have to conclude that everyone's colors are (GG RG RR RG), since the possibility of (GG RR RR GG) was eliminated by A's observation. But she did not observe this, so she said "I don't know". She similarly eliminates the case of (RR RG GG RG), because if she saw (RR XX GG XX) she would know that she had RG.

If you continue on with this logic, C eliminates the following possibilities:
(RR RR GG GG)
(GG GG RR RR)
(RR GG RG RG)
(GG RR RG RG)
(GG RG RG RR)
(RR RG RG GG)

Logician A then eliminates the following:
(RG RR GG RG)
(RG GG RR RG)
(RG GG RG RR)
(RG RR RG GG)
(RR RG RG GG)
(GG RG RG RR)
(RG RG RR GG)
(RG RG GG RR)

When it comes around to B again, she observes
(RG XX RG XX)
and can only conclude that they all have RG because the other possibilities have been eliminated.

... and I bet that was about as clear as mud. =)

3. Wow. That's a great explanation and I really appreciate it. I would not have been able to write up an answer as well as you just did.

Thanks, Jeff.

4. The previous explanation is not entirely accurate.

A would know their cards on the on the 1st try for the following permutations:
(GG,RR,RR,GG) I have GG; I see all four Red cards
(RR,GG,GG,RR) I have RR; I see all four Green cards

B would know their cards on the on the 1st try for the following permutations:
(RR,GG,RR,GG) I have GG; I see all four Red cards
(GG,RR,GG,RR) I have RR; I see all four Green cards

C would know their cards on the on the 1st try for the following permutations:
(RR,RR,GG,GG) I have GG; I see all four Red cards
(GG,GG,RR,RR) I have RR; I see all four Green cards

A would know their cards on the on the 2nd try for the following permutations:
(RG,GG,RG,RR) I have RG; If I had GG or RR, C would have answered
(RG,GG,RR,RG) I have RG; If I had GG or RR, C would have answered

B would know their cards were RG on the 2nd try for ALL remaining permutations.
Interestingly, in all remaining permutations B has RG, and, these are the only permutations out of the 19 possible where B does have RG.
(RR,RG,RG,GG) I can't have RR (not enough Red Cards); if I had GG, C would have answered on 1st try
(RR,RG,GG,RG) If I had GG, A would have answered on 1st try, if I had RR, C would have answered on 1st try
(GG,RG,RG,RR) I can't have GG; if I had RR, C would have answered on 1st try
(GG,RG,RR,RG) If I had RR, A would have answered on 1st try; if I had GG, C would have answered on 1st try
(RG,RG,GG,RR) I can't have GG; if I had RR, A would have answered on 2nd try
(RG,RG,RR,GG) I can't have RR, if I had GG, A would have answered on 2nd try
(RG,RG,RG,RG) If I had RR or GG, A would have answered on 2nd try

Leave your answer or, if you want to post a question of your own, send me an e-mail. Look in the about section to find my e-mail address. If it's new, I'll post it soon.

Please don't leave spam or 'Awesome blog, come visit mine' messages. I'll delete them soon after.

Enter your Email and join hundreds of others who get their Question of the Day sent right to their mailbox