Drinking Party Puzzle

Starting with 2 bottles, a rat can choose to drink from either the first or the second bottle. If it drinks from the first bottle and dies, then that one is poisoned. If it drinks from the first bottle and lives, then the other one is poisoned.

Anything above 2 bottles will require additional rats. The greatest amount of bottles tested with 2 rats is 4 bottles. Let

• rat #1 tests bottles #1,2
• rat #2 tests bottles #1,3

then

• bottle #1 is poisoned if rats #1,2 die
• bottle #2 is poisoned if rat #1 dies
• bottle #3 is poisoned if rat #2 dies
• bottle #4 is poisoned if NO rats die

For three rats, I found the maximum number of bottles tested to be 8. Let

• rat #1 tests bottles #1,2,3,4
• rat #2 tests bottles #1,3,5,7 
• rat #3 tests bottles #1,2,5,6

so that all rats share one bottle (#1), all rats don't drink from one bottle (#8), all rats drink from one bottle which no other rat has drank from (#4,6,7), and two rats share the same bottle (#2,3,5). This covers all the bottles. Then

• bottle #1 is poisoned if rats #1,2,3 die
• bottle #2 is poisoned if only rats #1,3 die
• bottle #3 is poisoned if only rats #1,2 die
• bottle #4 is poisoned if only rat #1 dies
• bottle #5 is poisoned if only rats #2,3 die
• bottle #6 is poisoned if only rat #3 dies
• bottle #7 is poisoned if only rat #2 dies
• bottle #8 is poisoned if NO rats die

A pattern is starting to emerge. I notice that rat #1 just needs to consume half of the bottles, #1-n/2. Rat #2 needs to drink from every other bottle. Rat #3 needs to drink from every 2 bottles. With 1 rat, it can test 2^1 = 2 bottles. With 2 rats, they can test 2^2 = 4 bottles. With 3 rats, they can test 2^3 = 8 bottles. Therefore, I claim that with 10 rats, they can test 2^10 = 1024 bottles, sufficient for the 1000 bottles of the problem. Continuing from above, rat #4 would drink every 3 bottles, rat #5 from every 4 bottles, etc.

*This works fine for 10 rats, but breaks down for 9 rats.

After thinking more about this, I can show that the number of bottles follows 2^n, where n is the number of rats. Let R = {the set of rats}. Then the power set of R, P(R), lists each bottle and which rats drank out of them. For example, for n = 3, we have R = {1,2,3}, and so

P(R) = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

From this, we see that each subset matches up exactly with the hand-written solution above. We can then use a theorem that states: "a set containing n distinct objects has 2^n subsets". Therefore, the power set of a set containing n distinct objects has 2^n elements. And so for 10 rats, n = 10, and the set of bottles has 2^n = 2^10 = 1024 elements, which means that 1024 bottles can be tested.