Posted by: yanzhang | December 17, 2009

M-3: Coins and Low-Knowledge Proofs

This puzzle was presented by Tanya Khovanova at a casual combinatorial meeting, apparently from some Russian olympiad for middle/high-schoolers. I really like this type of problem since I haven’t seen it before (also, it starts in a way that makes most people think “oh I’ve seen this before…” only to be wrong). Before I present the problem, we will look at a “baby version” to see how the problem works (this is also another excuse to make a Matryoshka problem).

We have 100 coins. Both Cecil and Lisa know the fact that “there are either 1 or 2 counterfeit coins.” Counterfeit coins have the same weight and are lighter than real coins. Given that Lisa knows that there are actually 2 counterfeit coins instead of 1 (and knows exactly which coins they are), find a way for Lisa to prove this fact to Cecil, aided with just a balance, such that at the end of the proof Cecil now knows there are 2 counterfeit coins but does not know the identity of any particular coin.

Proof:

Lisa puts 50 coins on either side of the balance, such that each side contains 1 counterfeit coin. The balance will then be balanced. Cecil then knows that we must have an even number of counterfeit coins. Since he knows there are either 1 or 2, he can deduce there must be 2 instead of 1. However, he does not know whether any particular coin is real or counterfeit.

I like the flavor of this problem, because it is similar to the concept of zero-knowledge proofs, but it isn’t quite “zero-knowledge.” In the above example, we gain some information about pairs of coins (i.e. no pair of coins on either side are both counterfeit). However, note that the probability of each coin being counterfeit, if Lisa used uniform distributions to scramble her coins, remains uniform.

Now, the followup. This is quite a bit harder, and I spent a long time on the problem without getting it:

This time, both Cecil and Lisa know the fact “there are 2 or 3 counterfeit coins.” Find a way for Lisa to prove to Cecil that there are actually 3 counterfeit coins, subject to the same conditions as above.

Proof and analysis:

(this proof is due to Alan Deckelbaum). Split the coins into 4 groups A, B, C, D of size 36, 32, 16, and 16 respectively. Put 1 counterfeit coin in C, D, and one in A.

1) Balance C and D. They will balance. This gives Cecil the information that C and D both have either 0 or 1 counterfeit coins.

2) Balance C+D and B. B will be heavier. This gives Cecil the information that C + D must have at least 1 counterfeit coin (note this does *not* give away any information about any particular coin in B, since B could have had either 0 or 1 counterfeit coins). Given the information gained in the previous step, Cecil now knows that both C and D have exactly one counterfeit coin in each.

3) Split C into two groups, C_1 of size 6 and C_2 of size 10, such that the counterfeit coin is in C_2. Now balance A+C_1 against B+C_2. They will balance. From this, Cecil knows that between A, B, and C, we have exactly 2 counterfeit coins (since C had 1), or equivalently, there was 1 counterfeit coin in A+B. Thus, there are 3 counterfeit coins, and we’re done.

The crucial part of the argument is that Lisa could have theoretically put the other counterfeit coin in A or B (even though she put it in A), so this does not show the identity of any coin in A or B.

I really like the idea used in this proof. Of course, this naturally brings up a third question, to which I do not know the answer, although I highly suspect this is impossible:

Given the same setup as above, find a way for Lisa to prove to Cecil that there are actually 3 counterfeit coins, with the additional constraint that knowing Lisa’s algorithm (which could be probabilistic), Cecil has no way of finding a coin whose probability of being counterfeit is different from 3/100.

This is the “almost zero-knowledge” condition satisfied by the baby version of the problem. Although Cecil gained some knowledge (about the distribution of pairs of coins), if Lisa scrambles coins uniformly, even knowing her algorithm Cecil cannot find two coins, one of which is “more likely” to be counterfeit. However, in the proof of the harder version of the problem, Cecil can just pick a coin randomly from C or D, both of which have probability 1/16 to be counterfeit, as opposed to 3/100. Intuitively, this seem to require (can this be proven?) that we must split the coins into groups of the same size, and never break these groups when weighing. I’ve been unable to find a solution with this property.

There are also many more clear natural extensions of this problem (giving a set A of possible numbers of values, proving that the number of coins is in some specified subset B in A, etc.), none of which I’ve solved or think are easy.

Happy winter break,
-Yan

Advertisements

Responses

  1. So Lisa knows the identity of the counterfeit coins. That’s not clear from the question.
    Thinking about it, if Lisa only knows that there are 2 counterfeit coins and doesn’t know which ones they are, is it possible to prove to Cecil that there are 2 coins with out giving away or discovering the identity of the coins? I haven’t thought about it much, but the answer is probably no.

  2. Hmm, I didn’t think about that version at all, probably for the same reason you say “probably no.” I feel she has way too little information in that case.

  3. Instead of splitting the coins into 4 groups, how about this:

    – Split the coins into two groups with 50 coins in each. Keep 2 fake coins in group A and 1 in group B.

    – Balance A and B – group A will weigh lighter.

    – Now let’s say Cecile thinks that there are only 2 fake coins. In that case, he is convinced that both fake coins are in group A, because A weighed lighter. (In other words, he would think that if one fake coin was in A, and the other in B, then both groups would have balanced. They didn’t. Hence, the lighter group must contain both fake coins.)

    – To prove Cecile wrong, Lisa needs to show that group B also contains one fake coin.

    – She can easily show that 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, it’s proved that group B also contains one fake coin.

    – Hence, Cecile’s assumption (that there are only 2 fake coins) is wrong. Which means that there are 3 fake coins. (Note that he knew that there were either 2 or 3 fake coins.)

    The probability of finding the fake coin here is reduced to 1/25 (which is not as good as 3/100 but better than 1/16).

    Vishal

  4. Late to the party but a 3/99 solution to the second problem :

    divide the coins into three groups of 33 and one group of 1 such that each group of 33 has a counterfeit coin. Then using the balance show that all of the groups of 33 have the same weight. This means that either each group of 33 has a counterfeit coin (3 coins), or they have none (0 or 1 coin which contradicts the assumption that there are 2 or 3 coins)


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

Categories

%d bloggers like this: