1000 Batches, 1 Poisoned, 4 Mice, Minimized Costs

Question

You work at a pill factory that recently produced $1000$ batches, each with ample samples. Your boss has just discovered that exactly one batch is entirely poisoned, and just one pill from it will cause a person or mouse to die at midnight, regardless of when they eat it. Your boss gives you 24 hours and a budget for animal tests to identify the poisoned batch.

The store offers four types of mice: a small mouse, costing $\\\$1$, can consume $50$ pills; a medium mouse, costing $\\\$1.5$, can consume $100$ pills; a large mouse, costing $\\\$2$, can consume $200$ pills; a mouse king, costing $\\\$3$, can consume $1000$ pills, but there’s only one.

Questions:

1. What’s the minimum cost to identify the poisoned batch?
2. If the mouse king is unavailable, but each medium mouse can consume $125$ pills, what’s the minimum cost to identify the poisoned batch?
3. You visit the store and find that all types of mice except for the small ones are sold out. Looks like your budget for testing 1000 batches isn’t enough, so you aim for $500$ batches instead, what’s the minimum cost to identify the poisoned batch?
4. You call the boss about the situation that only small mice are left, and he gives you more budget but insists on testing all $1000$ batches, what’s the minimum cost to identify the poisoned batch?

_{source: DawnStarRiver, from the Variety Detective}

Answer 1

1. What’s the minimum cost to identify the poisoned batch?

\$38

In each of the following steps, if a mouse dies, the poisoned batch must be one of the batches that mouse ate. If no mice die, then the poisoned batch must be in the set of batches that were untested on that step. All of these tests are to be run simultaneously. The steps are ordered just to illustrate how the 1000 are narrowed down to 1.

* Use a mouse king to test batches 1-500. This splits the 1000 into 2 sets of 500.
* Use a 4 large mice. Each large mouse tests 100 from each of the 2 sets from the previous step. This splits the 2 sets of 500 into 10 sets of 100.
* Use 9 medium mice. Each of these tests 10 batches from each the 10 sets from the last step. This splits the 10 sets of 100 into 100 sets of 10.
* Use 9 medium mice. Each of these tests 1 batch from each of the 100 sets from the last step. This splits the 100 sets of 10 into 1000 sets of 1.

Final cost: 1 mouse king (3) + 4 large mice (x2 = 8) + 18 medium mice (x1.5 = 27) = \$38

2. If the mouse king is unavailable, but each medium mouse can consume 125 pills, what’s the minimum cost to identify the poisoned batch?

\$34.50

* Use 7 medium mice. Each mouse tests 125 batches from the 1000. This splits the set of 1000 into 8 sets of 125.
* Use 4 large mice. Each mouse test 25 batches from each of the 8 sets. This splits the 8 sets of 125 into 40 sets of 25.
* Use 4 large mice. Each mouse tests 5 batches from each of the 40 sets. This splits the 40 sets of 25 into 200 sets of 5.
* Use 4 large mice. Each mouse tests 1 batch from each of the 200 sets. This splits the 200 sets of 5 into 1000 sets of 1.

Final cost: 7 medium mice (x1.5 = 10.5) + 12 large mice (x2 = 24) = \$34.50

3. You visit the store and find that all types of mice except for the small ones are sold out. Looks like your budget for testing 1000 batches isn’t enough, so you aim for 500 batches instead, what’s the minimum cost to identify the poisoned batch?

\$26

* Use 9 small mice. Each mouse tests 50 batches from the 500 batches. This splits the 500 into 10 sets of 50.
* Use 9 small mice. Each mouse test 5 batches from each of the 10 sets. This splits the 10 sets of 50 into 100 sets of 5.
* Use 8 small mice. The first 4 mice test 1 batch from each of the first 50 sets. The second 4 mice test 1 batch from each of the second 50 sets.

Total cost: 26 small mice = \$26

4. You call the boss about the situation that only small mice are left, and he gives you more budget but insists on testing all 1000 batches, what’s the minimum cost to identify the poisoned batch?

\$53

* Use 19 small mice. Each mouse tests 50 batches from the 1000 batches. This splits the 1000 into 20 sets of 50.
* Use 18 small mice. The first 9 test 5 batches in each of the first 10 sets. The second 9 test 5 batches in each of the second 10 sets. This splits the 20 sets of 50 into 200 sets of 5.
* Use 16 small mice. Each set of 4 mice tests 1 batch in the (first/second/third/fourth) set of 50 sets. This splits the 200 sets of 5 into 1000 sets of 1.

Total cost: 53 small mice = \$53

Answer 2

Broadly, bigger is better - we're going to be getting (n-1) rats to eat an nth of the pills, and so we'd rather be spending \$8 to divide by 5 (or \$16 to divide by 25) than \$19 to divide by 20.

1. What’s the minimum cost to identify the poisoned batch?

\$35.

