The antidote can be found in no more than TWO months.
Okay, so I was working on a set-theory proof, but it occurred to me I can explain things much more easily:
Consider a set of N people, 2^N bottles, exactly one of which has poison and one (different bottle) has the antidote.
Organize the bottles in base 2: (x1, x2, ... , xn).
In the first month, the ith person drinks precisely those 2^N bottles where the ith digit is 0:
(x1,x2...,0,...,xn).
Just like 20answer's proof for the poison problem. So far.
Two cases.
Case 1: At least one person, say the jth person, dies after a month.
Then the set of all bottles with jth digit equal to zero contains the poison, AND this same set does not contain the antidote.
Furthermore (this is subtle): Since the antidote exists, and is not in this set, it must be in the complement of this set, which is precisely the set of bottles with jth digit equal to 1!
Formally: If {j1,...,jk} are those people who did die, then the binary representation of the poisoned bottle has all jk's equal to 0, and the antidote's representation has those digits equal to 1.
Consider the set of all people who did not die; i.e., the complement of the set of dead people. (Special case: if this set is empty - if everyone died - then the poison must have been in the bottle corresponding to (0,0...0) all zeroes, and the antidote at (1,1...1) , and we're done! Because if mth digit of poison is 1, mth person did not drink it and lived; likewise, if antidote's mth digit was 0, then the mth person drank the antidote and lived).
The digits these people represented are precisely those digits of the antidote's location which we do not know (see above). Let each kth person drink all bottles in the intersection of the sets of all the bottles the dead people drank; the poison is obviously in this set, and the antidote obviously isn't. Then, let each kth person drink all bottles with their kth digit equal to 0 (again!). This will uniquely determine the remaining digits of the antidote's location: if kth person dies, kth digit is 1, else it is 0.
Case 2: No one dies in the first month.
Then the either the poison must be in (1,1,1...1) or the antidote in (0,0,0...0). If neither of these were true - kth digit of poison were 0, and mth digit of antidote were 1 - then mth person would drink poison, but not antidote because mth person only drinks bottles with 0 in mth digit.
Then we progress exactly as in month 1, with two changes: every person additionally drinks bottle (1,1,1...1). If no one dies, that means (0,0,0...0), the only other bottle drank in common by everyone, was in fact the antidote; otherwise, (1,1,1...1) was in fact poison (see above), and thus the digits of the antidote are uniquely determined, by those who do not die.
Squid erat demonstratum.
This result allows us to find the antidote in a set of 2^k bottles, with only k people, in no more than 2 months.
An example:
5 people, 2^5=32 bottles. 5-digit binary representations: (x1,x2,x3,x4,x5). Poison is in (1,1,0,1,0), antidote in (1,0,0,1,1).
month 1: Person #1 drinks 16 bottles, namely all (0,x2,x3,x4,x5).
Person #1 does not drink from the poisoned bottle, nor the antidote.
Persons 3 and 5 drink poison; person 5 drinks antidote, person 3 doesn't. The only person to die is person 5.
Month 2: Everyone drinks all bottles of the form (x1,x2,x3,x4,0), including (1,1,0,1,0) the poison, but not including (1,0,0,1,1) the antidote.
Person 1 then drinks all (0,x2,x3,x4,x5), which does not include the antidote. Persons 2 and 3 drink the antidote; 1 and 4 die. Thus the antidote must have 0's in digits 2 and 3; and 1's in digits 1,4, and 5.
(1,0,0,1,1).
Only two months!
edit: emphasis
