The Mystery of Counterfeit Coins

I came across this very interesting coin weighing puzzle on Concrete Nonsense blog (with a hat tip to Tanya Khovanova). It might sound familiar but I can assure you that it’s not that one! The solution involves the concept of zero-knowledge proof.

First, let’s start with a warm-up version, shall we?

You present 100 identical coins to a judge, who knows that among them are either one or two fake coins. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real ones.

You yourself know that there are exactly two fake coins and you know which ones they are. Can you use a balance scale to convince the judge that there are exactly two fake coins without revealing any information about any particular coin?

This one is quite easy to solve. You can divide the coins into two equal groups. And when the judge sees that both groups balance on the scale (i.e. have equal weight), she is convinced that there can’t be one fake coin. Which means that there are two fake coins.

Note that the this solution doesn’t reveal any information about any particular coin (i.e. the judge doesn’t know if any particular coin is fake or real – all coins are equally likely to be fake or real). However, in addition to proving that there are two fake coins, some additional information is also passed on to the judge.

Initially, if the judge randomly picked two coins from the pile, the probability that she picked the fake coins is 1 out of 4950. (The probability that the first coin is fake is 2/100 since initially there are two fake coins. And the probability that the second coin that the judge picked is also fake is 1/99 since there is one fake coin left in the remaining 99 coins. By multiplying both probabilities, you get the combined probability of both coins being fake. Alternatively, you can get this number by doing ‘2 choose 100’ — which equals 4950.)

After you divide the coins into two groups and show that there is one fake coin in each one, the judge can now pick two fake coins with a probability of 1/2500. (The probability of picking a fake coin from each of the two groups is 1/50. Hence, overall probability of picking two fake coins is 1/50 multiplied with 1/50 = 1/2500.)

This shows that the solution is not a zero-knowledge proof. The judge has greater chances of picking the fake coins after your illustration – the probability increased from 1/4950 to 1/2500.

Now keep that (concept of zero-knowledge proof) in mind and let’s move on to the next level:

A judge is presented with 100 coins that look the same, knowing that there are two or three fake coins among them. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real.

You yourself know that there are exactly three fake coins and you know which ones they are. Can you use a balance scale to convince the judge that there are exactly three fake coins, without revealing any information about any particular coin?

If you’re thinking that this one is also easy like the previous one, think again!

Please don’t read further if you want to try to solve this puzzle yourself.

For example, dividing the coins into three groups with 33 coins in each and leaving one coin aside, and then showing that those three groups weigh equal does prove that there are three fake coins BUT what about the coin that you put aside? The judge is certain now that the coin that was put aside is real. That’s a deal breaker. Remember, you can’t reveal information about any particular coin.

***

Here’s one solution that I initially thought of:

Split the coins into two groups with 50 coins in each. Keep two fake coins in group A and one in group B. Group A will weigh lighter on the scale. Now let’s say the judge thinks that there are only two fake coins. In that case, she is convinced that both fake coins are in group A, because A weighed lighter.

To prove the judge wrong, all you needs to show is that group B also contains one fake coin.  Which can be easily shown by dividing group B in half – let’s call them B1 and B2 (25 coins in each). Upon balancing B1 and B2, and seeing they don’t balance equally, it’s proven that group B also contains one fake coin. Hence, the judge’s assumption (that there are only two fake coins) is wrong. Which obviously  means that there must be three fake coins.

But the problem with this solution is that it’s not a zero-knowledge proof.

***

Here’s another solution by Mary from the comment section of Tanya Khovanova’s blog post:

Make three groups A, B and C, with 32 coins in each one. And put four coins aside for now. Three consecutive weighing will show the equality of weights among A, B and C. Then swap those four coins that were initially set aside with four coins from A, B and C. And three more consecutive weighing can demonstrate that A, B and C weighs the same – which proves that each group contains one fake coin (either in the first round or in the second.)

Further Explanation: Let’s say you put aside three fake coins – let’s say w,x,y – and a real one – z. Hence, all three groups contain all real coins. Now after demonstrating that A, B and C weighs equal, you can swap w with a real coin from A, x with a real coin from B, and y and z with two real coins from C. After the swap, the A, B and C will still balance because there is exactly one fake coin in each group. Another possibility is that you can put aside four real coins initially. In that case, all three groups will still weigh equally before the swap, as well as after the swap – you can swap in such a way that each of the three groups end up with exactly one fake coin or replace all fake coins with a real one so that A, B and C contain no fake coin.]

Note that in any case, the judge has no way of knowing whether the initial four coins were all real or three fake plus one real.

Do you think this is a zero-knowledge proof? (I think it is.)

Are there any other solutions that you can think of?

***

P. S. If you liked that concept of zero-knowledge proof, here’s another interesting problem: [The Millionaire Problem] Alice and Bob are two millionaires who want to find out who is richer without revealing the precise amount of their wealth. [Solution]