Algorithm Design- Identify single bottle in wine cellar with fewest testers

Question

This is for extra credit in an algorithms class. The problem states

A king has a wine cellar of N bottles, and a single bottle has been poisoned.
The poison takes approximately a month to work. The king wants the exact bottle identified using the fewest testers possible within a months time.

My solution is

• Split up the N bottles into M lots and use ``M testers

  • The first tester tastes both the first and last lot

  • The second tester tastes both the first and second lots.

  • The third tester tastes both the second and third lots.

  • Continue on for M lots, with testers overlapping lots.

• When the two testers that tasted the tainted wine become ill, the lot has been identified. The M-2 testers left each taste one bottle from the tainted lot, and the third tester that becomes ill identifies the tainted bottle.

However, this algorithm requires double the time allotted to work: one month to identify the tainted lot, and a second month to identify the tainted bottle. Is there a more efficient algorithm?

Answer 1

We can do it with log2(N) testers with a pretty neat algorithm.

Let me demonstrate it with a simple example. Assume N = 1000.

If we label the bottles 0 through 999, then each bottle can be represented by a unique binary number ranging from 0000000000(0 decimal) to 111100111(999 decimal).

Claim: we only need 10 testers to find the poisoned bottle. Note: log2(N) = log2(1000) = 10.

Algorithm: for the Mth bottle, we first get the 10-bit binary representation of M. If the ith bit of the binary number is 1, we let the ith tester to drink the wine from the bottle. Note: 0 < M <1000, 0 < i <10.

Consider an example where we have the 1st, 4th, 9th tester being dead and other testers being alive after a month. We conclude that the 289th bottle is the poisoned one since 0100100001 is the binary representation of the decimal number 289.

Why are 10 testers enough to identify the poisoned one among 1000 bottles?

Because with 10 testers each being dead or alive in the end, we can have a total of 1024 combinations, each of which can be used to uniquely identify one bottle as poisoned from as many as 1024 bottles.

Answer 2

This is a classic puzzle, so I don't want to immediately give the answer away, but here's a hint: suppose you split up the wine bottles into two groups, each of which contains half the bottles, then have one person test each half. That would give you a way to narrow down which bottle is poisoned to one half of the bottles.

So the question is this - is there a way to come up with lots of different ways of splitting up the wine bottles into halves and running the above approach in parallel? As a hint, think about the binary representation of N.

Hope this helps!