Fog Creek Software
Discussion Board




Chinese emperor

I'm stumped on the Chinese emperor question -- http://www.techinterview.org/Puzzles/fog0000000031.html

I know that if I was one of the wise men, and I saw one white ball and one black ball, then there's a 66% probability that the ball on my head is white.  Likewise, if I see two white balls on the other two sages' heads, I have a 33% probability of having a white ball on my head.  And if I see two black balls on the other sages' heads, I definitely have a white ball on my head.

It's combining the probabilities that gets me down.  I'm not sure how the wise men could say with any certainty that "the last one to guess would always win."  And I can't seem to remember the "sampling without replacement" rules that I learned in high school stats.

Can someone throw me a bone on this one?

Andreas Udby
Friday, June 14, 2002

Well, let's see. I'm going to assume that a sage will pass unless he is absolutely certain of his color. If any sage guesses at any point, the last sage will still know his color, having followed the logic.

Call the sages A, B, C, in guessing order.

A will guess only if B and C are both black, leaving only white balls available for A to have. If A guesses, A is white, B is black, and C is black. If A passes, at least one of B and C (and possibly both) must be white.

So, A passes to B. It's B's turn: B knows that B or C must be white. If C is black, B must be white. If C is white, B can't know his own color, even by looking at A, since not all the black balls are accounted for. So, if B guesses, C must be black, and if B passes, C must be white (and A still doesn't know what color he is!)

Therefore, if A and B both pass, C guesses white and is correct, even if no black balls are present. C will know his color after B's turn regardless if B passes or not.

Seems to work given the assumption. What do you think?

Mike Weber
Saturday, June 15, 2002

Ahhh... and if B guessed "white", then C would definitely know that he has a black on his head?  Okay, now I think I understand.  Thanks, Mike.

Andreas Udby
Monday, June 17, 2002

How "fair" is the game?

A wins if B and C are black -- 10 %
B wins if B is white and C is black --  30 %
C wins if C is white -- 60 %

Roy Pollock
Wednesday, June 19, 2002

This one takes some figuring. Not too hard if you go through this puzzle through combination study.

Assuming A B C. C is always the last one to guess. Let me walkthrough all to see how the last one can always guess his ball.

Combination 1:
--------------
B  B  W
A  B  C

In this instance, C definitely knows the answer. A and B do not even need to say anything.


Combination 2:
--------------
W  W  B
A  B  C

A sees that B has White ball and C has Black ball. He is not sure if he has Black or White ball. He pass.
B sees that A has White ball and C has Black ball. If he himself has Black ball, A should have know the answer. A does not know, so B confidently says he has White ball.
C, seeing two white balls, knows that he must be holding the Black ball for B to make the decision. C guesses he has Black ball.


Combination 3:
--------------
W  W  W
A  B  C

This is very related to Combination 2.
A sees that B and C has White balls. He is not sure if he has Black or White ball. He pass.
B sees the same thing. He pass.
C, seeing that both A and B pass, makes an assumption that he must be white. Because if he has Black ball, it will lead to Combination 2 scenario.

Combination 4:
--------------
B  W  B
A  B  C

A sees that B has White ball and C has Black ball. He is not sure if he has Black or White ball. He pass.
B sees that A and C has Black balls, he guess he has White ball.
C, seeing that B has guess he has White ball and that A has Black ball, knows that he is holding the Black ball for B to make that confident guess.

Combination 5:
--------------
B  W  W
A  B  C

A sees that B and C has White balls. He is not sure if he has Black or White ball. He pass.
B sees that A has Black ball and C has White ball. He is not sure if he has Black or White ball. He pass.
C sees that A and B pass. If he is holding the Black ball, B will not have pass. He knows he is holding the White ball to give A and B the inability to guess correctly.

Combination 6:
--------------
W  B  W
A  B  C

The answer is similar to Combination 5.
A sees that B has Black ball and C has White ball. He is not sure if he has Black or White ball. He pass.
B sees that A and B has White balls. He is not sure if he has Black or White ball. He pass.
C sees that A and B pass. If he is holding the Black ball, A will not have pass. He knows he is holding the White ball to give A and B the inability to guess correctly.

