Jewel Thieves and a Stolen Gem

The Moonstone has been stolen. Police have three suspects under surveillance—three of the city’s most notorious jewel thieves—but no evidence to arrest any of them. Each thief, denying involvement, has publicly wondered: who took it this time?

The surveillance team observes the three dining together. During the meal, each thief leaves the table to visit the lavatory. Whilst one is away, the two remaining thieves flip a fair coin, hiding the result from both the absent thief and the watching police. After the third thief returns, all three wink at each other and disperse silently.

From what they observed, the surveillance team concludes that all three thieves now know whether one of them stole the Moonstone, but if one did steal it, the other two don’t know which one. The police still don’t know whether any of them is guilty.

How did the thieves communicate this information using only coin flips and winks?

Hint

Each pair of thieves saw exactly one coin flip together. What information does each thief have after all three coins have been flipped?

Hint

Consider what happens if each thief computes a simple function of the two coin results they saw, then winks based on that computation.

Hint

If all three thieves are innocent and follow the same protocol, how many winks would you expect to see in total? What property ensures this number is consistent?

Hint

How could a guilty thief alter their behaviour to signal their guilt whilst still preventing the other two from identifying them?

Solution

Answer: There are multiple solutions, but here’s a possible strategy they could be using: each thief winks if both coin flips they see are different. A guilty thief does the opposite, winking if both coin flips are the same.

Let’s label the thieves $X$ , $Y$ , and $Z$ . Three coins are flipped:

$C_{X Y}$ : seen by $X$ and $Y$ (whilst $Z$ was away)
$C_{X Z}$ : seen by $X$ and $Z$ (whilst $Y$ was away)
$C_{Y Z}$ : seen by $Y$ and $Z$ (whilst $X$ was away)

Represent heads as 1 and tails as 0.

Each thief computes the XOR of the two coins they saw:

$X$ computes: $C_{X Y} \oplus C_{X Z}$
$Y$ computes: $C_{X Y} \oplus C_{Y Z}$
$Z$ computes: $C_{X Z} \oplus C_{Y Z}$

The protocol: if the result is 1 (i.e. the coins are different), wink. If the result is 0 (i.e. the coins are the same), don’t wink.

Notice that the total number of winks has a fixed parity. Computing the XOR of all three values:

\begin{matrix} X \oplus Y \oplus Z = (C_{X Y} \oplus C_{X Z}) \oplus (C_{X Y} \oplus C_{Y Z}) \oplus (C_{X Z} \oplus C_{Y Z}) \\ = (C_{X Y} \oplus C_{X Y}) \oplus (C_{X Z} \oplus C_{X Z}) \oplus (C_{Y Z} \oplus C_{Y Z}) \\ = 0 \oplus 0 \oplus 0 \\ = 0 \end{matrix}

Each coin appears exactly twice in this expression. Since $a \oplus a = 0$ for any bit $a$ , all terms cancel out. Thus, the total XOR is always 0.

This means the total number of winks is always even: either 0 winks (if all three XOR results are 0) or 2 winks (if exactly two XOR results are 1). We can never have 1 or 3 winks if all thieves follow the protocol honestly.

Now suppose one thief is guilty. That thief inverts their behaviour: they wink if their XOR is 0, and don’t wink if their XOR is 1. This adds 1 to the total XOR.

Without loss of generality, let’s assume the thief is $X$ .

\begin{matrix} X \oplus Y \oplus Z = (C_{X Y} \oplus C_{X Z} \oplus 1) \oplus (C_{X Y} \oplus C_{Y Z}) \oplus (C_{X Z} \oplus C_{Y Z}) \\ = (C_{X Y} \oplus C_{X Y}) \oplus (C_{X Z} \oplus C_{X Z}) \oplus (C_{Y Z} \oplus C_{Y Z}) \oplus 1 \\ = 0 \oplus 0 \oplus 0 \oplus 1 \\ = 1 \end{matrix}

The total number of winks becomes odd: either 1 or 3.

The protocol reveals:

Even number of winks (0 or 2): None of them stole the Moonstone
Odd number of winks (1 or 3): One of them is guilty

The other two thieves can’t determine which one inverted their behaviour—they only know someone did.

However, this is only one such possible protocol. If the thieves instead decided that they should wink if both coins flips are the same, then an even number of winks would indicate that one of them is guilty. As such, the police learns nothing from this surveillance.

Jewel Thieves and a Stolen Gem

Try These Next

Planting Trees 3

Chomp 1

Equal Shape Cutting 4