The Poisoned Wine Problem


#1

Originally published at: http://boingboing.net/2017/03/24/the-poisoned-wine-problem.html


#2

Well I thought that was rather clever. :slight_smile:


#3

Presumably each person has to drink a bit from 100 bottles, at regular intervals? Keep a record so you know what they were drinking one hour before they died.

Ah, is there meant to be a time limit stated? 1 hour, perhaps?

Not in a place to watch the video, but I assume this is the answer?


#4

Yeah, but the party needs to happen. You don’t have that much time.


#5

Ahhh damn I can’t believe I missed that. I was so close, but my solution was a binary search and a really long party opener.


#6

Actually, I think I’d just let everyone drink their own bottles.


#7

I’m not a coder, but it came to me pretty simply…

Prisoner 1 samples 500 bottles, Prisoner 2 the other 500. P1 dies.

P2 samples bottles 1-250, P3 samples 251-500, P3 dies.

etc… you will be able to get 1 one bottle.

edit: this might not work w/in the time allowed and, thus, there is a better solution.


#8

You are a wise king.


#9

For the problem to be tricky, you need to add the condition that you must have 999 bottles of poison-free wine shortly after 1 hour has elapsed.

(If you’re okay to start the party in one hour with only 900 safe bottles of wine [the remaining 99 safe bottles to arrive later], the problem is considerably easier.)


#10

Number the bottles from 0 to 999
Prisoner 1 takes 1 drop from all the odd numbered bottles
Prisoner 2 takes 1 drop from bottles 0,1 4,5 8,9 etc…
Prisoner 3 takes 1 drop from bottles 0,1,2,3 8,9,10,11, etc…
Prisoner 4 takes 1 drop from bottles 0,1,2,3,4,5,6,7, etc…

After one hour you read out the number of the poisoned bottle in binary using the dead prisoners


#11


#12

It was that lazy-ass bulb-fondling electrician, wasn’t it?


#13

That was my thought as well.


#14

Binary

I haven’t seen the video, but my solution would be to consider the ten prisoners a ten-digit binary number, with drink/abstain representing zero and one. Process of elimination would tell you the poisoned bottle.

Edit: nailed it.


#15

Number the bottles from 1 to 1000 in binary using 10 binary digits per bottle.
Prepare 10 cups, filled with a drop of each bottle for which the corresponding binary digit is “1”.

Let the 10 prisoners each drink a cup. After 1 hour, see which prisoners drop dead and which ones survive. This gives you the 10-digit binary number of the poisoned bottle.

In fact, the king could ask 24 extra guests/bottles and still make this work… (2^10 = 1024)


#16

I didn’t think of the binary assignment solution, but isn’t it possible to do this by division as well?

Divide wine into two groups of 500 bottles. Take a drop from each bottle group and place in two respective glasses. Feed to two prisoners. After an hour, a prisoner dies, and you know that group A is clear, and a bottle from group B is poisoned, divide group B into two groups of 250. Repeat.

You’ll go through 9 prisoners, but you’ll get specificity to one bottle before they all die.

EDIT: Ah - The video and description screw up the riddle. It should be phrased that the party takes place within the same time that the poison takes effect, this makes the binary solution the only valid one.


#17

Bingo. Not excluded from the riddle setup and the party is on right away!


#18

Hey man, you don’t need alcohol to have a fun time!

:neutral_face:


#19

This is the easiest question ever.

Dump every bottle. Serve your own vintage in carafes, and thank your guests for their gifts.

If you need to find your assassin, sure, use your prisoners. Or even better, a mammal that can smell volatiles. Like a dog. And classify/categorize the damn bottles.

No math is required, and noone needs to die.

I assume we all have our own vintages, right?


#20

The time to start of the party isn’t mentioned, so I assume that it’s a single one-shot test, and then you wait an hour to see which tasters die to pin-point the bottle. Otherwise a binary search would eventually find it.

Hmm, yup, it’ll work. (Except that odds are someone messes up or contaminates the wrong glass, etc.)