Combination 7:
--------------
W  B  B
A  B  C

A sees that B and C has Black balls. He guess he has a White ball.
B and C subsequently concludes that they both have a Black ball.

Thus proving the last person will always be able to guess the colour of his Ball.

Cappella
Wednesday, July 24, 2002

Now just wait a second here....

The last sage can always guess the color of his ball, but ONLY if he gets a chance to guess!

Assuming that the sages can clearly see that the game only goes one round, the first and second sage will clearly GUESS what's on thier head (they're being threatened with not winning, not with losing thier heads) if they cannot infer from what's visible.  That changes the odds completely!  The odds are FAR from 10% A, 30% B, and 60% C.  Let's go through the combos again (blatant cut and paste) :

Combination 1: (10% chance of occuring)
--------------
B B W
A B C

A knows that he cannot know for certain the color of his ball, but the fact that one black and one white is visible will tell him that two white and one black are available.  He will GUESS white, going with the odds, and be incorrect.

B, having seen that A guessed white incorrectly, realizes that with one black and one white visible, it's clear that A guessed white (incorrectly) because he assumed two white balls were available (going with the odds).  Seeing that one of the whites is on C, not on himself, and the other black is on A, he must assume that he has the other black ball on his head and correctly calls "Black!".

B wins 10%

Combination 2: (20% chance of occuring)
--------------
W W B
A B C

Again, A sees that he cannot be sure of the color on his head, since two black are not visible.  However, he once again has a 66% chance of having a white ball on his head, so with nothing to lose, he guesses "White!" and is correct.

A wins 20%

Combination 3: (10% chance of occuring)
--------------
W W W
A B C

A sees two white balls, and having no assurances of what he has on his head, he is forced to hazard a guess.  He knows two black balls and one white ball are unaccounted for, so odds are that he has a black ball on his head.  He guesses, but incorrectly and is removed from the game.

B sees that A guessed black, and the only reason A would guess black would be if A could not account for one white and two black balls.  B reasons that he must therefore have a white ball visible on his head, and correctly guesses "white!"

B wins additional 10% (cumulative 20% so far)

Combination 4: (10% chance of occuring)
--------------
B W B
A B C

A once again sees that two white and one black ball are unaccounted for and guesses "White!" incorrectly once more.

B is completely aware that both black balls are on the other's heads and correctly guesses "White!"

B wins additional 10% (cumulative 30% so far)

Combination 5: (20% chance of occurring)
--------------
B W W
A B C

A sees that two white balls are accounted for, leaving two black and one white in limbo.  Playing the odds (correctly this time), A correctly guesses that he has a black ball on his head.

A wins additional 20% (cumulative 40% so far)

Combination 6: (20% chance of occurring)
--------------
W B W
A B C

A clearly sees that with one black and one white visible, two white and one black ball are unaccounted for.  He guesses "White!" and is again awarded the position as the Emperor's position as advisor.

A wins additional 20% (cumulative 60% so far)


Combination 7: (10% chance of occuring)
--------------
W B B
A B C

A can clearly see that with two black visible, "White!" is the only answer. 

A wins additional 10% (cumulative 70% so far)

----------------------------------
So... placing guesswork into the game, and given the various permutations that are possible, it's clear that C can correctly guess at the end of the first round if A and B remain mute, but any sage worth his salt plays the odds if there's nothing to lose (and disqualification isn't an issue if the game only goes one round).

In fact, if they guess based strictly on the odds, A wins a startling 70% of the time, and B manages to sneak off with the victory the remaining 30% using simple logic.  Poor C never gets a chance to speak at all.

Yes, the game is rigged, but the inability of the sages to correctly decipher the leaning of the game leads me to believe that they are in cahoots, as they'd only agree to tell the chinese emperor that the game was stilted so that "C always wins" (which he doesn't, even if they don't guess).  Clearly, this is a con job by the sages.

Stephen Hoffman
Wednesday, July 24, 2002

*  Recent Topics

*  Fog Creek Home