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 must have been 129 glasses.
Removing 1 (the random test at the start) leaves 128, which divides by 2 all the way down to 1. Therefore half the sample can be tested (starting with 64) and, if no poison is found that half can be discarded. If poison IS found in that half, the other half are discarded. Then you test half the remaining glasses, again discarding the half with no poison. keep halving the sample until you are down to the last 2, then test 1.
Solution
