Logic!

Here, once again, is the question:

Three perfect logicians, A, B, and C, sit around a circular table. There is a set of stamps, four red and four green. Each logician has had two stamps pasted on his forehead; he doesn’t know which they are, he can see the other ones’ stamps. They are asked, in rotation, if they know which stamps (red-red, red-green, or green-green) are on their own forehead.

A: “No.”
B: “No.”
C: “No.”
A: “No.”
B: “Yes.”

What stamps does B have? (Easy.) And how does he know it? (Hard.)

First, the easy part. The situation is completely symmetrical in red and green. That is, if there were a way to conclude “N greens”, you could run the same solution with red and green switched and get “N reds”. So the solution has to be also be symmetrical, and thus is “one red, one green”.

Now, the hard part.

• First, assume B has two reds.
• If A had two reds, C would see all four reds and would have known at his first turn to speak that he had two greens. So A does not have two reds.
• For the same reason, C does not have two reds.
• Suppose A has two greens. Then C will know he doesn’t have two greens (because B would have seen all four greens) or two reds (because A would have seen all four reds). So C would know he has one of each when he first speaks. Thus A does not have two greens.
• For the same reason, C does not have two greens.
• Thus B knows that A and C both have one of each.
• But consider A’s second turn to speak. He knows he can’t have two reds (or C would have known he had two greens himself) or two greens (because C would have known he had one of each himself). Since A said “no”, this is impossible.
• Thus B does not have two reds.
• By the same logic, B does not have two greens.
• Thus B has one of each.

There are these possibilities:

(Updated from here on, thanks to Alan Scott.)

• A has two greens, B one of each, C two reds
• A has two reds, B one of each, C two greens
• A and B both have one of each, C has 2 of the same color
• B and C both have one of each, A has 2 of the same color
• All three have one of each

In the first two, B knows what he has as soon as C says “no”. In the rest he doesn’t know until A says “no” the second time. There isn’t enough information to determine which is true.

Mike Schilling

Mike has been a software engineer far longer than he would like to admit. He has strong opinions on baseball, software, science fiction, comedy, contract bridge, and European history, any of which he's willing to share with almost no prompting whatsoever.

1. kenB

Hmmm… the easy explanation depends on an assumption that isn’t mentioned in the actual problem, i.e. that there’s a unique solution.

• Mike Schilling

It’s implied, when posing this sort of puzzle, that it has an answer.

• kenB

I’m not sure what you mean — there’s a difference between having an answer and having a unique answer. I’ve seen puzzles where the answer is along the lines of “either x or y”, though granted they’re not that common.

If you’re thinking along the lines of Stillwater’s comment, I don’t think that applies — B can have a unique answer even if we can’t be sure what it is, since B is seeing a particular set of stamps.

• Mike Schilling

The problem, as stated, cannot have the answer “two greens”. Nor can it have the answer “two reds”. What does that leave?

2. Stillwater

So the solution has to be also be symmetrical

I agree with that.

, and thus is “one red, one green”.

I don’t see how that follows from the bare thesis of symmetricality. Wouldn’t symmetricality entail that the answer is EITHER “one of each color, OR both the same of either color”?

• Mike Schilling

If (as I’ve pointed out above, is implied) the puzzle has an answer, it has to be one of each. Without that implication, it could be “one of each”, or “two of either color”, or “no way to tell”.

• Stillwater

Ahh, yes. I see it now. The second part my above answer doesn’t follow from symmetricality but from the fact that B has arrived at a determinate answer, which narrows things down a bit. Nice.

3. Stillwater

Mike, I’m sure you’ve seen this one. It’s VERY puzzling.

1. a = x
2. a+a = a+x
3. 2a = a+x
4. 2a-2x = a+x-2x
5. 2(a-x) = a+x-2x
6. 2(a-x) = a-x
7. 2(a-x) = 1(a-x)
8. 2(a-x)/(a-x) = 1(a-x)/(a-x)
9. 2 = 1

