Michael Kleber: “Poisoned Wine Bottles, Not Enough Rats”
You have 1000 bottles of wine, two of which are poisoned, and you have to figure out which ones using ten taste-tester rats working ‘non-adaptively.’ First you pick which bottles of wine each rat tastes from, and only afterwards do you learn whether each rat died. How would you figure out which bottles are poisoned?
If you try to find the poisoned bottles using the fewest rats, you’re doing ‘combinatorial group testing’. But with only ten rats, that’s information-theoretically hopeless. The goal instead is to discard as few bottles as possible and be sure the rest are safe to drink.
Can you figure out how to use the ten rats and save all but 200 bottles of wine? Good, then how about 120? Under 100? Under 80?!
Join Michael Kleber as he explores the mathematics behind answering these very questions.
Buy It
Kleber began his career as a mathematician working on efficient algorithms in combinatorics, then worked on efficiency in computational biology and in speech recognition before landing at Google, where he now tries to make the Web faster.
This talk was part of the American Math Society eastern sectional conference hosted at Bowdoin this year.