All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Logic
Mathematician Versus Detective (Posted on 2003-11-05) Difficulty: 3 of 5
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?

  Submitted by Ravi Raja    
Rating: 3.4444 (9 votes)
Solution: (Hide)
If the goal is to minimize the maximum number of tests then that maximum for n glasses is log2n (log to the base 2 of n), rounded up.

If the number of glasses is a power of 2 (32, 64, 128, 256, etc.) then the correct procedure on the first step would be to test exactly half the glasses. Then test half of the glasses in the positive half next. Keep repeating this procedure. Each step will narrow down the field of poisoned glasses by a factor of 2.

If the number number of glasses is not a power of 2 then there are lots of ways you can test them and still achieve the same maximum number of tests. One way would be to find the closest power of 2 less than n, set this many glasses aside, and then test the others. The only n for which this remainder is 1, between 100 and 200, is 129. In the case of 129 the first test would likely be negative. Then proceed with the procedure for testing 128. Between the first test and the log2128 the maximum number of tests is 8.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Puzzle AnswerK Sengupta2022-03-14 01:08:29
QuestionHmmm...Stephen Ticsay2005-03-14 21:30:08
No Subjectdon2003-11-20 19:44:30
binary search doesnt workdon2003-11-20 19:38:29
hardr2003-11-20 10:29:46
SolutionMark Longhurst2003-11-12 03:47:14
Hints/Tipsre: SolutionJack McBarn2003-11-11 09:08:06
Some ThoughtsHardJack McBarn2003-11-11 09:07:25
Re No CommentDrBob2003-11-07 15:58:13
No SubjectDrBob2003-11-07 15:47:06
re(5): Waste a testSilverKnight2003-11-07 09:00:16
re(4): Waste a testSaso2003-11-07 03:37:59
re(3): Waste a testSilverKnight2003-11-06 12:33:59
Questionre(2): Waste a testSaso2003-11-06 12:07:00
re: Waste a testSilverKnight2003-11-05 17:11:44
QuestionWaste a testGamer2003-11-05 16:48:03
SolutionI will drink to this solutionDan2003-11-05 12:50:45
Some ThoughtsWhat REALLY happened.Popstar Dave2003-11-05 09:55:09
Solutionretiarius2003-11-05 09:53:28
darn you SKLee2003-11-05 09:47:22
Some Thoughtsfirst thoughtsSilverKnight2003-11-05 09:40:44
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (11)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information