wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> MOONSTONE
        
(Message started by: S. Owen on Oct 1^st, 2002, 9:38pm)

Title: MOONSTONE
Post by S. Owen on Oct 1^st, 2002, 9:38pm

Here's how I understand the essence of this problem.

We've got three thieves who each have a bit of information (t₁, t₂, t₃) - this info is whether (1) or not (0) that thief stole the Moonstone. They all want to know whether at least one t_i is 1.

The coin flipping business means that there are three random bits (r_1,2, r_2,3, r_3,1), each of which is known to exactly two thieves, respectively.

Finally, the winking means that they each communicate 1 bit (w₁, w₂, w₃) to the other two thieves.

So, here we go...

The question is how each thief determines w_i such that each thief knows whether at least one t_i is 1. I believe this can be done if w₁ = t₁ ^ r_1,2 ^ r_3,1 ("^" is exclusive-or). w₂ and w₃ are the same.

Thief 1 already knows whether t₁ is 1 of course - if it is then the rest doesn't matter. If it isn't, he wants to know whether t₂ | t₃ = 1. Since both can't be 1, this is equivalent to t₂ ^ t₃ = 1.

Now, rewriting the first equation above, we have that t₁ = w₁ ^ r_1,2 ^ r_3,1, and likewise for t₂, t₃. So, plug in - thief wants to know whether:
t₂ ^ t₃ =
w₂ ^ r_1,2 ^ r_2,3 ^ w₃ ^ r_2,3 ^ r_3,1 =
w₂ ^ r_1,2 ^ w₃ ^ r_3,1 = 1

But thief 1 has all the bits in the last equation, and therefore can know whether one of them has stolen the Moonstone even in the case where he himself didn't. But he doesn't know which of the other two did; he can't know t₂ or t₃ without knowing r_2,3, which is the coin flip he didn't see.

But does the surveillance team learn anything? Assume that they even know what the winks "mean". Note from above that w₁ ^ w₂ ^ w₃ = t₁ ^ t₂ ^ t₃. They saw two winks - say it was from 1 and 2 - but not the third. So they have w₃ = t₁ ^ t₂ ^ t₃; if they knew w₃ then they'd know the value of t₁ ^ t₂ ^ t₃, and thus whether one of them stole the Moonstone. But they don't. They also don't know any of the random flips. Therefore I don't believe they gain any information.

Title: Re: MOONSTONE
Post by Chronos on Oct 3^rd, 2002, 5:34pm

Quote:

Therefore I don't believe they [the surveilance team] gain any information.

Depends, of course, on what you mean by "information". They do now know that the thieves have communicated, etc., and that the thieves all now know whether it's been stolen. This might be very useful information, if they get the opportunity to plea bargain with the suspects. Shades of Prisoner's Dilema, here.

Title: Re: MOONSTONE
Post by luke's new shoes on Nov 13^th, 2002, 6:31pm

each of the criminals is present for 2 flips of the coin. they will either view 2 flips that are the same, or 2 flips that are different. and either that person stole the gem or they didnt.
this makes four possible senarios for each person.

*they stole the gem and the 2 flips they saw were the same: in this senario the person winks their right eye.

*they stole the gem and the 2 flips they saw were different: in this senario the person winks their left eye.

*they didnt steal the gem and the 2 flips they saw were the same: in this senario the person winks their left eye.

*they didnt steal the gem and the 2 flips they saw were different: in this senario the person winks their right eye.

if none of them stole the gem then there will either be 3 right winks, or 2 left winks and a right wink (depending on the combination of heads and tails).

if one of them stole the gem there will either be 3 left winks, or 2 right and a left.

(because the cops only seen 2 of the criminals wink, they cant work out if one of them stole the gem)