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.
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,