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?

Although I agree that that makes sense, there's only a 2/129 chance of wasting a test if that is true. If you do it "the normal method" by a binary test and count the 2 glasses as 1 until you get to the end, there's only a 2/129 chance those two cups are it. Therefore, there's a ((127*7)+(2*8))/129 or an average of about 7.0155 tests needed.

When you do it the other way, you have a 1/129 chance of 1 test, and a 128/129 chance of 8 tests. That's ((1*1)+(128*8))/129 or about a 7.9457 chance.

Doing it both ways uses up at most 8 tests, but on the average, the "normal way" saves a test over 93 percent of the time.
Edited on November 5, 2003, 4:52 pm

Posted by Gamer on 2003-11-05 16:48:03