Finding the Poison Bottle: 1023 Bottles, 10 Sacrifices

[ssj5harsh]

I've mentioned this before, but that thread was moved to homework, so I'll put it here again:
There are 1023 bottles. One out of them is a poison bottle. You have ten persons who can be sacrificed for the purpose. Find the poison bottle in a systematical way.

Hint:Use the unique property of the number 1024.

 

[NateTG]

I've mentioned this before, but that thread was moved to homework, so I'll put it here again:
There are 1023 bottles. One out of them is a poison bottle. You have ten persons who can be sacrificed for the purpose. Find the poison bottle in a systematical way.

Um..
This is *really* easy. You draw lots. The person who looses takes a sip from each of the bottles except for one, one by one, to see whether it's poison. Give the other nine shovels to dig a grave.

 

[TenaliRaman]

Um..
This is *really* easy. You draw lots. The person who looses takes a sip from each of the bottles except for one, one by one, to see whether it's poison. Give the other nine shovels to dig a grave.

LOL!
Since the original question was so **easily** solved! Let me make it a bit harder.

"The person dies of the poison can be seen after a month only. So we don't have immediate results. However we would like to know which is the poison bottle immediately after a month. So we don't have much time. Can we devise a suitable strategy now?"

Ofcourse this one probabily is solved in this forum before :uhh:

-- AI

 

[NateTG]

Why not make it fun, and put a bottle of antidote in as well - so anyone who drinks the poison and the antidote survives.

Now, assuming a one month activation time, the challenge is to identify the poison and the antidote as quickly as possible, using 10 people.

 

[Jimmy Snyder]

You probably need 10 months.

 

[NateTG]

I'm fairily sure it can be done in 8 months or less.

 

[20questions]

Hint:Use the unique property of the number 1024.

number the bottles 0-1023 in binary numbers (10 digits), each bottle number with first digit a "1" is drunk by person 1, second digit a "1"? then person 2 drinks some, etc. etc. If say, the 1st 4th and 9th die then then bottle was 1001000010 (decimal 578)

 

[NateTG]

...

Can you do the harder version?

 

[quark]

Excellent solution by 20questions. I wouldn't have got it for a whole life time.

 

[ssj5harsh]

I got it

Right, 20questions gave the answer I expected. Well Done!
About the harder question: (in white)
The no. 1023 is 1111 1111 11 in base 2.
If we proceed as in the first part, we take only the first digit and two people. If the poison and the antidote have the same first digit, no one will die. If they have different digits, the one who gets the poison will die.

-Case 1: One dies: We have now narrowed down the range. The poison is obviously in the other digit. So, we can proceed as in the first part to find the answer with 9 people and 9 digits. Done. Took two months.

-Case 2: No one dies: We can't narrow it down now. We just proceed with the next digit and so on. At least one digit will be different. When we find the different digit, one person will have died. We now eliminate half of the numbers. Antidote is eliminated. 9 digits and 9 persons. Proceed as in first part. It can take a varying amount of time. Minimum is 3 months, maximum is 11 months.

This is what I believe Jimmy was referring to. Well, we can shorten the time further by using the ten persons for 5 digits simultaneously. So, maximum time is four months.

With this method, we can find the antidote as well. I'll just leave it to you guys as an exercise.

 

[ssj5harsh]

Other way

Here's another way. (for the poison only):
We shouldn't limit ourselves to binary system.
1023 in base 3 is 1101 220. That means a max. of 4 months, using 3 persons per digit.
1023 in base 4 is 3333 3. That means a max. of 4 months, using 4 persons per digit.
1023 in base 5 is 1304 3. That means a max. of 4 months, using 5 persons per digit.
1023 in base 6 is 4423. That means a max. of 5 months, using 6 persons per digit.
1023 in base 7 is 2661. That means a max. of 4 months, using 7 persons per digit(except the first which needs 3 persons).
1023 in base 8 is 1777. That means a max. of 4 months, using 8 persons per digit(except the first one which needs 2 persons).
1023 in base 9 is 1356. That means a max. of 5 months, using 2 persons for first digit, 9 persons for 2nd, 3rd and 4th digit.
1023 in base 10 is 1023. That means a max. of 5 months, using 10 persons per digit (except the first).

I hope everyone gets the point and I really got a lot more out of the puzzle than I expected.(Thanks to NateTG)

 