First, use the mouse king to divide our pills into two 500s. (\$3)
Then, use four large mice (each eating an equal amount from each group) to get ten 100s. (\$11)
Use four large mice again to get fifty 20s. (\$19)
Use four large mice again to get two hundred and fifty 4s. (\$27)
Finally, use four large mice. The can't be evenly divided over every group this time, but we only need them to sample three pills from each group, which they can manage with their capacity of 800. This gives us a unique dead-rat subset for each pill, so we're done with a total spend of \$35.

2. If the mouse king is unavailable, but each medium mouse can consume 125 pills, what’s the minimum cost to identify the poisoned batch?

\$34.50.

Use four large mice to get five 200s. (\$8)
Use four large mice to get twenty-five 40s. (\$16)
Use four large mice to get one hundred and twenty-five 8s. (\$24)
Use seven medium mice to get a unique result, for a total of \$34.50.

3. You visit the store and find that all types of mice except for the small ones are sold out. Looks like your budget for testing 1000 batches isn’t enough, so you aim for 500 batches instead, what’s the minimum cost to identify the poisoned batch?

\$26

Use nine small mice to get ten 50s. (\$9)
Use nine small mice to get one hundred 5s. (\$18)
Use eight small mice to get a unique result, for a total of \$26.

4. You call the boss about the situation that only small mice are left, and he gives you more budget but insists on testing all 1000 batches, what’s the minimum cost to identify the poisoned batch?

\$50.

Use 19 small mice to get twenty 50s. (\$19)
Use 19 small mice to get two hundred 2s and two hundred 3s. (\$38)
Use 12 small mice to get a unique result, for a total of \$50.

Finally, I offer a lateral solution to Q1 (extendable to the rest):

I buy 4 large mice, 4 small mice and the king (\$15). I use the king and the large mice to divide our pills into ten 100s.
Then I take my mice and my pills and I cycle towards the nearest other time zone. If this is to the east, I want to enter it; otherwise I stay by the border.
At midnight, one of my large mice may die, along with the king. This narrows me down to a group of 100 pills, which I use my remaining 7 mice to binary search (100 < 2^7). I then take my mice west into a different time zone.
At midnight, one hour after the previous window and thus within my 24-hour deadline, more mice die and I have a solution.

Answer 3

Simplified Problem

I'm going to start with a slightly modified version of question 3, and then use the answer to that problem to answer the original questions.

The first problem to solve is:

You visit the store and find that all types of mice except for the small ones are sold out. Looks like your budget for testing 1000 batches isn’t enough, so you aim for 100 batches instead, what’s the minimum cost to identify the poisoned batch?

What’s the minimum cost to identify the poisoned batch?

We can solve this smaller problem with just a few mice, using the following method.

Number the batches 0 to 99
Mouse 1 tests batches with odd numbers (1,3,5,9)
Mouse 2 tests batches with numbers that become odd when divided by 2, rounding down (2-3, 6-7)
Mouse 3 tests batches with numbers that become odd when divided by 4, rounding down (4-7, 12-15)
Mouse 4 tests batches with numbers that become odd when divided by 8, rounding down (8-15,24-31)
Mouse 5 tests batches with numbers that become odd when divided by 16, rounding down (16-31,48-63)
Mouse 6 tests batches with numbers that become odd when divided by 32, rounding down (32-63,96-99)
Mouse 7 tests batches 64-99
This uses a total of 7 mice.

After midnight, we can then find which batch is poisoned by

Arranging the mice in descending order and interpreting the lineup as a binary number, where dead mice are 1 and live mice are 0. So if mice 3, 4, and 7 died, we read the number as 1001100 or 76, which is the only batch tested by exactly those three mice.

Problem 1

Moving on to the real question now.

What’s the minimum cost to identify the poisoned batch?

The final answer total will be

$45.50

We use the method described above, with two small modifications.

We run the method above three times, with larger mice.
Batches 0-400 can be tested by 9 large mice.
Batches 401-800 can be tested by another 9 large mice. Batches 801-999 can be tested by 8 medium mice.

We can reduce the cost further by

Replacing the first mouse from each group with a mouse king, which will test all odd-numbered batches from all three groups.

This gives a final cost of

16 large mice, 7 medium mice, and one mouse king, which cost $45.50

But wait!

If the 0'th batch in one of the three groups is poisoned (batch 0, batch 400, or batch 800), none of the mice will die, and then we won't know which group contains the poison batch. Similarly, if the first batch in one group is poisoned, only the mouse king will die, who is shared between all groups. We can solve this by having the last mice from each group eat the first two pills from each of the other two groups. Then, if mice from more than one group die, we know that the group where all mice survived contains the poison.
The medium mouse group's last mouse only has room for 3 more pills, and we need them to eat 4, so for that group, we'll also need to have the second-to-last mouse eat one extra pill.

Problem 2

If the mouse king is unavailable, but each medium mouse can consume 125 pills, what’s the minimum cost to identify the poisoned batch?

We use the method above to get this with a budget of

$48.00

The details:

We divide the batches into 4 groups of 250, each of which can be tested by 8 medium mice. 32 medium mice costs $48.00

Once again, we need to account for the 0's case.

Each group's last mouse also tests the groups immediately before and after it.

