## IBM Research Ponder This: August 2016 Puzzle

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 $k$ coins from bag $k$, 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 $n$ of coins available in each bag (where, for example, $n=1000$ above)?  From the IBM Research page:

If $n \geq 1024$ 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 $2^{10}=1024$ 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 $n=512$ 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 $n$ (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.]

This entry was posted in Uncategorized. Bookmark the permalink.

### 4 Responses to IBM Research Ponder This: August 2016 Puzzle

1. mtbusche says:

274

• possiblywrong says:

Wow– can you describe your solution? The best approach I know of so far requires 309, taking (148, 225, 265, 285, 296, 302, 305, 307, 308, 309) from each bag.

• mtbusche says:

Uhmm….no. I don’t have a solution! I was guessing. I wrote software that found these solutions for smaller cases:

#Bags: Coins
1 1
2 1, 2
3 1, 2, 4
4 3, 5, 6, 7
5 3, 6, 11, 12, 13
6 11, 17, 20, 22, 23, 24
7 20, 31, 37, 40, 42, 43, 44

But it looks like 8 bags might take a month of run time. I put the numbers 1, 2, 4, 7, 13, 24, 44 into the oeis database and it came up (weirdly) with the tribonocci sequence. The 10th term in the sequence is 274, but it was beyond me as to why the tribonocci sequence might match the number of coins you need in each bag. The two problems seem unrelated, but it is strange that the first 7 numbers match. I thought I’d boldly guess the answer anyway and hoped you’d explain.

So how were you using oeis to gain insight into this problem?

2. mtbusche says:

I guess I didn’t look at the search results carefully. There were actually 9 matches! Holy smokes! And I’ve now found the sequence that matches your problem.

This site uses Akismet to reduce spam. Learn how your comment data is processed.