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]

Advertisements

4 responses to “The Mystery of Counterfeit Coins

  1. gaurav

    i dont think the solution by mary is zero knowledge proof, because the judge can pick 3 fake coins with probability 1/33 ^3 after the solution. whereas prior to solution, the probability was much less i.e. 1/100C3. But probably, this solution reveals least knowledge about coins.

    • Remember that you could have either put aside three fake coins OR four fake coins. In both scenarios, the piles would weigh equally – before and after the swap. Assuming that you are equally likely to go with scenario I or II, you’re not sabotaging the initial probability. The judge has no way of knowing whether she’s dealing with scenario I or II.

      Your explanation is valid if you always went with scenario I — i.e. you always put three fake coins in each pile in the beginning.

      Does that make sense?

  2. gaurav

    consider three sets A1,B1,C1, formed by adding to A,B, and C respectively the coins that were lying aside for swap. Then A1 and B1 have 33 coins each and C1 has 34 coins. Now are’nt we sure that A1,B1 and C1 have one fake coin each.

    In fact, there can be many similar solutions, eg. for any n from 17 to 32, let A,B, C have n coins each. 100-3n coins lie aside. As n >=17, 100-3n< 3n. This ensures that all coins aside can be swapped. Show A, B and C to be equal. Then swap all coins lying outside and again show A,B and C to be equal.

    Hope I m correct.

    • consider three sets A1,B1,C1, formed by adding to A,B, and C respectively the coins that were lying aside for swap. Then A1 and B1 have 33 coins each and C1 has 34 coins. Now are’nt we sure that A1,B1 and C1 have one fake coin each.

      We can’t be sure that A1, B1 and C1 have exactly one fake coin each. Because (1) the judge doesn’t know whether there are 2 or 3 fake coins, and (2) since C1 doesn’t weigh equal any more with A1 and B1 after the swap, there’s a possibility that C1 contains ALL fake coins.

      If that’s unclear, consider this: from judge’s POV, there could have been two fake coins in the first set-aside group. And after the swap both A1 and B1 has one fake coin each (that’s why they weigh equal.) Alternatively, C1 can have both of those fake coins.

      for any n from 17 to 32, let A,B, C have n coins each. 100-3n coins lie aside. As n >=17, 100-3n< 3n. This ensures that all coins aside can be swapped. Show A, B and C to be equal. Then swap all coins lying outside and again show A,B and C to be equal.

      For N=32, if C has more coins (i.e. 34) than A and B (i.e. 33) after the swap, how can it weigh equal to the other two groups?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 66 other followers

On Twitter

Categories

%d bloggers like this: