Author |
Topic: MOONSTONE (Read 3419 times) |
|
S. Owen
Full Member
Gender: 
Posts: 221
|
Here's how I understand the essence of this problem.
We've got three thieves who each have a bit of information (t1, t2, t3) - this info is whether (1) or not (0) that thief stole the Moonstone. They all want to know whether at least one ti is 1.
The coin flipping business means that there are three random bits (r1,2, r2,3, r3,1), each of which is known to exactly two thieves, respectively.
Finally, the winking means that they each communicate 1 bit (w1, w2, w3) to the other two thieves.
So, here we go...
The question is how each thief determines wi such that each thief knows whether at least one ti is 1. I believe this can be done if w1 = t1 ^ r1,2 ^ r3,1 ("^" is exclusive-or). w2 and w3 are the same.
Thief 1 already knows whether t1 is 1 of course - if it is then the rest doesn't matter. If it isn't, he wants to know whether t2 | t3 = 1. Since both can't be 1, this is equivalent to t2 ^ t3 = 1.
Now, rewriting the first equation above, we have that t1 = w1 ^ r1,2 ^ r3,1, and likewise for t2, t3. So, plug in - thief wants to know whether:
t2 ^ t3 =
w2 ^ r1,2 ^ r2,3 ^ w3 ^ r2,3 ^ r3,1 =
w2 ^ r1,2 ^ w3 ^ r3,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 t2 or t3 without knowing r2,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 w1 ^ w2 ^ w3 = t1 ^ t2 ^ t3. They saw two winks - say it was from 1 and 2 - but not the third. So they have w3 = t1 ^ t2 ^ t3; if they knew w3 then they'd know the value of t1 ^ t2 ^ t3, 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.
|
|
 IP Logged |
|
|
|
Chronos
Full Member
 
Gender:
Posts: 288
|
 |
Re: MOONSTONE
« Reply #1 on: Oct 3rd, 2002, 5:34pm » |
 Quote  Modify
|
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.
|
|
IP Logged |
|
|
|
luke's new shoes
Guest
|
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)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove