Finding the Poison Bottle: 1023 Bottles, 10 Sacrifices

[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