## The Rats of The Dungeon

Regardless of whether you like math or not (though if you’re reading this blog, I’m quite sure you’re interested), I’m sure you’ll enjoy this intricately woven riddle.  I found this gem online while simply browsing the depths of the internet, and had realized that I had to share it.

It is 7pm. A jubilant king has just defeated the enemy kingdom, and wants to throw a lavish banquet at 8pm with his subjects to celebrate. He has a large stash of 1000 bottles of wine for this feast, but knows that exactly one of the wine bottles has been poisoned by one the other kingdom’s spies. There are rats in the dungeon which will die within an hour if given the poison, and the king frantically needs to find out which bottle is poisoned before the feast, which is in one hour.

How many rats are needed to find out which bottle has been poisoned? Remember that since there is one hour, there is no possibility of waiting for rats to see if they die and then accordingly proceed. Therefore all the rats need to be fed at the same time, and the results need to determine the poisoned bottle. Also take into account the fact that one rat can be fed the wine of many wine bottles at once.

This puzzle is an extremely interesting one, and I have outlined the solution below the picture, but I wouldn’t suggest you look at it until you have given the problem a full day of thought.

One fundamental procedure to solve such problems is always to start out simply, and then to work upwards from there. For the purposes of this problem I will be using the integer n to represent the nth wine bottle. So what would we do in the case of 2 wine bottles? Only one rat would be needed, as we would simply feed it 1, and if it dies, we know 1 is poisoned, and else 2 is.

Now let’s move onto 4 wine bottles. A logical set of wines for a rat would be 1 and 2 by the same logic. We want at the end for the outcomes to distinguish which one bottle is poisoned, and with the least number of rats, so the next rat could be fed 2 and 3. Now based on which rats die we will know the poisoned wine bottle. Remember that First and Second for the rats has no meaning as we have to feed all the rats at once, and is just for understanding:

Wine Bottles: 1, 2, 3, 4

First Rat: 1 and 2

Second Rat: 2 and 3

Only First Rat Dies: 1 is poisoned

Only Second Rat Dies: 3 is poisoned

Both Rats Die: 2 is poisoned

No Rats Die: 4 is poisoned

This makes sense, right? The next step will be to try 8 bottles. Again, let’s feed the first rat the first four: 1, 2, 3, 4, and feed another rat 3, 4, 5, 6. From just these two rats, we will be able to narrow it down to two wine bottles. But we need a way to know which one of the two it is. So let’s feed another rat the wine of one of the two wine bottles in each pair: 1, 3, 5, 7. This will tell us which of the two wine bottles it is. Here is a breakdown of what happened:

Wine Bottles: 1, 2, 3, 4, 5, 6, 7, 8

First Rat: 1, 2, 3, 4

Second Rat: 3, 4, 5, 6

Third Rat: 1, 3, 5, 7

Only First Rat Dies: 2 is poisoned

Only Second Rat Dies: 6 is poisoned

Only Third Rat Dies: 7 is poisoned

First and Second Rats Die: 4 is poisoned

Second and Third Rats Die: 5 is poisoned

First and Third Rats Die: 1 is poisoned

All Rats Die: 3 is poisoned

No Rats Die: 8 is poisoned

I think you’re probably starting to get the idea. Now think about what would happen for 16 wine bottles. One rat with the first 8 and one with the middle 8, first of all. From these we would know which 4 it lies in. Another rat would take the first 2 from each of the sets of 4, so we would know which pair of two within the four it lies in. And another rat would be fed the wine of one in each pair of two, so we would know which one it is. It would be like this:

First Rat: 1, 2, 3, 4, 5, 6, 7, 8

Second Rat: 5, 6, 7, 8, 9, 10, 11, 12

Third Rat: 1, 2, 5, 6, 9, 10, 13, 14

Fourth Rat: 1, 3, 5, 7, 9, 11, 13, 15

I don’t think I need to write all the permutations for this one. If you are starting to see the pattern in this, you will realize that for a set of 2n wine bottles, n rats are needed. Since 1000 > 29, we will need at least 10 rats to find out which dreaded bottle contains the contaminated fermented grape juice. When I first saw this problem, I wouldn’t have thought that there would have been only 10 rats needed.

The unique aspect of this problem is that it is not sequential, as in it does not have you check if a rat dies, and then try another rat, and so on. In its essence you are trying to find a set of sets of particular numbers in which each number appears as a unique set of rats. A very well-known formula in set theory is that if you have k objects in a set, there are 2k possible unique subsets. This idea is inherently connected to the problem, and makes it all the more intriguing to explore further in terms of various mathematical ideas including combinatorics as well.  This problem is also a binary one, where each rat is uniquely identified by a binary number represented by the rats that die.

To end, I would like to thank the valiant rats which gave up their lives. Now we can drink our wine in peace…