Finding the number of poisoned bottles

Question

This is a well-known problem (discussed here and here), but I am adding a twist to it.
A king has 100 bottles of wine and poisons $K$ of them, where $0 leq K leq 100$. You have a supply of rats and need to determine how many of the bottles are poisoned. You are not interested in finding the actual poisoned bottles and you only want to find the value of $K$. You can get a rat to drink a mix of wine taken from different bottles. If the mix contains any poisoned wine then the rat will die after 1 hour. What is the minimum number of rats required to conclusively identify the value of $K$ in the general case (not any specific $K$)?
I only know the obvious solution that uses 100 rats, so I am very interested in seeing if better solutions exist! Note I am leaving this puzzle open to either adaptive (rats can be reused, but longer wait time) or non-adaptive (rats cannot be reused, but just 1 hour wait time) strategies. I am interested in both types of solutions.
P.S. No rats were harmed in the making of this puzzle :)

Anthony Ingram-Westover · Answer

I'm pretty sure the minimum is

If we consider the worst case scenario:

Iuri Guilherme · Answer

If I...

...then...

...unless...

Dapianoman · Answer

Iuri Guilherme · Answer

If I...

That would be a very inefficient solution to the problem, unless...

So it's kind of a...

musefan · Answer

What is the minimum number of rats required to conclusively identify the value of K?

The answer is 1 rat.
It just might happen to not always be the maximum number required.

bob · Answer

Looking at the benefit of mixing...

My gut feeling is

gnasher729 · Answer

Testing several bottles together instead of letting a rat drink from the first, second etc bottle until it dies or survives all the bottles never gains more information, so it is pointless.
Now to find the number of bottles: Assume the king who never lies tells you that he picked one bottle, poisoned the other 99, and then either poisoned the last bottle or not. So you know the answer is 99 or 100.
Mixing two or more bottles is pointless, because you know the rat is going to do, no information gained at all. So you can only give each rat in turn a bottle to drink, until one survives or all 100 rats are dead. If the king poisoned all the bottles or you and the rats are unlucky and the unpoisoined bottle is the last one, all 100 rats die.

Finding the number of poisoned bottles

7 Answers

Add your own answers!

Ask a Question