-3

So I came up with a variation of the famous problem https://www.reddit.com/r/math/comments/3o0mfi/a_king_1000_bottles_of_wine_10_prisoners_and_a/

There are n bottles, with each bottle independently having a probability p_poison that it is poisoned, and for every instance of a test subject drinking from a poisoned bottle there is a probability kill_chance that the poison takes effect after 24 hours.

The winning algorithm is the one that uses the least amount of test subjects (on average) to have a 75% or better chance to find at least one poisoned bottle (if any) in the 24 hour window.

Unless otherwise stated, all the rules and constraints from the original problem (as stated in the reddit link above) apply.

(Edited for clarity)

genealogyxie
  • 107
  • 1
  • The original problem is also here. – f'' Jun 13 '16 at 14:09
  • For clarification, do you just need to find one poisoned bottle even if there are more than one, or do you need to find all of them? – f'' Jun 13 '16 at 14:09
  • (I've edited the tags, enigmatic-puzzle is for puzzle where you don't know the goal of the puzzle. Feel free to edit back if I have made a mistake) – Fabich Jun 13 '16 at 14:14
  • If we're averaging, we need a probability distribution on the number of poisoned bottles. Should we assume that all configurations that don't have too many poisoned bottles are equally probable? – Gareth McCaughan Jun 13 '16 at 14:21
  • I'd hope the goal is to find all the poisoned bottles, given that the actual goal would be to be able to drink some wine without getting poisoned... – Gareth McCaughan Jun 13 '16 at 14:22
  • @f'' You only have to find one. Finding more than one is great, but not necessary – genealogyxie Jun 13 '16 at 21:58
  • 2
    What exactly does "let's assume a standard bell curve" mean here? (I dont actually see anything here that can be distributed that way -- it's a continuously varying thing that can go out to plus or minus infinity.) Perhaps what you actually want is something like this: there's a certain probability p (which might be, say, 5%) and then each bottle is independently poisoned or not with probability p of being poisoned. – Gareth McCaughan Jun 13 '16 at 23:00
  • @GarethMcCaughan Thanks for the tip. I guess I didn't really think this problem through haha – genealogyxie Jun 14 '16 at 06:33
  • Looking better now – Jonathan Allan Jun 14 '16 at 09:30

4 Answers4

1

As you are only asking to find at least one bottle of poisoned wine, and given that there are no time constraints, it can be shown that the minimum number of test subjects needed is

one test subject.

I make the reasonable assumptions that:

  • only a drop of wine is needed for testing.
  • the poison is sufficiently fast-acting that the fatal effects will be seen after only a short wait, rather than manifesting over a number of weeks in cases such as polonium poisoning.

The testing sequence would follow:

1.Feed your test subject a sample of wine.

2.Wait a short time.
- If test subject dies, you have found your bottle of poisoned wine.
- If test subject lives, wine is ok, and repeat from Step 1.

3.If test subject is showing signs of intoxication, let them rest quietly in the corner/their cell for a period before repeating from Step 1.

long
  • 1,319
  • 10
  • 14
0

To identify one poisoned bottle, you will need 10 bits of information. Let each subject be one of those bits. Number the bottles $0,\dots,999$ and get 10 subjects, and number them with powers of $2$: $1,2,4,\dots,512$. Prepare for each subject $b$ a mixture from each bottle $a$ where $a\; \&\; b=b$, where $\&$ is bitwise "and". The sum of the numbers of the subjects who keel over from the poison identifies the bottle.

Rosie F
  • 8,621
  • 2
  • 18
  • 50
0

Given that we are attempting to find a single poisoned bottle if one exists (and no information about which bottles are not poisoned) I can only assume that
...we wish to poison somebody!
In this case we may achieve our aim with

$0$ test subjects

Because

since even a trace of the poison will kill, we may pour all but $\frac1n$ out from one bottle and add $\frac1n$ from each of the other $n-1$ bottles into it, to give us a bottle that is poisoned if any were.

Jonathan Allan
  • 21,150
  • 2
  • 58
  • 109
  • The original problem states that you need to find out which bottle was poisoned, not just that a poisoned bottle exists. – genealogyxie Jun 13 '16 at 22:52
  • Yep, but your problem stated (until the edit) that you wanted to find a single poisoned bottle if one exists; this answers that problem. Also, I feel like the problem in it's current state needs a better description. Is it that n delegates have arrived, each with a bottle of wine, and on average some number are poisoned drawn from a normal distribution (with what variance?) and that our tests also have a false negative chance? Which data do we know? – Jonathan Allan Jun 13 '16 at 23:03
0

Since you don't have the time constraint it can be done with 11 rats/prisoners, using a bisection algorithm.

  1. Mix a drop from each bottle and feed it to rat 1. If it lives, you've got no poison, so have a party. If it dies go on to step 2.
  2. Mix a drop from bottles 1-500 and feed it to rat 2. Depending whether it lives or dies, you can select the group where the poison is (note, you're throwing away information here, because you're just looking for 1 bottle, not all of them).

Continue in this way, and you'll be down to 1 bottle by the time you've got through 11 rats. If you know at least one is poisoned, you can skip the first step and do it in 10 rats.

Dr Xorile
  • 23,406
  • 3
  • 47
  • 125
  • You forgot that the poison doesn't always work, and that the original problem states that you have a time constraint of the same length of time that the poison takes to work. – genealogyxie Jun 14 '16 at 06:16