This month’s IBM Research puzzle is pretty interesting: it sets the stage by describing a seemingly much simpler problem, then asking for a solution to a more complicated variant. But even that simpler problem is worth a closer look.
I won’t spoil the “real” problem here– actually, I won’t approach that problem at all. Instead, let’s start at the very beginning:
Problem 1: You have 10 bags, each with 1000 gold coins. Each coin should weigh exactly 10 grams, but one of the bags contains all counterfeit coins, weighing only 9 grams each. You have a scale on which you can accurately measure the weight of any number of coins. With just one weighing, how can you determine which bag contains the counterfeit coins?
This is a standard, job-interview-ish, “warm-up” version of the problem, with the following solution: arbitrarily number the bags 1 through 10, and take coins from bag , for a total of 55 coins. If all of the coins were genuine, the total weight would be 550 grams; the measured deficit from this weight indicates the number of the counterfeit bag.
So far, so good. The IBM Research version of the problem extends this in two ways (and eventually a third): first, what happens if more than one bag– or possibly none of the bags– might be counterfeit? And second, what if there is a limited number of coins available in each bag (where, for example, above)? From the IBM Research page:
If then one can identify the [subset of] counterfeit bags using a single measurement with an accurate weighing scale. (How?)
That is, instead of knowing that exactly one bag is counterfeit, any of the possible subsets of bags may be counterfeit, and our objective is to determine which subset, with just a single weighing of coins carefully chosen from each bag.
The motivation for this post is that, although the statement above seems to telegraph the intended elegant solution to this “warm-up” version of the problem, (a) that intended solution can actually be implemented by requiring only coins in each bag, not 1024; and (b) even this stronger bound is not tight– that is, even before approaching the “real” problem asked in this month’s IBM Research puzzle, the following simpler variant is equally interesting:
Problem 2: What is the minimum value of (i.e., the minimum number of coins in each bag), for which a single weighing is sufficient to determine the subset of bags containing counterfeit coins?
Hint: I ended up tackling this by writing code to solve smaller versions of the problem, then leaning on the OEIS to gain insight into the general solution.
[Edit: The puzzle statement on the IBM Research page has since been updated to reflect that the “nice”– but still not tight– bound is 512, not 1024.]