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?
(In reply to
re(4): Waste a test by Saso)
Saso, I agree with your last statement! In BOTH of your cases (method A and method B), the maximum possible is 8 tests.
The point of the problem, though, is ... given that we know that exactly one glass is poisoned, the MAXIMUM for 128 glasses is seven tests (assuming you use the appropriate algorithm).
As soon as I have more than 128 glasses (and no more than 256), then the maximum becomes eight tests.
But if, as the problem suggests, a detective FIRST selects a single glass at random, then we are diverging from the optimal method.
The point here is that it doesn't change the maximum if we have only 129 glasses, because if we don't find the poison in the first glass, then we can continue with 7 tests to find it (maintaining 8 total checks).
If we have 130 glasses, and we don't find the poison in the first glass, it is possible (even if improbable) that the next 7 tests will only bring us to TWO candidates, and a ninth test will be required to find the suspect glass.
____________________
I also do not wish to argue, but, as I hope you'll agree, it is important that language be used precisely, particularly in problem statements (such as on Flooble).
Nevertheless, misunderstandings and ambiguities occur, and you can find several problems on this site where it ended up causing multiple possible solutions (varied from the intended singular solution).
--- SK
re(5): Waste a test