Problem 3

You visit the store and find that all types of mice except for the small ones are sold out. Looks like your budget for testing 1000 batches isn’t enough, so you aim for 500 batches instead, what’s the minimum cost to identify the poisoned batch?

The final cost will be

$35.00

Once again, we start with the same strategy, plus divide and conquer.

We could the batches into 5 groups of 100, each of which takes 7 small mice to test, spending $35.00 in total.

We can do very slightly better, using a trick we learned from the mouse king in problem 1.

The last mouse in each group tests only 35 batches, which totals to 175 batches to test. Instead of buying a separate mouse for each group, we can buy only 4 mice to test the lot, allowing this to be done with only 34 small mice in total.

There are a few edge cases left to account for

The zero'th batches of each group are all indistinguishable from one-another, and the 64th batch of each group is tested by only the final group of mice. Since there are 3 high-mice testing 5 groups, this necessarily means that there will be 2 pairs of groups whose 64th is tested by the same mouse. We will group these 7 batches together into one special group, and take the second-to-last mouse from each of the first three groups and have them test this special group, requiring them each to eat a maximum of 4 additional pills, (which they can - they only ate 36 pills each previously). We only need 3 mice to test 7 pills, because numbers 0-6 can be represented with only 3 binary digits. The second-to-last mouse of the final two groups will test the entire special group. If both of these mice die, we know to read the special group instead of the regular groups.

Problem 4

You call the boss about the situation that only small mice are left, and he gives you more budget but insists on testing all 1000 batches, what’s the minimum cost to identify the poisoned batch?

We can solve this exactly like problem 3, except the numbers work out a little more nicely. The total comes out to

$67.00

Start with a divide-and-conquer strategy

Split the batches into 10 groups of 100 batches each. Each group takes 7 mice to test, which would take 70 mice.

Once again, we can save money by fully utilizing each mouse.

There are 350 high pills (35 pills per group, times 10 groups) so we can remove one mouse from each group and replace them with 7 mice, for a total of 67 small mice in the end.

And once again, the edge cases.

This time, there are 10 zero'th batches, plus 3 more 64th batches which are pigeonholed out from being uniquely identified by the last rat group. We create a special group of 13 pills. Once again, we form a special group to test this. This time, the special group needs 4 mice to test it (since we need 4 bits to represent the number 13), and the mice testing it will need to consume up to 8 pills. The 6th mouse from each group can still handle this, since they have room for 14 more pills each.
We still need two signaling mice to indicate that the special group is active, who need to each eat 13 pills. Luckily, we still have 6 more mice with room, so we can choose any two of them to form the signal.

We should applaud our boss's insight in choosing to spend an extra $33 on tests instead of risking a 50% chance of throwing out 500 whole batches of medicine (or killing a patient).

Answer 4

For 1, my minimum (with to solutions) is

32$

King, 14 large, 1 small = 32$

First we make 500 pairs.

We feed the king rat 1 pill of each pair.
We feed 1 pair to each rat (2 * 15 pills tested), then 1 pair to each pair of rats (2 * 105 pills), then 1 pair to each triplet of large rats (2 * 364 pills).

pills
2 * 1 no mouse
2 * 15 one mouse (1/mouse)
2 * 105 two mice (14/mouse)
2 * 364 three large mice (78/mouse)
2 * 485 total
This leaves 2*15 pills to test

2 *10 small+2large
2 *5 four large mice

Total (e.g. - Depending how the last 15 are distributed, since there is room to choose there)
1 small fed 2 *25
10 large fed 2 *97
3 large fed 2 *93

Alternative solution, same strategy:

King, 13 large, 3 small = 32$

pills
2 *1 no mouse
2 *16 one mouse (1/mouse)
2 *120 two mice (15/mouse)
2 *286 three large mice (66/mouse)
2 *27 small+ 2 large
2 *50 four large

3 small fed 2 *25
6 large fed 2 * 100
7 large fed 2 * 99

Answer 5

Doing the math only for the case with the smallest mouse available (as the others are quite analog):

The naive case is

to arrange all pills in one line, and let each one be eaten by a mouse. In this 1-dimensional line, we require 1000 mice.

We could

arrange the pills in a 32x32 grid (leaving some slots empty), and place 32+32 mice on the borders of that grid. This brings us down to 64 mice in the 2nd dimension.

Arranging the pills in 3 dimensions, we would need a 10x10x10 grid and 10+10+10 mice. However, in that case each mouse would need to eat 100 pills.

We can generalize the number of required mice as

g·d with g=gridsize and d=dimension. The numer of pills per mouse is 1000 divided by the d-th root of 1000.

The number of mice required is reduced with every

additional dimension, but the number of pills rises with every dimension. Giver that 3 dimensions already maxed us out, the perfect solution is 2 dimensions, i.e. 64 mice.

That all assumes

balanced grids. But splitting the 1000 pills into multiple grids (e.g. batches of 100 pills being tested by 10+10 mice) massivly increases the total number.

Unless I miss something clever (which is most likely the case), I come to a minimum of

64 mice