Poison bottles

  • Thread starter ssj5harsh
  • Start date
  • #26
rachmaninoff,

Case 1 is clever I didn't think of poisoning everyone to come up with the antidote! I'm not following case 2 yet though, if no one died all I can see is the poison was not (0,0,0,...0) but it still could be any other bottle. Any 0 digits in the number of the poison can just also correspond to 0's in the antidote's number- as long as there's at least one non 0 digit somewhere in the poison's number (so the antidote corresponding digit can be a 1, making the antidote a number different than the number of the poison)
 
  • #27
NateTG
Science Advisor
Homework Helper
2,450
6
It's probably possible in 2 months, but not by that method.

Let's take a crack at a simple case, and see what happens:

Let's say we have 4 bottles and 2 people - so there are a total of 12 possible situations. Let's lable the bottles 0,1,2,3. Then according to Rachmaninoffs method, one will drink from 0, 1 and 1, and the other from 0, and 2.

After the first month, both people survive. So (AFAICT) according to Rachmaninoff, in the second month, the testers drink from 0,1, and 3 and 0,2 and 3 respectively, and once again, everyone survives (in fact this is guaranteed to occur).

At this point, there are still 5 possibilities - the poision is in 3, and the antidote is in 0,1, or 2, and the antidote is in 0, and the poision is in 1, or 2. (The case where the antidote is in 0, and the poison is in 3 is an overlap.)
 
Last edited:
  • #28
rachmaninoff
NateTG - the two-person case is easy, the hard part is extending the method for arbitrary n persons. I haven't gone back over my method since I posted it (it's too much work), so I'm not even sure if there's a flaw... I'll get around to it.
 
  • #29
rachmaninoff
Explicit algorithm to solve the "simple" two-person case:
(warning: this is a non-elegant proof)

There are four bottles, B={0,1,2,3}; there is one antidote and one poison, and they are not in the same bottle.

[tex]a, p \in B= \{ 0,1,2,3 \} , a \neq p [/tex]

There are two persons. Let
person X drink the bottles in {0,1}, and
person Y drink the bottles in {0,2,3}.

Four cases.

Case I: Both X and Y die. Then
[tex]p \in X \bigcap Y = \{ 0,1 \} \bigcap \{ 0,2,3 \} = \{ 0 \} \Rightarrow p=0[/tex]
but

[tex]a \in \overline{X \bigcap Y} = \{ 1,2,3 \} \subseteq X \bigcup Y \Longrightarrow \left( a \in X \right) \vee \left( a \in Y \right) [/tex]
Which contradicts the assumption that both X and Y die (one drank the antidote). Thus Case I is impossible.

I can formalize the idea of dying:
[tex]\mbox{X dies} \Longleftrightarrow \left( p \in X \right) \wedge \left( a \in \overline{X} \right) [/tex]

Case II: X dies.
Then, formally,
[tex] ( p \in \{ 0,1 \} ) \wedge ( a \in \overline{ \{ 0,1 \} } = \{ 2, 3 \} ) [/tex]

