A horrible disease has broken out in the Kingdom of Faroffia. There is a wonder cure, and you have a 1000 bottles of it which must be distributed today to save the kingdom. Unfortunately, you have just found out that one of the bottles is contaminated with a deadly poison. You have a supply of laboratory mice which can be used to test for the poison, but because it takes some time to have its effect, you only have time to conduct one test.

How many mice do you need in order to find out which is the poisoned bottle?


Solution: 10 mice.

Method:

  1. Number the bottles from 1 to 1000 and the mice from 1 to 10.
  2. Convert the bottle numbers into binary. The bottles are numbered 0000000001, 0000000010, 0000000011, …, 1111101000.
  3. For the first bottle, if the first digit of the bottle number is a 1 feed it to mouse number 1.
  4. Repeat for each digit of the first bottle number up to digit 10 and mouse 10 (only mouse 10 will get the first bottle).
  5. Repeat for each bottle up to bottle number 1000 (mice 1,2,3,4,5 and 7 will get the last bottle).
  6. Wait until the poison has worked and all mice are alive or dead.
  7. Find the bottle where the numbers of the 1 digits in its binary number match the numbers of the dead mice. This is equivalent to using the dead mice as a binary number and converting back to a decimal bottle number (so if mice 1 and 10 die, the binary number is 1000000001 and the poison is in bottle number 513).

Laborious, but very economical of mice.

Variation: How can you minimise the number of mice that must die, and what is that number?

Answer: 8. Simply avoid using numbers that have more than 8 digits in them (such as 511, which is 0111111111) when numbering bottles.