(The following is based on some recent joint work of myself, Dov Gordon, and Vinod Vaikuntanathan.)

Consider the following coin-weighing problem.

You are given coins, all-but-one of which weigh the same amount (say, 1 unit each). Call the outlier a “bad” coin. You have access to a scale that supports the following operation: you can place any number of coins on it, and ask whether the total weight of the coins on the scale is equal to some value. Since you know nothing about the weight of the bad coin, this is equivalent to asking whether some subset of the coins contains the bad coin or not.

How do you determine the bad coin in the fewest number of weighings? I’ll let you think about it for 1 paragraph; the solution is given below.

I am sure I have seen this question before, possibly in a list of interview questions. But when the question recently came up in the context of something I was working on, I couldn’t find any reference to this problem. If anyone is aware of one, please let me know.

Here is a solution using weighings, which is easily shown to be optimal. Number the coins (in binary) from to and define subsets , where contains all coins whose th bit is ‘1’. If we assign a ‘1’ to the indices of those subsets that weigh the wrong amount, we exactly recover the binary representation of the bad coin.

What about the general case, where there are up to bad coins? Generalizing the above, what we want is to associate each coin with a subset , indicating that coin is placed in sets (and then the sets are weighed as above). If we want this process to uniquely identify any set of or fewer bad coins, then the property we need is that the are –*union free*: basically, this means that the union of any two distinct collections of or fewer of the yield distinct subsets of . What is the dependence of on ? (A lower bound of is immediate.)

It turns out that this notion is tightly connected to a more familiar one, *cover free families* (a google search will turn up a definition). We showed:

Lemma:

Any -cover free family is also -union free. Conversely, any -union free family is also -cover free.

Cover-free families are well studied. Optimal (explicit) constructions are not known, but a result of Kumar, Rajagopalan and Sahai shows that is achievable.

What is the cryptographic connection? I’m simplifying a bit here, but imagine we want to perform batch verification of signatures where up to might be invalid. How quickly can we identify the bad ones, if we assume as an atomic primitive a way to identify whether any collection of signatures contains all valid signatures? (Obviously, this is only of interest if the cost is less than verifications of individual signatures. Schemes with this property are known.) The above approach gives a solution where only “batch verifications” are needed. (I want to point out that better solutions are known when the batch verifications performed (i.e., the sets ) can be chosen *adaptively*. In our case, we explicitly wanted a non-adaptive solution where the batch verifications could be parallelized. For further details, you will have to wait for the eventual paper.)

All-in-all, a fun problem with some neat connections to combinatorics.

Dear Jonathan,

The subject you should look into is Combinatorial Group Testing. The monograph by Ding-Zhu Du and Frank Hwang is authoritative.

t-cover-free families are equivalent to something called t-disjunct matrices (just the matrix whose columns are characteristic vectors of the sets in the family)

t-union-free families are equivalent to something called t-separable matrices.

The lemma you stated is well-known (see the textbook).

There are many known constructions showing that is possible, including a construction given in the following paper

Ely Porat, Amir Rothschild: Explicit Non-adaptive Combinatorial Group Testing Schemes. ICALP (1) 2008: 748-759

THere’s also a recent submission showing that we can attain AND efficiently “decode” the bad coins given the weighing outcomes. (Please email me for details if you’re interested.)

If you want a super-quick reference to non-adaptive combinatorial group testing, this (old) survey probably helps:

http://www.cse.buffalo.edu/~hungngo/papers/dimacsCGT.pdf

Regards,

Hung

By:

Hung Q. Ngoon July 24, 2009at 10:21 pm

Just a typo:

In the para above the Lemma, k > log(n\choose t) = O(t logn)

By:

ranjiton July 25, 2009at 12:02 am

Hung, thanks very much for the pointers!

By:

jonkatzon July 25, 2009at 9:18 pm

In the second half of your problem (when there is more than one bad coin):

What happens if one bad coin weighs 1.5 units and the other weighs 0.5 units? Can you tell them apart from two good coins if they’re weighed together?

By:

Kevin C.on July 27, 2009at 11:29 am

Ranjit – thanks, I corrected it.

Kevin – Sorry I didn’t make it clear. The assumption is that the weights of the bad coins do not “cancel out”. (If you want, you can imagine they are all light or all heavy.) For the particular application to signatures, one has to prove that multiple “bad” signatures can never combine to give a positive batch verification.

By:

jonkatzon July 27, 2009at 11:40 am

Also a reference: http://www.jstor.org/pss/2975353

By:

helgeron July 28, 2009at 12:41 pm

Helger – thanks for the link.

I should make clear that I was able to find lots of references for the version of the problem where the scale indicates whether the pile of coins being weighed is heavy, light, or the correct weight. But in the variant of the problem discussed in the post, the scale only tells you whether the weight is correct or not.

By:

jonkatzon July 28, 2009at 2:21 pm

You may also look at

http://eprint.iacr.org/2009/240

By:

Anonymouson July 29, 2009at 10:58 am