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?

Unfortunately, the binary search technique would not work in this case. A binary search can ONLY be used when the data set has been sorted first. If you do not sort the data first, then you have no way of knowing whether or not the item you are looking for is in one subset or the other. Since the poison can be in any glass, then the data isn't sorted, it is random.

Posted by don on 2003-11-20 19:38:29