Posted June 29th, 2006 @ 09:22am by Erik J. Barzeski
A king is having a feast. His intelligence officer comes up to him 30 days before the feast and tells the king that 1 of his 1,000 bottles of wine had been poisoned by his enemies. The poison kills immediately after 29.9 days, but has no other effects beforehand. The king has only 10 wine tasters. How will he find out which bottle of wine was poisoned in time for the feast?
This blog contains posts, all written by me, and comments, only some of which were written by me.
About Me
Disclaimer
The Sand Trap
… via Email
firstname@lastname.com
(Think about that one a little.)
… via IM
AIM: iacas
MobileMe: iacas
flickr: iacas
Yahoo: iacas
Twitter: iacas
MSN: iacas@hotmail.com
Xbox Live: erikjb
Google Talk: erikjb@gmail.com
ICQ: 8186546
Don't email me at any of the above IM addresses or I may never see the email. I use these accounts primarily for chat (IM) only.
… on Facebook
http://facebook.com/iacas
Donate Life: Because if you're not using your body parts, someone else can.
Posted 29 Jun 2006 at 9:40am #
Torture the intelligence officer. What are his sources? What's his scheme? He's clearly gunning to put the king to panic. Nuts to that guy!
Posted 29 Jun 2006 at 9:41am #
PS. Binary.
Mix wines in pairs, such that each tester gets a different combination of wines. In the end, you'll trace it down by seeing the pattern in the people that die.
Posted 29 Jun 2006 at 9:52am #
So let's say 1 = drink, 0 = doesn't drink and each digit = one wine test:
Wine #1
0000000001
Wine #2
0000000010
Wine #3
0000000011
....
Wine #1000
1111101000
On average, less than 5 testers will die. Worst case, nine.
Posted 29 Jun 2006 at 10:15am #
I would have said the same as Carl. Do you mean it's not the correct solution?
Posted 29 Jun 2006 at 9:59am #
Carl's got it.
Posted 29 Jun 2006 at 12:27pm #
It is something as simple as dividing the wine up between the 10 taster, and having each one take a sip from each of their 100 bottles, every minute. That way if you keep track of the order people tasted the wine in, you'd be able to figure out what bottle of wine was poisoned based on the time the taster dies.
Of couse this would only work if the poison killed EXACTLY 29.9 hours after ingesting. If not you would still know 90% of the wine was safe to drink. And if 90% isn't enough wine for the feast, he is a king and I am sure he could afford to but the extra 100 bottles in those 30 days.
Posted 30 Jun 2006 at 1:28am #
Simply look for the opened bottle, right?
Behold the power of Google :^)
Posted 30 Jun 2006 at 10:30pm #
This is easy. Send all the wine to the enemy and buy more wine. Tasters are more expensive than bottles.
Posted 30 Jun 2006 at 10:36pm #
You basically have 1/10th of a day to test *every* bottle of wine in some manner before the feast. Anything that can't be completed in 1/10th of a day is ruled out, as the poison might not have taken effect before the feast.
This leaves to my mind:
1. look for the opened bottle, or a bottle that has been tampered with in some way. That assumes a dumb ass enemy that hasn't gone to some effort to reseal the wine in a convincing manner.
Point 1 is a prime example of why I dislike puzzles, because the "solution" is often dependent on some big assumptions.
2. have each wine taster take a sip of wine. That would mean each taster needs to have a sip from 100 bottles in a 1/10th of a day. You would probably have your wine tasters pretty sloshed by that point, although it's do-able. In Australia we have a drinking game called the century club (or 100 club) where the idea is 100 sips of beer in 100 minutes. A 10th of a day is 144 minutes, so it's actually easier than our drinking game 🙂
Point 2 also depends on concentrations. If the poison is deadly only in high concentrations, it might be possible to homogenise similar types of wine from the cellar in order to dilute the poison.
3. purchase a significant number of premium, untained bottles and ensure that your most important guests and dignitaries drink from those bottles only. So the risk of dying is shifted to a more disposable section of the guest list.
Posted 01 Jul 2006 at 8:50pm #
Forget about tasting the wine. Just have the feast in 30 days. The king should not drink any wine at the feast (claim ill or something). Then when someone dies 29.9 days after the feast, who's going to trace their death to the feast?
Posted 21 Mar 2007 at 10:19pm #
I think the idea is to form 1000 different experimental groups. 2 people, A and B, can form 3 different groups, A, B, and A+B. Each group tastes one wine; if all the people within the same group die at the end of 30th day then we can figure out the poisoned wine. So the question becomes much simpler. At least how many people do we need to form 1000 experimental groups? I believe the answer is 10 since we can form 1023 groups from only 10 people. 2^10-1=1023. Is it right?
Posted 09 Apr 2007 at 10:33am #
well, sure... yes, inclusion-exclusion.
um well, actually 2^k - because actually the empty set
is also a group - (in this case ie. nobody dies)
so can actually have 1024.
i think inclusion-exclusion graphs are not really
sufficient for bigger numbers of elements - not able to
get all the possible inclusion-exclusions in the diagram,
I just drew a table with each entry (row) a unique
arragement of included members (members with ticks).
P.S. can somebody get this guy to change the wording
on his site? it says 'dies' but then we could just have one
person test each bottle and only one person would die...
I got a bit confused at first. 🙂
Posted 09 Apr 2007 at 10:54am #
yeah, sorry - here's the website:
http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml
the wording should be maybe - "he only has 10 prisoners
to use" or something like that.
but it's sort of seems right - reading that after you've
worked it out... how many of them might die??
if we put each bottle in an inclusion-exclusion region,
it can only affect _that region_ - what might that be?
sure, it might be in the "all drink it" region... any of the
regions... maybe lucky and none drink it... heh heh, getting
confused here - not the regions of the bottles - it's the
regions of the people... we don't care about the region's
number of people in it, just that they are different regions.
yeah, with the diagrams, eg. with 4 - circle-type things,
we don't have regions of [the two opposite (on the drawn
diagram) circles(people) but not the other two].
0: 1
1 person affected: k
2: 2CK (ways of choosing 2 from k)
.
.
yeah, etc.
.
k: 1
these (1, k, C{2,k} , .... , k, 1) are rows in pascal's triangle. - number of
regions for each "number of people dying" (these add to 2^k)
if put bottle randonly into any of these, i think guess that
number of people dying would be... (it reads from left to right
as (0, 1, 2, ... k) people dying, hmm...
- some fancy maths? maybe something to do with e? maybe not? heh heh... me tired.
Posted 09 Apr 2007 at 11:13am #
oh yeah, i mean e as in for really large numbers
for the smaller ones, we can just figure it out
eg. for 1 2 1
(0*1 + 1*2 + 2*1)/(1+2+1) = 1 (average no. of people getting the bottle)
for 1 3 3 1
(1*0 + 3*1 + 3*2 + 1*3)/(1+3+3+1) = 12/8 = 1.5
1 4 6 4 1
(0*1 + 1*4 + 2*6 + 3*4 + 4*1)/16 = 32/16 = 2
4*1 + 4*4 + 4*6 / 2
1 5 10 10 5 1
(0*1 + 1*5 + 2*10 + 3*10 + 4*5 + 5*1)/32 =
10*5 + 5*5 + 1*5 } / 32
= 16*5÷32 = 2.5
oh wait... this is looking really simple... for k people, the probability is half... did i miss something really simple?
maybe i should have played around with it more
should this be so obvious?...
hmm...
if switched the 'number of people' (- of the regions - order)
around, then no difference ... cos symmetry we got the ones
with eg. 3 and ones with k-3 - same number... so can switch
around so, should/must be no difference -
so the probability must be half ( - 0.5) ?
hmm... heh heh, take it easy Paul... 🙂
Posted 27 Sep 2007 at 11:03pm #
I prefer Luke Burton's #2 solution. If the wine is divided into 10 groups of 100 bottles, each taster must taste 100 bottles in a tenth of a day. Whichever taster keels over just before the feast lets the king know which bottles to keep out of the festivities. Nine hundred bottles should be more than adequate for the feast. After the feast, the remaining tasters divide up the segregated bottles (about 11 each). After 30 more days, the king would have only about 11 bottles in the "undrinkable" group. The remaining tasters now only have to taste one or two bottles each. Eventually the good wine will all be consumable and the poisoned wine will be identified, with the loss of only 3 or 4 tasters -- a small payment when you're a king and 999 bottles of wine are at stake.
Posted 26 Nov 2007 at 3:18pm #
Here is my idea:
Taster #1 tastes only odd numbered bottles.
Taster #2 tastes only even numbered bottles.
Taster #3 tastes only every third bottle beginning with bottle 3.
Taster #4 tastes only every fourth bottle.
Taster #5 tastes only every fifth bottle.
Taster #6 tastes only every sixth bottle, and so on through taster #10.
The assumption with this puzzle is that even a drop of the wine will kill since at least two tasters will be sampling 500 bottles of wine, so that there will be wine enough left over for the party. The problem with my solution is that prime numbers above 10 would only be tasted by the Taster #1, impossible then to determine the exact bottle. The primes would have to be assigned in some manner as well so that in the final result, every bottle number has only one possible and unique combination of taster deaths.
Posted 31 Mar 2008 at 7:11pm #
how about if it says n number of bottles are poisoned? what would the answer be then? any ideas?
Posted 25 Sep 2008 at 3:55am #
Number of wine testers available 10
Number of bottles 1000
Each tester can either live or die. Hence each tester can distinguish between a maximum of 2 possibilities. This is like one tester representing one binary digit. With n testers, you can distinguish between 2^n possibilities, i.e. 2^n bottles of wine.
For 1000 bottles, you need log2(1000) rounded up = 10 testers.
Procedure:
You create a cocktail for each tester as follows:
Each tester represents one binary digit, from 1 to 10.
For each bottle, you number it, and use the binary representation to select testers.
E.g. for bottle 1, the binary is 0000000001, so tester 1 only tries it.
For bottle 19, the binary is 0000010011, so testers 1,2 and 5 try it.
Each tester's cocktail consists of a drop of wine from every bottle which has a one in 'their' digit.
After 20 hours, you note which testers died. You then construct a number with '1's for the testers that died, '0's for others. That is the number of the poisoned bottle.
So, if testers 4,5 and 6 die, the bottle that is poisoned is 0000111000 = 48.
If memory serves me right, this is very similar to the Hamming code, a way of providing single error correction, double error detection with parity bits.
Posted 11 Nov 2008 at 7:10am #
30 days 43200 mins
29.9days 43056 mins
if d person tastes the poisoned bottle at 1st min he will die at 43057th min as said effect will be after 29.9 days
Taster 1st min 43057 th min 43058 43059
1
2
3
4
5
6
7
8
9
10
As and when the intelligence officer told him ,king should make 1000 bottles into 10 parts.
so that each taster will get to taste 100 bottles.
distibution of bottles
1st taster 1 to 100 number bottles
2nd taster 101 to 200 number bottles
.
.
.
.
10th taster 901 to 1000 numbered bottles
minute wise numbered bottle tasting
1st taster 1 st min bottle 1 2nd taster 1st min bottle 101 3rd taster 1st min bottle 201 … … 10th taster 1st min bottle 901
1st taster 2nd min bottle 2 2nd taster 2nd min bottle 102 3rd taster 2nd min bottle 202 … … 10th taster 2nd min bottle 902
. . . … … .
. . . … .. .
. . . … … .
1st taster 100th min bottle 100 2nd taster 100th min bottle 200 3rd taster 100th min bottle 300 …. …. 10th taster 100th min bottle 1000
coz the poison starts only after 29.9 days.
ie the person who take the poisoned bottle at min 1 will die at 107757 th min
tasted poisoned bottle will xpire at
1st min 43057th min
2nd min 43058 th min
3rd min 43059th
100th min 43156 th min
if a taster will die at 43057th min then it is clear that the bottle he had tasted at min 1 is poisoned
so if taster 1 will die at 43057th min then the bottle he tasted at min 1 was poisoned which is number 1 bottle
similarly if taster 2 will die at 43059 th min then we can find out bottle number 103 is poisoned coz he has tasted bottle 103 at 3rd min
in this way the king can trace out the poisoned bottle 44mins before the party starts…………….
hope I was able to solve the puzzle
Posted 28 Jan 2009 at 7:49pm #
It doesn't matter either way which one in the thousand is poisoned or not. In the end, none of them can be drank because if they aren't tested, nobody can drink it because of the poison. If they DO test it, nobody can drink it since the testers drank it, so it would be a waste of time. So either way at the end of the time period, by the time the feast comes, there would be no wine to drink either way.
Posted 11 Oct 2010 at 4:42am #
There is another very humane option.
Use 64 prisoners in a matrix set-up: 31 rows and 33 columns
just 2 prisoners will die!
Posted 21 Sep 2011 at 3:23am #
What you really should ask is "why the hell just not get more wine as opening bottles 30 days before the feast would ruin them"
Posted 26 Sep 2011 at 5:39pm #
Just use the binary combinations and correspond those to each wine bottle. For example of there are 8 bottles of wine and we have three people use the following combinations:
000
001
010
011
100
101
110
111
Where each digit represents a person and each combination represents one wine bottle (1 means they drank and 0 means they didn't). Then depending on the combination of who dies that corresponds to one wine bottle.
For example from above is the first person died and the rest lived that corresponds to 100. So whichever wine bottle corresponds to that combination is the poisoned one.