Fog Creek Software
Discussion Board




chinese emperor partial solution

You have 3 scenerios...
Say the people are labeled 1,2,3 and their stone is B or W. Since these are sages we will also assume they go with the odds when they aren't certain.

If you have 1 B, and 2 B, then 3 will know his stone must be white.

If you have 1 W, and 2 B, then you have to go my what 1 says. If he thinks he has a W, then it is because he sees 3 has a B. If he says he has a B, then it is because he sees 2 has a B and 3 has a W and he has better odds at picking W since there are 2 available verses 1 B. Same thing goes for the case where you have 1 B and 2 W.

If you have 1 W and 2 W then you go with what 1 and 2 say. If 3 has W also, then 1 and 2 will think they gave B since there would only be 1 available W and 2 B stones. If 3 has B, then 1 and 2 will think they have W using the same logic.

I'm not sure what to do if 1 and 2 pass on their turn. If they do, that doesn't seem to give 3 anymore insight then they have and would prevent 3 from having an advantage unless 1 and 2 have black stones.

Tom
Monday, January 03, 2005

The first one can only see one of the 3 cases, 2 B, 2W, or B & W. He can say W for sure if he saw 2 B. In other cases, he should say pass for the next turn.

If the 2nd one heard the 1st one said W, he would say B. Otherwise, if he saw the 3rd has B, he would be able to say W for sure. I think he had to say pass if he saw the 3rd one had W.

Now, the 3rd one know what he has for sure. If 1st said W, or the 1st pass and the 2nd one said W, the 3rd one would say B. If both the 1st and 2nd passed, He would say W.

Simon
Friday, January 07, 2005

A very clear solution!
There are seven possible cases (first - second - third):

(1)    W      W      W
(2)    W      W      B
(3)    W      B      W
(4)    W      B      B
(5)    B      W      W
(6)    B      W      B
(7)    B      B      W

The first sage says white only if he sees 2 black balls (case 4).  Otherwise, he passes.

If the first passed, the second sage knows he is in case 1, 2, 3, 5, 6 or 7. He knows he has a white ball if the third sage has a black ball (cases 2 and 6). Otherwise, he passes (he cannot distinguish between cases 1 and 3, and between cases 5 and 7)

The third knows his color in all cases: if the two sages before him passed, it is white (case 1, 3, 5 or 7), otherwise, it is black (case 2, 4 or 6).

Mark
Saturday, January 08, 2005

Another way of stating the same solution is:-
I assumed that nobody is going to make wild guess.

Lets say there are 3 persons are P, Q and R and turn to answer starts from P.

Three sets of answer are possible for this are:-
a) color
b) Pass, Color
c) Pass, Pass, colour

(color --> correct guess of the ball over that person's head :)

case a: P has seen 2 B balls on the heads of Q and R (W, B and B over P, Q and R respectively)

case b: P has seen 1 W, 1B ball over Q and R.

case 1b: W, W and B over P, Q and R
        Q can definitely tell his is W ball because he is sure
        from P's reply that 2 B cant be there and he can see 
        one over R.

case c: P has seen either 2W balls or 1W, 1 B ball over Q 
            and R
case 1c: W, W and W over P, Q and R
case 2c: W, B and W over P, Q and R

solution for above 2 sub cases is here:
        R will conclude from P's reply(pass) that either 2W or
        1W and 1B balls are there over Q and R.

        and Q's reply (pass) will confirm him that Q is not able
        to see and B ball, so he can answer correctly seeing
        the ball on Q's head. 

Vivek Gupta
Tuesday, February 08, 2005

I made these assumptions:
(a) guesses are made sequentially
(b) the first correct guess wins instantly and stops the game
(c) each person can hear the previous guesses
(d) nobody is dumb enough to throw away a sure win.

Now - if you know there's never going to be a 2nd turn, why would
anybody ever pass?  C will always know her color unless A and B lose
on purpose, so by assumption (b) there will never be a Round Two.

cases:
  (1)  C is black.  B is black.  A has a sure win.
  (2)  C is black.  If A doesn't win, B has a sure win because of (1) and (d).
  --> A should at least guess.

  (3) C is white.  If A or B doesn't win, C has a sure win b/c of (1) and (2) and (d).
  --> A and B should guess.

In case (3), if A guesses with the odds and loses, B knows her color based on
A's guess.  So unless A or B is illogical, C never even gets to guess.
Nobody ever passes.  A wins 70% of the time, B wins 30%.

I think I've seen the problem stated such that you get killed for wrong guesses.

betty
Thursday, February 24, 2005

*  Recent Topics

*  Fog Creek Home