Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Here's an interesting question.

There are $1000$ mice and $1000$ bottles (numbered $1,2,3....1000$).

One of the bottles is poisoned. You can mix the solution with the other bottles any number of times. Even a fraction of poison can kill a mouse. Whats the minimum number of mice required to check which bottle is poisoned?

There's a proof which involves grouping (which I'm aware of). I want a better mathematical proof.

share|improve this question
    
A binary search like method would work. –  Ishan Banerjee Mar 10 '13 at 10:51
    
Are you sure that only one bottle is poisoned? This seems like an awfully easy problem if so, as Hagen von Eitzen's solution shows. –  Alexander Gruber Mar 10 '13 at 11:03
    
Yeah! Only one bottle is poisoned. I wanna know whether binary search(As the answer says) is the only tackle to this? If yeah, I wanna know why? –  Inceptio Mar 10 '13 at 11:25
1  
Just drink from the bottles yourself. What's life without danger? –  Asaf Karagila Mar 10 '13 at 12:12
    
Remember that the does makes the poison, so the assumption that the poison can be diluted indefinitely without influencing the accuracy of the experiment is almost certainly not warranted. –  Henning Makholm Mar 10 '13 at 12:14
show 2 more comments

1 Answer 1

One. In test $n$ give the mouse a bit to drink from bottle $n$ and check if it survives (until it dies and you thus have found the poisoned bottle).

If you need to do parallel testing, the answer is: ten. Nine mice can give you only $2^9=512$ different "answers" by their respective dieing and surviving, which is not enough for a test that must be able to give $1000$ different answers. With ten mice, you can mix drinks by giving a bit (pun not intended) from bottle $n$ to mouse $i$, $0\le i\le 9$, if the coefficient $a_i$ in the binary expansion $n=\sum_{i=0}^9 a_i2^i$ is nonzero. Then the "bit pattern" of dead mice is exactly that of the poisened bottle number.

If you want to be more human (or rodan?), you can try to avoid bit patterns with many $1$s. As $1000=2^{10}-24$, you can drop the one pattern with ten $1$s, the ten patterns with nine $1$s and thirteen of the $45$ patterns with eight $1$s. Then again, using $1000$ mice with one drink for each would only kill one mouse instead of about five ...

share|improve this answer
    
Ah! This is the proof that I'm aware of. –  Inceptio Mar 10 '13 at 11:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.