Newsgroups: rec.puzzles
From: hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: 3 Aug 92 21:21:23 GMT
Subject: Re: Gummy Drop-bears (spoilers and discussion)

In a newsgroup clogged with vacuous inanities, endless quibbles over
carelessly posed problems, futile FAQs, definitions of decimals, and
now even the noisome overflow from sci.physics, it is most refreshing
to see cl...@remus.rutgers.edu (Chris Long) favor us with a new,
interesting puzzle:

> Real gummy drop-bears mass 10 grams, while imitation gummy
> drop-bears mass 9 grams.  Spike has 7 cartons of gummy drop-bears, 4
> of which contain real gummy drop-bears, the others imitation.  Using
> a scale only once and the minimum number of drop-bears, how can
> Spike determine which cartons contain real gummy drop-bears?

k...@cs.cornell.edu (David Karr), d...@hpnmdla.sr.hp.com (Dan Merget),
and a...@troi.cc.rochester.edu (Andrew Markiel) all provided the
51-bear solution of taking 0, 1, 2, 4, 7, 13, and 24 bears from the
respective boxes.  Certainly that selection serves to distinguish the
possible sets of imitations, but I would like a proof that this set is
the bear minimum.  I already have a program that says so, but I have
a fondness for succinct proofs.  And the methods of David, Dan, and
Andrew are not apparently rigorous in determining the minimal solution.

Andrew got the solution by starting with 0, 1, and 2 and making the
other numbers be the sum of the previous three.  But if Spike had ten
cartons among which to determine the three cartons of imitations,
Andrew would tell him to take 0, 1, 2, 4, 7, 13, 24, 44, 81, and 149
bears from the respective cartons.  Spike could do better by taking
only 139 from the last carton, and still determine the bogus bears in
a single weighing.

David and Dan appear to proceed by taking the minimum possible from
each box in turn, such that they find a solution.  But this is a
greedy algorithm, in which by taking fewer bears from one carton they
might conceivably force themselves to take more bears from a later
carton.  For instance, if Spike had EIGHT cartons, only TWO of which
were fake, David and Dan would have him choose 0, 1, 2, 4, 7, 12, 20,
and 29 bears from the respective cartons.  But that requires 75 bears,
while a 72-bear solution exists: 0, 1, 2, 4, 8, 14, 19, and 24 bears.

Searching for a case in which the greedy algorithm does not provide an
optimal solution for identifying three bogus cartons turned out to be
surprisingly difficult, though.  My program tells me that greed is a
perfectly good strategy up to ten boxes.  But for finding three bad
cartons in a consignment of eleven, the greedies would have us take 0,
1, 2, 4, 7, 13, 24, 44, 81, 139, and 234 bears, for a total of 549.
We can, however, save eleven bears by taking 0, 3, 5, 6, 7, 14, 25,
44, 79, 133, and 222 bears.  (The program for this takes a long time.
It has not yet concluded that this is the optimum, though I suspect it
will soon.  It has already elminated all cases in which the second
number is less than 13.)

I imagine this problem must be addressed in the literature somewhere,
and I would appreciate a word from anyone who recognizes it.
Especially if the literature has some approaches to succinctly
proving optimality.  I expect that with a little work we can shew the
optimality of the solution for the original seven-carton problem, in
a way that could be appreciated by a human.  But barring some truly
amazing insight, I suspect the proof for the eleven-carton problem is
reading matter for our electronic brethren only.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil