The Emperor's Second Celebration

We answered 20 but we happened to device a testing method that can locate both the poisoned glasses out of 1000 using only 12 prisoners

First, we arranged the 1000 glasses in a 10x10x10 cube. Each glass will have a unique set of 3D coordinates. Instead of placing 10 prisoners per axis, we decided to take combinations from 4 prisoners to cover all 10 positions per axis (since 3 prisoners can only cover at most 7 coordinates). Therefore, based on which set of prisoners die or get sick, we can locate the poisoned glasses from their coordinates.

We still haven't found the flaw in either this testing method or the theoretical solution posted.

(solution created with Alen Balbuena)

For every single prisoner, it seems like we can get maybe two bits of information: whether the non-lethal glass is in a subgroup, and whether the lethal glass is in a subgroup.

However, I will prove to you that each prisoner will supply at most one bit of information using induction.

Let the lethal glass be $L$ and the non-lethal glass be $N$ .

The base case: the first prisoner chooses a set $\mathbb{S}_1$ of glasses. Worst case scenario, $L\in \mathbb{S}_1$ , so he might die without showing symptoms and it will give us one bit of information.

Now consider the intersections $S_n=\bigcap_{L\in \mathbb{S}_i}^{n}\mathbb{S}_i$ If $\mathbb{S}_{n+1}\cap S_n = \emptyset$ then we know that $L\not\in \mathbb{S}_{n+1}$ so we can get at most one bit of information about whether $N$ is or is not in $\mathbb{S}_{n+1}$ .

If $\mathbb{S}_{n+1}\cap S_n \ne \emptyset$ then there is a possibility that $L\in \mathbb{S}_{n+1}$ so we get only one bit of information, whether prisoner $n+1$ will or will not die.

Thus, we get at most one bit of information per prisoner. The number of ways to arrange a lethal glass and a non-lethal glass in $1000$ glasses is $1000*999=999000$ and since $\lceil\log_{2}{999000}\rceil = 20$ we need at least $20$ bits of information to determine the glasses. Thus the answer is $\boxed{20}$ prisoners.

Let's do some mind experiment.

As you are probably familiar, you need 10 prisoners to find only the lethal-poisoned glass. To solve this using a binary system, you can feed the first prisoner glass number 1, second prisoner glass number 2, first and second prisoner glass number 3, and so on.

The mental stretch comes here. Imagine making 1000 groups of 999 glass. First group has all but glass number 1, second group has all but glass number 2, etc.

Out of those 1000 groups, there will be exactly one group of 999 glasses that has non-lethal poison but does not have lethal poison. From that group, you can find the non-lethal poisoned glass. 999 to check for, so you need 10 prisoners account all possibilities using the same tactic you use for the simpler version of the question. Now the second part is finding which group of 999 glasses was the one that contained the non-lethal glass but not the lethal glass. There are 1000 of such groups. Since we need to find 1 of 999 out of 1000, we need to count for 999000 possibilities. Closest power of 2 that is greater than 999000 is 2^20, which is approximately 1 million.

Therefore, we need 20 prisoners.

Label the glasses in binary numbers. To determine the lethal poison, ask the first prisoner to try all glasses with first number 1, second prisoner to try all glasses with second number 1, etc. Then you can determine which one is deadly by which prisoners are dead. Nine won’t work, since you can only form 2^9=512 combinations but ten can form 2^10=1024 combinations. Also, you need to locate the non-lethal poison and there is no way to test both the deadly one and the non-lethal one at the same time. Therefore you need another 10 prisoners, total 10+10=20 prisoners.