[Jimmy Snyder]

This is what I believe Jimmy was referring to.

No, I was just not thinking about the problem correctly. I figured for 1 guy to drink from half the bottles and then wait a month to see if he died. Then continue on in a binary search for 9 more months. This solution takes 10 times as long as the solution given by 20questions. Before 20questions posted the correct solution, I had already come up with a different solution requiring 4 months, but there is no point in proposing it now.

 

[ssj5harsh]

Originally posted by jimmysnyder
Before 20questions posted the correct solution, I had already come up with a different solution requiring 4 months, but there is no point in proposing it now.

Well, Jimmy you should write your solution down at least to give us a new way of thinking about the problem. I've already proved sufficiently that the minimum maximum is 4 months. Post it please.

 

[Jimmy Snyder]

I've already proved sufficiently that the minimum maximum is 4 months.

20question's solution only requires one month.

 

[ssj5harsh]

20question's solution only requires one month.

Well, it does but it doesn't account for the antidote. If the antidote is included, the solution points to the wrong bottle. In order to correct it, I introduced the elimination method.

I also said that the minimum maximum is 4 months. This means, if you are really unlucky and are not able to eliminate any bottles till the last step, you will take 4 months. You can of course be stupid and take more time, but you don't need to. This is the maximum time that my algorithm needs.
You can of course be really lucky as in case 1(see reply#10) and find the poison in 2 months.
By the way, if you haven't got it yet, I left finding the antidote as an exercise. In fact, you have to be lucky(or take an more time and people) to find the antidote.
Hence, the time period has to be between 2 and 4 months.

 

[everneo]

I got at the most 3 dead in 4 months. May be someone can find more optimum way of finding out the poison with less casualities in less time.



1st month :

10 groups of bottles; 1 person for each group; 102 bottle in each group; (10 * 102 = 1020) ;
3 bottles reserved.

2nd month :

case 1: No one died; then 3 persons for the remaining 3 bottles .
case 2: 1 died. 102 bottle from his group divided into 9 groups ;
11 bottle in each group. 9 X 11 = 99;
3 bottles reserved.



3rd month :

case 1.1 : 1 of the 3 died ; the bottle is fixed. in 2 months with 1 dead.

case 2.1 : No one died; 3 persons for the remaining 3 bottles.
case 2.2 : 1 died. 11 bottles from his group for 8 persons, one each. 8 X 1 = 8;
3 bottles reserved.


4th month :

case 2.1.1 : 1 of the 3 died; the bottle is fixed.. in 3 months with 2 dead.

Case 2.2.1 : No one died; 3 persons for the remaining 3 bottles.
case 2.2.2 : 1 died. the bottle is fixed. in 3 months with 3 dead.


5th month :

case 2.2.1.1 : 1 died. the bottle is fixed. in 4 months with 3 dead.

 

[ssj5harsh]

Good work, everneo.
But you must realize that the solution obviously was very rigorous and took you a lot of time. If, now, I give you the number 262,143, you will need even more cases and subcases and sub-sub-cases to find an algorithm. So, such a solution would be frowned down upon.
But, a knowledgeable person will tell you that 262,143 is 777 777 in octal system.
So, the algorithm is set. Take 8 people and give them bottles beginning with one digit each. Again take 2 cases(see reply#10). Do this and you will find the poison bottle with 14 people in 7 months.

Your effort really is worthy of praise, but it cannot extend to significantly more people.
As for your question, I don't think anyone will be able to find an optimal solution which is generalisable(By the way, when I was introduced to this problem, I found that I could find the poison bottle with 8 people in 4 months, by your method)

 

[rachmaninoff]

I don't know what's going on, are you people approaching the POISON ONLY problem or the POISON + ANTIDOTE problem? Everneo and ssj5harsh: I'm assuming your methods are dealing with the POISON ONLY problem?

edit: everneo, your method as I've read it is in general is THE optimal one, if you're seeking to minimalize casualties. 20answer's is the optimal solution for minimizing time.

edit2: mea culpa, an improvment on everneo's method is for a single person to go through bottle by bottle... hence solving the question with exactly one fatality.

 

[rachmaninoff]

I solved it! The antidote version of the problem! It can be done in two months! I'm writing my proof now, it'll be up in some minutes.

 

[ssj5harsh]

I don't know what's going on, are you people approaching the POISON ONLY problem or the POISON + ANTIDOTE problem? Everneo and ssj5harsh: I'm assuming your methods are dealing with the POISON ONLY problem?

Everneo's solution is for the POISON only. It has lowest and definite casualties. The best solution for the poison problem is 20questions' method.
For the POISON + ANTIDOTE problem, I (obviously) agree with my solution. But I have yet to see Jimmy's solution. I'd like to see your solution as well.

The two problems are separate problems.

 

[rachmaninoff]

What is your solution for the antidote problem? Just curious, mine works in two months tops.

 

[rachmaninoff]

You mentioned you 'proved' the minimum maximum amount of time for the antidote problem was 4 months? What's your proof?

 

[ssj5harsh]

My solution is the same that I have written in reply#10. You'd have to extend a bit further to accommodate the antidote. The time taken would vary as per the case. In the worst case mentioned before, you know which digits are same so, you just need one month more. In the best case, you have the poison and 9 persons. Work with the other digits(using the poison to isolate the antidote). Well, I've realized that this might not work in all cases(people may be less in some cases), but I think It works in most cases. That's why I want to see other solutions.

Besides, you should realize that the poison + antidote problem wasn't set by me. It was set by NateTG. I just set the first problem(POISON ONLY). So I'm sure only about that particular solution. What I can assure you is that my method will find the poison in 4 months max., but it will not necessarily find the ANTIDOTE, with limited no. of people.

 

[ssj5harsh]

The proof was a rigorous proof(see #11). I was talking wrt my algorithm only . It applies to my algorithm at least, i.e We can take any number system and get the answer in max. of 4 months. For number systems above 10, it becomes clear that the number of months would be more than 4. Hence I say that the minimum maximum is 4 months. What I mean is that you do not need more than 4 months to find the poison. It can take 2,3 or 4 months depending on the position of the bottles, but not more than 4.

I'm sorry if I was not clear in explaining my algorithm.

 

[rachmaninoff]

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

 

[20questions]

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)

 

[NateTG]

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.)

 

[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.

 

[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.

$$a, p \in B= \{ 0,1,2,3 \} , a \neq p$$

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
$$p \in X \bigcap Y = \{ 0,1 \} \bigcap \{ 0,2,3 \} = \{ 0 \} \Rightarrow p=0$$
but

$$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)$$
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:
$$\mbox{X dies} \Longleftrightarrow \left( p \in X \right) \wedge \left( a \in \overline{X} \right)$$

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

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 $$p \in \{ 0, 1 \} \subseteq Y' \Longrightarrow a \in Y'$$. Combining results from the two months,
$$a \in \{ 2,3 \} \bigcap \{ 0, 1, 2 \} = \{ 2 \}$$. (Antidote is bottle #2).
Subcase 2: Y' does not die. Then by similar logic,
$$a \in \{ 2,3 \} \bigcap \overline{ \{ 0,1,2 \} } = \{ 3 \}$$. (Antidote is bottle #3).

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

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

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

Subcase2: at least X' does not die.
eq. 3 $$\left( p \notin \{ 1,2,3 \} \right) \vee \left( a \notin \overline{ \{ 1,2,3 \} } = \{ 0 \} \right)$$
Sub-sub-case 2a: Y' dies.
$$( p \in \{ 0,1,2 \} ) \wedge ( a \in \overline{ \{ 0,1,2 \} } = \{ 3 \} )$$ (Antidote is in bottle #3.)
Sub-sub-case 2a: Y' lives.
eq. 4 $$( p \notin \{ 0,1,2 \} ) \vee ( a \notin \overline{ \{ 0,1,2 \} } = \{ 3 \} )$$
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,
$$a = 1 \Rightarrow - \left( a \notin {1} \right) \Rightarrow p \notin \{ 0,2,3 \} \Rightarrow p=1=a$$
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!

 

[NateTG]

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.

 

[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.

 

[NateTG]

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 $2^{21}$ possible test results for $2^{20}-2^{10}$ possible situations.)

 

[gnpatterson]

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

 

[NateTG]

Yeah. I was thinking of the problem in the wrong way.

 

[gnpatterson]

I can't 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 can't 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 doesn't 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 let's me get the information

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