My friend Qin told me this puzzle, but her version involves using 10 condemned prisoners to test the wines. I took the liberty of softening the story a little bit by replacing the 10 condemned prisoners with 10 samples of testing agent. The solution to this puzzles stays the same.
A result-dependent solution can be: first divide the 1000 bottles into two groups of 500 each and then test the sample from one group, the result of this testing tells us which group was contaminated and has to be tested again. Next divide this group of 500 bottles into two groups of 250 bottles each and test one group... and so on. Eventually the contaminated bottle will be singled out.
Here is a more elegant solution which uses the binary system.
Tuesday, September 1, 2009
1000 Bottles of Wine
The King has 1000 bottles of wine one of which was contaminated with a deadly poison. A chemist offered a small vial of agent that can detect traces of the poison, but it can be used for only 10 samples.
How can the King find the contaminated bottle?
How can the King find the contaminated bottle?
Subscribe to:
Posts (Atom)
