Another poisoned bottle question!

Question

There are $1000$ bottles of wine, of which $n\leq10$ are poisoned at random. (You don't know the exact number) A person consuming the poison dies on the midnight of that day.

You have $2$ prisoners who you are willing to sacrifice, and only one day to test the wine. However, the number of days is not pre-determined, so imagine it as a counter. Every day that passes decrements it by 1. On a given day, for every prisoner who dies, the counter decrements by another 1 and you lose a day. For every prisoner left alive, you have a choice:

• either you can ask for an extra day, and increment the counter by 1 (no net gain/loss in time)
• or for an extra prisoner.

It is not compulsory for a prisoner to drink on a a given day. You must stop if your days left are $\leq0$

The main objective is a guaranteed strategy to identify the poisoned bottle(s) What is the optimal strategy if you want to minimize:

(a) Total number of days (not the counter's value)
(b) Total number of deaths

Answer 1

You can do it in 9 days (if I have understood the rules correctly):

Day 1: You have 1 day and 2 prisoner. Ask for 1 day and 1 prisoner.
Day 2: You have 1 day and 3 prisoners. Ask for 1 day and 2 prisoners.
Day 3: You have 1 day and 5 prisoners. Ask for 1 day and 4 prisoners.
Day 4: You have 1 day and 9 prisoners. Ask for 1 day and 8 prisoners.
Day 5: You have 1 day and 17 prisoners. Ask for 1 day and 16 prisoners.
Day 6: You have 1 day and 33 prisoners. Ask for 11 days and 22 prisoners.
Day 7: You have 11 days and 55 prisoners. Ask for 11 day and 44 prisoners. Let 50 prisoners each drinks from 20 bottles. At most 10 of them will die, and you'll know the poisoned bottles are in the 200 bottles they have drank from.
Day 8: You have 11 day and 89 prisoners. Ask for 11 days and 78 prisoners. Let 50 prisoners each drinks from 4 bottles. At most 10 of them will die, and you'll know the poisoned bottles are in the 40 bottles they have drank from.
Day 9: You have 11 day and 157 prisoners. Let 40 prisoners each drinks from a bottle. 10 of them will die, and what they have drank from are the poisoned bottles.

To minimize deaths, just ask for enough days and prisoners in whatever ways, and let each prisoner drink from one bottle.

Answer 2

First of all, this puzzle has no explicit objective (It doesn't aks you to find which bottle is poisoned!), so...

Just don't make them drink at all.

If the objective is to minimize the numbers of days and the numbers of deaths, and drinking the wine is not mandatory, just doing nothing give you one day total and zero deaths. No other strategy can get you lower than that, since you already start at 1, and any day-decrementing strategy kills a prisoner.

Other than that, if you need to find which wine bottles are poisoned, you can do something like this (step by step):

-- On the first, day, ask for an extra day and an extra prisoner.

Days Remaining: 1 Prisoners: 3

On the second day, ask for 2 extra prisoners and an extra day.

Days Remaining: 1 Prisoners: 5

On the third day, ask for 4 extra prisoners and an extra day.

Days Remaining: 1 Prisoners: 9

On the fourth day, ask for 8 extra prisoners, and an extra day.

Days Remaining: 1 Prisoners: 17

On the fifth day, ask for 16 extra prisoners, and an extra day.

Days Remaining: 1 Prisoners: 33

On the sixth day, ask for 32 extra prisoners, and an extra day.

Days Remaining: 1 Prisoners: 65

On the 7th day, ask for 64 extra prisoners, and an extra day.

Days Remaining: 1 Prisoners: 129

On the 8th day, ask for 128 extra prisoners, and an extra day.

Days Remaining: 1 Prisoners: 257

On the 9th day, ask for 256 extra prisoners, and an extra day.

Days Remaining: 1 Prisoners: 513

On the 10th day, ask for 487 extra prisoners, and an extra day.

*Days Remaining: 1 Prisoners: 1000 *

Make all of them drink from one bottle. At midnight of the 11th day, you have between 990 and 1000 prisoners, up to 10 deaths, and 12 days used.

Answer 3

Guaranteed strategy:

11 days.
10 days to round up enough prisoners, the 11th day to test it all (see explanation of the opposite)
prisoners lost will always be N

O wait N < 10. it thought it could be 10 or more, never the less my answer is still right, the explanation might be difficult to understand.

A strategy for (a) is as follows:

you have 1/2 the prisoners drink form the wine, if you are lucky the last 10 bottles will be poisonous and it will take you 10 days

let me explain:

1 prisoner drinks, but does not die, means you have 2 prisoners, for each prisoner you ask a new one so now you have 4 prisoners. then you have 2 prisoners drink, none dies so you have 4 prisoners after midnight, then you ask 4 more resulting in 8. This is exponential which makes it easy. (you will have 1024 prisoners in day 10. Now to continue, the first day you have 1 bottle tested, the second day you have 2 bottles tested (you will have a total of 3 bottles tested then 1 first day + 2 2nd day) then the third day you will test 4 bottles (add that to the 3 tested you have 7 bottles tested after the 3th day). the pattern here is you will have tested 1 bottle less than you have prisoners.

Now for the opposite:

if you have 999 bottles poisoned you will do the same but the first person will die, there will always be 1 person that dies and 1 person that lives, so you can only ask for 1 person each day. meaning you'll need 999 days to find out all but 1 bottles are poisoned. you will also lose 999 prisoners. now this takes way to long so instead, as we have seen you can wait 10 days, asking for new prisoners every day, so after 10 days you will have enough prisoners and you can test all the bottles at once, so on the 11th day you will have lost 999 prisoners but it will have only cost 11 days.

As for losing the least prisoners, you will always lose at least N prisoners.

Answer 4

I'm going to make a assumptions here:

• You start at 1 day, even if you do not test, you would be at 0 days the next day. If you are not allowed to add extra days because you still have 2 prisoners left, you would instantly lose. Therefore, I assume you are allowed to add extra days even when you are at 0 days, as long as you have prioners left alive.
• Similar, when you go negative, I still assume you can add extra days as long as you have enough prisoners to do so.

I will use the following strategy:

• If my counter is at 0 or negative, I will use enough prisoners to get it back to 1.
• Any other prisoner left alive is used to get more prisoners.
• I will let the following number of prisoners drink from a new bottle of wine:
  1. Let N be maximal number of toxic bottles. This is 10 - nr of dead prioners.
  2. If I have more than 2xN-1 prisoners, all of them will drink wine from a new bottle.
  3. If I do not have enough prisoners for step 2, only half minus 1 is allowed to drink.
• If all 1000 bottles are tested, or if 10 prisoners have died, I'm done.

Best case this will take me 6 days, if 10 prisoners die on day 5+6.
Usually this will take me 10 days, if the first 495 bottles are safe, I will have all 1000 bottles tested on day 10.
Even with 2 of the 257 bottles tested on day 9 toxic, this will only take 10 days.
In most other cases, I will need 11 days. As long as the first 44 bottles are safe (drunk in the first 6 days), 9 prisoners can die on day 7, and I will still finish testing all bottles by day 11.
Worse case, the first 9 bottles I test are toxic. My run will now extend up to 16 days. This is however, very unlikely.

This solution should have the lowest average number of days. Max dead prisoners it equal to the number of toxic bottles. If, however, you want the minimal worse case, simply wait till day 11 until you have over 1000 prisoners, and let them all test one bottle at that time.

---

Example run:
Day 1: 2 prisoners, 0 drink, 0 die, get 1 new.
Day 2: 3 prisoners, 0 drink, 0 die, get 2 new.
Day 3: 5 prisoners, 1 drink, 0 die, get 4 new.
Day 4: 9 prisoners, 3 drink, 0 die, get 8 new.
Day 5: 17 prisoners, 7 drink, 0 die, get 16 new.
Day 6: 33 prisoners, 33 drink, 0 die, get 32 new.
Day 7: 65 prisoners, 65 drink, 0 die, get 64 new.
Day 8: 129 prisoners, 129 drink, 0 die, get 128 new.
Day 9: 257 prisoners, 257 drink, 0 die, get 256 new.
Day 10: 513 prisoners, 505/513 drink, 0-10 die, done.

---

Some on day 9 die:
Day 9: 257 prisoners, 257 drink, 2 die, get 252 new.
Day 10: 507 prisoners, 505/507 drink, 0-8 die, done.

---

More likely scenario: some die on day 5:
Day 5: 17 prisoners, 7 drink, 2 die, get 12 new.
Day 6: 27 prisoners, 27 drink, 7 die, get 12 new.
Day 7: 32 prisoners, 32 drink, 0 die, get 31 new.
Day 8: 63 prisoners, 63 drink, 0 die, get 62 new.
Day 9: 125 prisoners, 125 drink, 0 die, get 124 new.
Day 10: 249 prisoners, 249 drink, 0 die, get 248 new.
Day 11: 497 prisoners, 493/497 drink, 0-1 die, done.

Still only 11 days!

Worse case:
Day 1: 2 prisoners, 0 drink, 0 die, get 1 new.
Day 2: 3 prisoners, 0 drink, 0 die, get 2 new.
Day 3: 5 prisoners, 1 drink, 1 die, get 2 new.
Day 4: 6 prisoners, 2 drink, 2 die, get 1 new.
Day 5: 5 prisoners, 1 drink, 1 die, get 2 new.
Day 6: 6 prisoners, 2 drink, 2 die, get 1 new.
Day 7: 5 prisoners, 1 drink, 1 die, get 2 new.
Day 8: 6 prisoners, 6 drink, 2 die, get 1 new.
Day 9: 5 prisoners, 5 drink, 0 die, get 4 new.
Day 10: 9 prisoners, 9 drink, 0 die, get 8 new.
Day 11: 17 prisoners, 17 drink, 0 die, get 16 new.
Day 12: 33 prisoners, 33 drink, 0 die, get 32 new.
Day 13: 65 prisoners, 65 drink, 0 die, get 64 new.
Day 14: 129 prisoners, 129 drink, 0 die, get 128 new.
Day 15: 257 prisoners, 257 drink, 0 die, get 256 new.
Day 16: 513 prisoners, 472/513 drink, 0-1 die, done.

Not only is the worse case extremely unlikely, it also takes N=9 or N=10.

See/play with numbers here.