• Mike Schilling

Not that puzzling, though it is a nice lead-in to Monday essay.

• Stillwater

No, not puzzling for you. I wonder what other people think of it, tho.

• Mike Schilling

My 18-year-old saw it too. (Actually, if you’ve seen enough like it, you know what the gimmick is right away.)

• It has to do with that thing that Cantor said: “Small infinities let you get away with, like, murder.”

• Is Rot13 the polite alternative to letting the cat out of the bag?

• Mike Schilling

Lrf, vg vf.

• Gunax lbh.

• It’s irrational. You can’t divide by zero.

• Stillwater

Well, I’m not gonna let the cat outa the bag by saying you’re right or anything…

• In some of the batch COBOL programs I wrote, if I found a critical error in processing, I’d divide by zero to purposely make the program crash — an ABEND — a shop standard. We did this to alert operations that something was really wrong; because otherwise, they’d just run it and not always notice if the program returned an error but ended itself normally.

• Mike Schilling

I used to work with a guy who would do the equivalent in C code (dereference a null pointer). Not print out a useful error message and then dereference a null pointer, mind you. That would have been too much effort.

• Stillwater, better answer: Catalives. Catxdied. But it’s only when we peek in the bag that we realize there are no cats to let out, and it’s filled with hairballs.

• J@m3z Aitch

Would I have found it more puzzling if I was actually better at math?

• aleb

In step 8 you divide by zero (a-x). You can “prove” anything by doing that.

4. Alan Scott

a quibble:

There are three possibilities:

A has two greens, B one of each, C two reds
A has two reds, B one of each, C two greens
A, B, and C all have of each
In the first two, B knows what he has as soon as C says “no”. In the third he doesn’t know until A says “no” the second time. There isn’t enough information to determine which is true.

There are actually seven possibilities. In addition to the ones listed above:
A has two greens, B and C one of each
A has two reds, B and C one of each
A and B have one of each, C has two greens
A and B have one of each, C has two reds

Are all possibilities. Noticing that there were only 19 possible distributions in the first place, I just brute forced it. Other interesting tidbits:

Were A, B, or C instead to say yes the first time around, we wouldn’t be able to say what they or any of the others had. The logicians themselves would know, though.

Were A to instead say yes the second time, we’d know that he has one red and one green. After A says yes, B may say yes (in which case all three logicians know what stamps they each have but we know only A’s stamps) or he may say no (in which C has a red and a green, but B’s stamps cannot be deduced by us or B).

Once A has answered “no” a second time, there’s no set of circumstances where B’s second answer will not be yes. Continuing from B’s yes answer, there’s no way that we or the remaining logicians can determine the distribution of the remaining stamps.

5. Ken

If we just consider the game the logicians are playing, and drop the outcome that Mike has supposed, there are 10 ways the stamps can be distributed (aside from the symmetry between R and G): three ways to order the RR,RR,GG (order matters in this game), three ways to order RR,GG,RG, three ways to order RR,RG,RG, and RG,RG,RG. I believe that in every case, eventually one of the players will be able to deduce what stamps he has.

In the case of RR,RR,GG, the GG player immediately deduces that he has GG, because he sees all four R’s.

In the case of RR,GG,RG, as soon as RG hears “No” from both RR and GG, he knows that he cannot have RR or GG, so he must have RG.

In the case of RR,RG1,RG2, let’s look at the game from the point of view of RG2. He sees RR and RG1, so from the previous case he knows that if he had GG, eventually RG1 would be able to deduce that he has RG, so when he hears enough No’s, RG2 can deduce that he has RG.

I’m pretty sure that a similar argument shows that in the case RG,RG,RG, eventually one of the players will deduce his status, but it is late at night and I want to double-check my reasoning in the morning.

