Fog Creek Software
Discussion Board

Solution: Chinese emperor

Well, there's a false implication here that the game will *necessarily* go to the last person to guess. One of the first two may know even earlier, and get the answer that way. But it is true that the last person will definitely know the answer if the first two don't, and it's also true that the game it *biased* towards the last person.

Here's how it works:

Lets call the three sages A, B, and C, in the order they get to guess.

Now, let's break the problem space into three possibilities:

1) B and C both have black balls on their heads. There's a 1 in 10 chance of this happening (2/5 * 1/4).
2) B has a white ball, and C has a black ball. There's a 3 in 10 chance of this happening (2/5 * 3/4).
3) C has a white ball (whatever color B's ball is). There's a 3 in 5 chance of this happening.

OK. In situation 1, when it's A's turn to guess, he can see that B and C have the black balls on their heads, so he knows he has a white ball.

In situation 2, A can't tell the color of his ball--he doesn't know if his ball is the remaining black one, or one of the two remaining white ones. So the question will move to B. Well, B can see the black ball on C's head (so he knows situation 3 doesn't obtain), and, since A couldn't guess, he knows situation 1 doesn't obtain. So he can conclude that situation 2 is the situation, and knows he has a white ball.

In situation 3, neither A nor B can tell the color of his ball. But since C will know that A and B have both failed to guess, he'll know that situation 3 obtains, so he'll know that his own head contains a white ball.

So A has a 10% chance of being appointed, B has a 30% chance, and C has a 60% chance.

Actually, it's more complicated than that, but I'll save that for a separate post.

Avrom Roy-Faderman
Friday, October 8, 2004

OK, so why did I say the situation was more complicated?

Well, suppose A is unable to guess with certainty (that is, situation 2 or 3 obtains). Since the only penalty for guessing wrong is disqualification, and since A *knows* he's not going to get another chance to guess (C will definitely guess correctly, if nobody else does), the face is, he should try anyway.

If B and C both have white balls, A knows there's a 2/3 chance that his ball is black. And if one has a black ball, there's a 2/3 chance that his ball is *white*. So A's actual chance of being made advisor is
(1/10) * (1) + (9/10) * (2/3) = 70%.

What about B?

Well, if situation 1 obtains, B will never get to guess.
If situation 2 obtains (30% chance, remember), B still only has a 1/3 chance of getting to guess. In those cases, he'll be certian to get it right.
If situation C obtains (60% chance), then (by calculations similar to the above), B will again guess right 2/3 of the time (in the 1/3 likely event that he gets to guess at all). And he should still guess, since, if he passes, he'll lose the job anyway. So B's actual chance of being made advisor is
(3/10) * (1/3) + (6/10) * (2/3) * (1/3) = 7/30 >~ 20%.

So even though C will be guaranteed right *if he gets to guess*, he has less than a 10% chance of this happening. So in reality, the game's biased towards *A*:

A = 70%
B ~ 20%
C ~ 10%

Close to the reverse of the other case!

My other solution would hold true if the penalty for guessing wrong were much worse than disqualification; e.g., death.

Avrom Roy-Faderman
Friday, October 8, 2004

Oops. Actually, it's even more complicated than that.

I'll stick by my answer for A: He has a 70% chance of getting the solution right.

So, as before, B has a 30% chance of getting to guess. And if situation 2 obtains, he can be certain to get it right.

So suppose situation 3 obtains. Now, B knows (presumably) just how wise A is. So he can remember A's answer, and use it as a guide.

If A answered "black", it was because he saw that B and C both had white balls. So B knows his ball is white.

If A answered "white", it was because B and C had different colored balls. And B can see that C's ball is white, so he knows his ball must be black.

Either way, if B gets to guess, he can guess correctly.

So the *real* chances of being made advisor are:

A: 70%
B: 30%
C: 0%

You *don't* want to be the last person to guess here.

Avrom Roy-Faderman
Monday, October 11, 2004

only way first dude can know for sure is if he sees 2 blacks.
if first dude passes, second dude looks up at my head.
if second dude sees black on my head, he knows he's white so he wont pass.
so... if the second dude passes i gotta have the white ball on my head.

downtown brown
Wednesday, December 8, 2004

Agreed. But my point is that the first and second people will *never* both pass. If the first person passes, the second person will know.

Avrom Roy-Faderman
Wednesday, December 22, 2004

*  Recent Topics

*  Fog Creek Home