A poisonous party.

Algebra Level 3

A businessman decides to hold a party at his villa. His guests gift him with bottles of wine . By the end of the party, he has 1000 bottles of wine . However, he is informed that one of these bottles has poison. The businessman decides to test those bottles by making mice drink samples from each bottle . One mouse can drink one or more samples. The poison affects the mice the next morning. How many minimum mice are required to carry out this test within one day?

The answer is 10.

1 solution

Richard Desper
Nov 18, 2019

Let the bottles be numbered from 1 to 1000 in binary. Since 1000 < 1024, we only need 10 digits to do this.

Let the mice be numbered from 0 to 9, and let each mouse i sample every bottle that has a '1' in its binary expansion in the ith position.

The next morning, a subset of the mice will have been poisoned. Translate the powers of two represented by the mice and add them up. This is the binary code of the poisonous wine.

For example, if mice 1, 4, and 7 are poisoned, then the index of the poisonous wine is 2^7 + 2^4 + 2^1 = 128 + 16 + 2 = 146.

This shows that $10$ mice are enough. You also need to show that $9$ mice are not enough.

If you use $9$ mice, then each of the nine can either die or not. This means that there are $2^9 = 512$ possible outcomes of an experiment using $9$ mice and $512$ possible responses is not enough to distinguish $1000$ cases.

Mark Hennings - 1 year, 6 months ago

Good point. I forgot to show that 10 mice are necessary. It's just that, from an information theory standpoint, it's obvious. (Presuming the mice only have binary outcomes.)

Richard Desper - 1 year, 6 months ago

This was an excellent attempt. There are numerous ways to solve this problem and I personally find the binary one the best

Mehul Arora - 1 year, 6 months ago

A poisonous party.

The answer is 10.

1 solution

1 pending report

Vote up reports you agree with