I have not tried to count the number of “No”s prior to the first “Yes” for two reasons. One is that it varies from case to case, so there will be too many different answers to trouble with. The other is this: In order to find a lower bound, we have to be certain that we have considered all possible deductions that the logicians can make. (For an upper bound, we don’t.) That’s not impossible to do, but it doesn’t sound so easy.

• Mike Schilling

In the case of RR,RG1,RG2, let’s look at the game from the point of view of RG2.

He’s never going to be as famous as RG3.

6. Alan Scott

Here are all nineteen possible cases (Ken’s ten cases plus their reflections, (keeping in mind that the 10th case is a reflection of itself). I’ve included the responses we’ll get by asking the logicians the question in order until they’ve identified their stamps or are unable to make further deductions from the answer:

Case 1: A=gg, B=gg, C=rr
A says no, B says no, C says yes, A says yes, B says yes

Case 2: A=gg, B=gr, C=gr
A says no, B says no, C says no, A says no, B says yes, C says no, A says no
A unable to distinguish from case 10 and 18
C unable to distinguish from case 3

Case 3: A=gg, B=gr, C=rr
A says no, B says no, C says no, A says no, B says yes, C says no, A says no
A unable to distinguish from case 11
C unable to distinguish from case 2

Case 4: A=gg, B=rr, C=gg
A says no, B says yes, C says yes, A says yes

Case 5: A=gg, B=rr, C=gr
A says no, B says no, C says yes, A says yes, B says yes

Case 6: A=gg, B=rr, C=rr
A says yes, B says yes, C says yes

Case 7: A=gr, B=gg, C=gr
A says no, B says no, C says no, A says yes, B says no, C says yes
B unable to distinguish from case 13

Case 8: A=gr, B=gg, C=rr
A says no, B says no, C says no, A says yes, B says yes, C says yes

Case 9: A=gr, B=gr, C=gg
A says no, B says no, C says no, A says no, B says yes, C says no, A says no
A unable to distinguish from case 17
C unable to distinguish from case 10 and case 11

Case 10: A=gr, B=gr, C=gr
A says no, B says no, C says no, A says no, B says yes, C says no, A says no
A unable to distinguish from case 2 and case 18
C unable to distinguish from case 9 and case 11

Case 11: A=gr, B=gr, C=rr
A says no, B says no, C says no, A says no, B says yes, C says no, A says no
A unable to distinguish from case 3
C unable to distinguish from case 9 and case 10

Case 12: A=gr, B=rr, C=gg
A says no, B says no, C says no, A says yes, B says yes, C says yes

Case 13: A=gr, B=rr, C=gr
A says no, B says no, C says no, A says yes, B says no, C says yes
B is unable to distinguish from case 7

Case 14: A=rr, B=gg, C=gg
A says yes, B says yes, C says yes

Case 15: A=rr, B=gg, C=gr
A says no, B says no, C says yes, A says yes, B says yes

Case 16: A=rr, B=gg, C=rr
A says no, B says yes, C says yes, A says yes

Case 17: A=rr, B=gr, c=gg
A says no, B says no, C says no, A says no, B says yes, C says no, A says no
A is unable to distinguish from case 9
C is unable to distinguish from case 18

Case 18: A=rr, B=gr, C=gr
A says no, B says no, C says no, A says no, B says yes, C says no, A says no
A is unable to distinguish from case 2 and case 10
C is unable to distinguish from case 17

Case 19: A=rr, B=rr, C=gg
A says no, B says no, C says no, A says yes, B says yes, C says yes

As Mike points out in the post, the only time we know what stamps a logician has is when they have one of each. There are circumstances where we know that a logician has two of the same color, but without seeing some of the stamps, we can’t tell which color that is. Here’s the cases where we can identify a logician’s stamps:

Cases 2, 3, 9, 10, 11, 17, and 18: These correspond to the original question. We know B has one of each

Cases 7 and 13: We know that A and C both have one of each.

Cases 8 and 12: We know that A has one of each.