The police commissioner hired a mathematician to help at a crime scene. At the scene were between 100 and 200 glasses of wine. Exactly one glass was poisoned. The police lab could test any sampling for poison. A group of glasses could be tested simultaneously by mixing a sample from each glass. The police commissioner desired only to minimize the maximum possible tests required to determine which exact glass was poisoned.

The mathematician started by asking a detective to select a single glass at random for testing. "Wouldn't that waste a test?", the detective asked. "No, besides I'm in a gambling mood.", the mathematician replied. How many glasses were there?

There were 129 glasses.

The logical way to proceed in a case like this is a binary test, and that will be minimized if the number of glasses is a power of 2: progressively dividing the glasses into 2 groups and testing one of the groups. The only power of 2 between 100 and 200 is 128. So there must have been 129 glasses, so that testing one glass at random would leave 128 glasses - a power of 2, which would minimize the tests.

Posted by Dan on 2003-11-05 12:50:45