Then person Y can determine whether 2 or 3 contains the antidote, by drinking {0,1,2} in the second month.
Subcase 1: Y' dies. We know [tex]p \in \{ 0, 1 \} \subseteq Y' \Longrightarrow a \in Y' [/tex]. Combining results from the two months,
[tex]a \in \{ 2,3 \} \bigcap \{ 0, 1, 2 \} = \{ 2 \} [/tex]. (Antidote is bottle #2).
Subcase 2: Y' does not die. Then by similar logic,
[tex]a \in \{ 2,3 \} \bigcap \overline{ \{ 0,1,2 \} } = \{ 3 \} [/tex]. (Antidote is bottle #3).

Case III: Y dies.
[tex] ( p \in \{ 0,2,3 \} ) \wedge ( a \in \overline{ \{ 0,2,3 \} } = \{ 1 \} ) [/tex] (Antidote is bottle #1).

Case IV: Neither dies.
eq 1. [tex] ( p \notin \{ 0,1 \} ) \vee ( a \notin \overline{ \{ 0,1 \} } = \{ 2,3 \} ) [/tex]
eq 2. [tex] ( p \notin \{ 0,2,3 \} ) \vee ( a \notin \overline{ \{ 0,2,3 \} } = \{ 1 \} ) [/tex]

In the second month, let X' drink {1,2,3}, and Y' drink {0,1,2}.
Subcase 1: at least X' dies.
[tex] \left( p \in \{ 1,2,3 \} \right) \wedge \left( a \in \overline{ \{ 1,2,3 \} } = \{ 0 \} \right) [/tex]
Thus the Antidote is in bottle #0.

Subcase2: at least X' does not die.
eq. 3 [tex] \left( p \notin \{ 1,2,3 \} \right) \vee \left( a \notin \overline{ \{ 1,2,3 \} } = \{ 0 \} \right) [/tex]
Sub-sub-case 2a: Y' dies.
[tex] ( p \in \{ 0,1,2 \} ) \wedge ( a \in \overline{ \{ 0,1,2 \} } = \{ 3 \} ) [/tex] (Antidote is in bottle #3.)
Sub-sub-case 2a: Y' lives.
eq. 4 [tex] ( p \notin \{ 0,1,2 \} ) \vee ( a \notin \overline{ \{ 0,1,2 \} } = \{ 3 \} ) [/tex]
Then combining the above with eq. 1, 2, 3, we get a=2. (Antidote is in bottle #2).*

*Proof: Assume for contradiction that a = 1.
Then by eq. 2,
[tex]a = 1 \Rightarrow - \left( a \notin {1} \right) \Rightarrow p \notin \{ 0,2,3 \} \Rightarrow p=1=a [/tex]
A contradiction of our assumption that the poison and antidote are different.
Thus a != 1.

An identical argument, assuming a=0 and eq. 3, shows that a!=0.
Yet the same argument, assuming a=3 and using eq. 4, shows that a!=3.
Therefore a = 2.


This one actually works!!!
 
Last edited by a moderator:
  • #30
NateTG
Science Advisor
Homework Helper
2,450
6
Part of the issue is that you're only finding the antidote, and not both the antidote and the poison. Finding either just the poison, or just the antidote in 2 months is not particularly difficult.

It's impossible to identify both the poison and the antidote from 4 bottles in 2 months with 2 people.
 
  • #31
rachmaninoff
Part of the issue is that you're only finding the antidote, and not both the antidote and the poison. Finding either just the poison, or just the antidote in 2 months is not particularly difficult.

It's impossible to identify both the poison and the antidote from 4 bottles in 2 months with 2 people.
I thought the problem was just to find the antidote. You're right that finding both in two month is impossible, and it's easily proved to be so.
 
  • #32
NateTG
Science Advisor
Homework Helper
2,450
6
rachmaninoff said:
I thought the problem was just to find the antidote. You're right that finding both in two month is impossible, and it's easily proved to be so.
OK:
How about 11 instead of 10 people for 1024 bottles. Is it possible to find both the poison and the antidote in 2 months then? (11 people in two months gives a total of [itex]2^{21}[/itex] possible test results for [itex]2^{20}-2^{10}[/itex] possible situations.)
 
  • #33
could I have some clarification please

to my way of thinking if you have 1024 bottles
you have 1024 * 1023 possible combinations of poison and antidote
= approx 10^20

while if you ten people testing in

1 month you have 2^10 possible outcomes
2 months you have 3^10 possible outcomes
3 months you have 4^10 possible outcomes

my reasoning is that a person can
a)die in first month or live
b)die in the first month or the second or live

NB a person can't die in the first test and then give information in the second

unless you are allowing me to recruit more testers to fill a maximum number of positions.

in the one month case and the 1023 bottles the number of people required is 20

for two months it is thus requires 13 people

and for three months it requires 10 people

in each case this is only possible if the optimal strategy is used

the form of the optimal strategy can be optained recursively from the results of successively lower numbers of bottles on the principal that if you have people left alive you must have exactly the right amount of uncertainy left

eg if you kill 12 out of 13 people you must be able to narrow it down to two bottles one of which is the posion and the other is the anti dote
 
  • #34
NateTG
Science Advisor
Homework Helper
2,450
6
Yeah. I was thinking of the problem in the wrong way.
 
  • #35
I cant figure out what the optimal pattern is for even 3 or bottles and 3 or four people in the one month senario.

If I have 1 person i can get two bottles in one month

but with 1 person and any number of months it is impossible to do more than 2 bottles

with 2 people and one month you cant even do 3 bottles anyway with the amount of information you have

with 3 people even though the amount of potential information is enough no configuration exists to get the result for 3 bottles in one month

it seems that the antidote kills off a large amount of information

the recursive method I had thought to use doesnt seem to work in a straight-forward manner

my thinking had been that if you had any number of people and they all died in the first month that would dictate the pattern to be one in which one bottle should be drunk by all people and one bottle should be left undrunk by all. this would give an clue to the total pattern and all you had to do has work your way in. however i now see that the antidote has the potential to kill off all the information by being the one that they all drink from thus identifying it but totally concealiing the poison.

so my new strategy is to look for some other form of totally othrogonal sets that lets me get the information

I note that 1023 = 33*31 and 31 is prime
 

Related Threads on Poison bottles

  • Last Post
Replies
9
Views
9K
  • Last Post
Replies
15
Views
2K
  • Last Post
2
Replies
29
Views
4K
  • Last Post
Replies
23
Views
6K
  • Last Post
2
Replies
39
Views
6K
  • Last Post
2
Replies
45
Views
6K
Replies
13
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
6K
Replies
4
Views
728
Top