Poisoned Wine Problem
October 29th, 2015 at 9:35:15 AM
permalink
The emperor wants to throw a banquet in just over 24 hours and serve as much wine as possible. He owns 1,000 bottles but one of them is poisoned. To help determine which is the poisoned bottle, he may make use of ten prisoners on death row. However, it takes a day for the symptoms of the poisoned wine to manifest.
What testing strategy should the emperor use to maximize the minimum number of bottles he can safely serve? What is this number of safe bottles?
In other words, if a testing procedure may produce a range in the number of safe bottles, go with the worst case scenario of the smallest number of them.
For example, you could give each prisoner one drop from 100 distinct bottles. After seeing which prisoner falls sick you would be able to safely serve the other 900 bottles he didn't sample from. However, there is a way to serve even more than that.
What testing strategy should the emperor use to maximize the minimum number of bottles he can safely serve? What is this number of safe bottles?
In other words, if a testing procedure may produce a range in the number of safe bottles, go with the worst case scenario of the smallest number of them.
For example, you could give each prisoner one drop from 100 distinct bottles. After seeing which prisoner falls sick you would be able to safely serve the other 900 bottles he didn't sample from. However, there is a way to serve even more than that.
Have a nice day.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
October 29th, 2015 at 9:44:58 AM
permalink
I'm in a lazy overworked mood today, so I'll spoiler and explain what I think the answer is without doing the actual math =P.
I don't think this needs spoiled: He's an emperor. a) get more prisoners. b) move the party back 1 day and test twice, narrowing it down to 2 bottles, etc, etc. =)
It's going to be a cross section of the prisoners. I.E. Each of them gets 100 bottles but they also have some of the same bottles. Not only that you don't need to test all the bottles because if you leave out say 50 or 100 and none of the prisoners get sick then you know the final bottles have the poison. So if Prisoner 1 gets sick but prisoner 2 doesn't (and they had 50 bottles that were the same) then you could rule out down to 50 bottles and serve 950...
Prisoner 1: Bottles 1-100
Prisoner 2: Bottles 80-180
Prisoner 3: Bottles 160-260
Prisoner 4: Bottles 240-340
Prisoner 5: Bottles 320-420
Prisoner 6: Bottles 400-500
Prisoner 7: Bottles 480-580
Prisoner 8: Bottles 560-660
Prisoner 9: Bottles 640-740
Prisoner 10: Bottles 720-820
Remaining: Bottles 821-1000
None of them getting sick is also another way to check the bottles. So really you have 11 used cases. In the scenario above if any one of the prisoners gets sick then you can serve up to 920 bottles. If none of the prisoners get sick then it's a hit at only serving up to 820, but I'm hoping here instead of showing proper math to show how the problem could be solved =p.
EDIT - Each prisoner gets 90 bottles. If one of them gets sick then you can serve 910, if none of them gets sick you can serve 900... for example.
Prisoner 1: Bottles 1-100
Prisoner 2: Bottles 80-180
Prisoner 3: Bottles 160-260
Prisoner 4: Bottles 240-340
Prisoner 5: Bottles 320-420
Prisoner 6: Bottles 400-500
Prisoner 7: Bottles 480-580
Prisoner 8: Bottles 560-660
Prisoner 9: Bottles 640-740
Prisoner 10: Bottles 720-820
Remaining: Bottles 821-1000
None of them getting sick is also another way to check the bottles. So really you have 11 used cases. In the scenario above if any one of the prisoners gets sick then you can serve up to 920 bottles. If none of the prisoners get sick then it's a hit at only serving up to 820, but I'm hoping here instead of showing proper math to show how the problem could be solved =p.
EDIT - Each prisoner gets 90 bottles. If one of them gets sick then you can serve 910, if none of them gets sick you can serve 900... for example.
I don't think this needs spoiled: He's an emperor. a) get more prisoners. b) move the party back 1 day and test twice, narrowing it down to 2 bottles, etc, etc. =)
Playing it correctly means you've already won.
October 29th, 2015 at 10:00:46 AM
permalink
Hmmm......
prisoners are A, B, C, D, E, F, G, H, I, J
150 bottles/prisoner:
A: 1-150
B: 101-250
C: 201-350
D: 301-450
E: 401-550
F: 501-650
G: 601-750
H: 701-850
I: 801-950
J: 901-1000, 1-50
If B and C die, one bottle of 201-250 is tainted. Emperor can serve 950 bottles. If only C dies, then one bottle in 251 to 300 is tainted. Emperor can serve 950 bottles.
175 bottles/prisoner:
A: 1-175
B: 101-275
C: 201-375
etc.
B & C die: 201-275 : 75 bad bottles
B only: 176-201 = 25 bad bottles.
So then it comes down to interpretation [next spoiler]......
BTW mike i clicked new page and got this error [ you should investigate it ]
prisoners are A, B, C, D, E, F, G, H, I, J
150 bottles/prisoner:
A: 1-150
B: 101-250
C: 201-350
D: 301-450
E: 401-550
F: 501-650
G: 601-750
H: 701-850
I: 801-950
J: 901-1000, 1-50
If B and C die, one bottle of 201-250 is tainted. Emperor can serve 950 bottles. If only C dies, then one bottle in 251 to 300 is tainted. Emperor can serve 950 bottles.
175 bottles/prisoner:
A: 1-175
B: 101-275
C: 201-375
etc.
B & C die: 201-275 : 75 bad bottles
B only: 176-201 = 25 bad bottles.
So then it comes down to interpretation [next spoiler]......
If the question means "Of all the distinct possible outcomes, what's the most the emperor can serve his guest?" Then the answer is 999. Because he can give prisoner A bottle #1 only. And if he dies, the other 999 bottles are not poisoned. This is the MOST amount of bottles that the emperor can serve, IF that prisoner dies.
However, I don't think that is the meaning of the question. I think the question is asking how much can he DEFINITELY serve his guests, regardless of whether or not who dies or whatever. In other words, in any such case, the emperor would always be able to serve X amount of bottles, despite who died.
However, I don't think that is the meaning of the question. I think the question is asking how much can he DEFINITELY serve his guests, regardless of whether or not who dies or whatever. In other words, in any such case, the emperor would always be able to serve X amount of bottles, despite who died.
I say 999 for "question possibility #1.
And 950 for "question possibility #2" [more likely meaning of question].
And 950 for "question possibility #2" [more likely meaning of question].
BTW mike i clicked new page and got this error [ you should investigate it ]
RECENT THREADS
Sorry, an internal error has occurred. The error has been logged and will be reviewed.
In the meantime, please try your request again if you haven't already.
If the problem occurs more than once, rest assured that it will be investigated and fixed soon.
October 29th, 2015 at 10:06:00 AM
permalink
I think the answer is slightly more ...
909.
Rather than dividing the number into 10 divide it by 11 and giving each prisoner drops from 91 bottles. Thus you either find out which block of 91 is bad, or if all the prisoners live, then the 90 you didn't serve were bad.
Rather than dividing the number into 10 divide it by 11 and giving each prisoner drops from 91 bottles. Thus you either find out which block of 91 is bad, or if all the prisoners live, then the 90 you didn't serve were bad.
October 29th, 2015 at 10:27:33 AM
permalink
They are all poisoned. I spent the last 2 years building an immunity to iocaine powder.
A falling knife has no handle.
October 29th, 2015 at 10:29:33 AM
permalink
Charliepatrick's answer is the same one I was going to post, but I was suspicious as it was waaaay too straightforward and simple compared to every other puzzle Wizard puts out. Going with it anyway...
If the House lost every hand, they wouldn't deal the game.
October 29th, 2015 at 10:43:29 AM
permalink
My answer unless I think of a way to get more
916
"Truth is ever to be found in the simplicity, and not in the multiplicity and confusion of things."
-- Isaac Newton
October 29th, 2015 at 10:52:12 AM
permalink
But you can go higher! I think...
Continuiing from before...
prisoners are A, B, C, D, E, F, G, H, I, J
150 bottles/prisoner:
A: 1-150, 201-225
B: 101-250, 301-325
C: 201-350, 401-425
D: 301-450, 501-525
E: 401-550, 601-625
F: 501-650, 701-725
G: 601-750, 801-825
H: 701-850, 901-925
I: 801-950, 1-25
J: 901-1000, 1-50, 101-125
If D dies, it can only be 301-450 or 501-525.
C (301-350)
E (401-450)
F (501-525)
are also candidates to die if D has died.
If it's in the D&C section (301-350), 50 bad bottles.
If it's in the D&E section, (401-450), 50 bad bottles.
If it's in the D&F section, 25 bad bottles.
We can do the same thing I've done above, with inter-changing (or inter-dispersing?) 25 bottles to other prisoners, in such a way [I ain't writing all that sh** out!!], such that 25 bottles can be completely excluded (one of which is poisoned), leaving 975 good bottles to be served, in any case.
However, I infer (see that's a fancy word there), that we can do the same/similar thing, but get it down to 1, 9, 10, 11, or 24 bottles.
Continuiing from before...
prisoners are A, B, C, D, E, F, G, H, I, J
150 bottles/prisoner:
A: 1-150, 201-225
B: 101-250, 301-325
C: 201-350, 401-425
D: 301-450, 501-525
E: 401-550, 601-625
F: 501-650, 701-725
G: 601-750, 801-825
H: 701-850, 901-925
I: 801-950, 1-25
J: 901-1000, 1-50, 101-125
If D dies, it can only be 301-450 or 501-525.
C (301-350)
E (401-450)
F (501-525)
are also candidates to die if D has died.
If it's in the D&C section (301-350), 50 bad bottles.
If it's in the D&E section, (401-450), 50 bad bottles.
If it's in the D&F section, 25 bad bottles.
We can do the same thing I've done above, with inter-changing (or inter-dispersing?) 25 bottles to other prisoners, in such a way [I ain't writing all that sh** out!!], such that 25 bottles can be completely excluded (one of which is poisoned), leaving 975 good bottles to be served, in any case.
However, I infer (see that's a fancy word there), that we can do the same/similar thing, but get it down to 1, 9, 10, 11, or 24 bottles.
October 29th, 2015 at 11:04:56 AM
permalink
A, B, C, D, E, F, G, H, I, J
Each get 200 (not sure why!)
A: 1-200
B: 101-300
C: 201-400
D: 301-500
E: 401-600
F: 501-700
G: 601-800
H: 701-900
I: 801-1000
J: 901-1000, 1-100
They each get 10 bottles from a different section.
A: 201-210, 301-310, 401-410, 501-510, 601-610, 701-710, 801-810, 901-910,
B: 211-220, 311-320, 411-420, 511-520, 611-620, 711-720, 811-820, 911-920, 11-20
C: 321-330, 421-430, 521-530, 621-630, 721-730, 821-830, 921-930, 21-30, 121-130
D: 431-440, 531-540...
E: 541-550...
F: 651-660...
G: 761-770...
H: 871-880...
I: 981-990...
J: 1-10
actually instead of re-writing what I wrote above, I'm going to do the same thing, but give them 11 bottles from a different section.
A: 201-211, 301-311, 401-411, 501-511, 601-611, 701-711, 801-811, 901-911, 1-11
B: 312-322, 412-422, 512-522, 612-622, 712-722, 812-822, 912-922, 12-22, 112-122, 212-222
screw this im done
October 29th, 2015 at 11:07:09 AM
permalink
You can identify the poisoned bottle and serve the rest.
Because 1000 <= 2^10
Label prisoners = A..J; bottles 0..999
Prisoner A drinks from every other bottle (the even-numbered bottles 0, 2, 4, 8, etc.)
Prisoner B drinks two bottles in a row, then skips 2, then drinks another 2 (0..1, 4..5, 8..9)
Prisoner C drinks 4 in a row, skips the next 4, etc. (0..3, 8..11, 16..19)
Prisoner D drinks/skips 8
Prisoner E drinks/skips 16
Prisoner F drinks/skips 32
Prisoner G drinks/skips 64
Prisoner H drinks/skips 128 (0..127, 256..511, etc.)
Prisoner I drinks/skips 256 (0..255, 512..767)
Prisoner J drinks/skips 512 (0..511)
Based on who dies (or doesn't) you'll have the exact binary identification of the poisoned bottle and therefore the rest are safe.
Prisoner A drinks from every other bottle (the even-numbered bottles 0, 2, 4, 8, etc.)
Prisoner B drinks two bottles in a row, then skips 2, then drinks another 2 (0..1, 4..5, 8..9)
Prisoner C drinks 4 in a row, skips the next 4, etc. (0..3, 8..11, 16..19)
Prisoner D drinks/skips 8
Prisoner E drinks/skips 16
Prisoner F drinks/skips 32
Prisoner G drinks/skips 64
Prisoner H drinks/skips 128 (0..127, 256..511, etc.)
Prisoner I drinks/skips 256 (0..255, 512..767)
Prisoner J drinks/skips 512 (0..511)
Based on who dies (or doesn't) you'll have the exact binary identification of the poisoned bottle and therefore the rest are safe.
Let me fix that because I was being backwards:
Label prisoners 0..9
Bottles 0..999
For each prisoner 0..9, prisoner N *skips* the first 2^N bottles, drinks the next 2^N, skips the next 2^N, etc.
Then the number of the poisoned bottle is the binary number formed by the numbers of the dead prisoners. I.e. if prisoner 0, 6 and 8 die, the poisoned bottle is 2^0+2^6+2^8 = 321. If no prisoners die, bottle 0 is poisoned.
Label prisoners 0..9
Bottles 0..999
For each prisoner 0..9, prisoner N *skips* the first 2^N bottles, drinks the next 2^N, skips the next 2^N, etc.
Then the number of the poisoned bottle is the binary number formed by the numbers of the dead prisoners. I.e. if prisoner 0, 6 and 8 die, the poisoned bottle is 2^0+2^6+2^8 = 321. If no prisoners die, bottle 0 is poisoned.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
October 29th, 2015 at 11:20:02 AM
permalink
999.
give prisoner 1 a taste of the first 500 bottles. if he dies, you know one of the first 500 bottles is poisoned. If he doesn't, the one of the 2nd 500 is poisoned.
each prisoner can determine whether or not the poison is in one half of the remaining bottles, or the other half.
prisoner #2 gets to sample 250 of the 500 bottles where you know the poison is.
#3 gets 125 out of 250, #4 gets 63 out of 125 - at this point the poison is either in the 63 or the 62, but I'll just round up:
#5 tastes from 32, #6 from 16, #7 from 8, #8 from 4, #9 from 2, and finally #10 gets to taste one or the other of the last bottles.
give prisoner 1 a taste of the first 500 bottles. if he dies, you know one of the first 500 bottles is poisoned. If he doesn't, the one of the 2nd 500 is poisoned.
each prisoner can determine whether or not the poison is in one half of the remaining bottles, or the other half.
prisoner #2 gets to sample 250 of the 500 bottles where you know the poison is.
#3 gets 125 out of 250, #4 gets 63 out of 125 - at this point the poison is either in the 63 or the 62, but I'll just round up:
#5 tastes from 32, #6 from 16, #7 from 8, #8 from 4, #9 from 2, and finally #10 gets to taste one or the other of the last bottles.
October 29th, 2015 at 11:26:12 AM
permalink
Quote: Dalex64999.
give prisoner 1 a taste of the first 500 bottles. if he dies, you know one of the first 500 bottles is poisoned. If he doesn't, the one of the 2nd 500 is poisoned.
each prisoner can determine whether or not the poison is in one half of the remaining bottles, or the other half.
prisoner #2 gets to sample 250 of the 500 bottles where you know the poison is.
#3 gets 125 out of 250, #4 gets 63 out of 125 - at this point the poison is either in the 63 or the 62, but I'll just round up:
#5 tastes from 32, #6 from 16, #7 from 8, #8 from 4, #9 from 2, and finally #10 gets to taste one or the other of the last bottles.
Very close. (I didn't get it right, btw.) But since you only have 24 hours before the party begins, and it takes 24 hours for the symptoms to kick in, doing it your way, you'd only have 500 confirmed non-poisoned bottles by the time the party starts.
October 29th, 2015 at 11:32:42 AM
permalink
Each prisoner (0-9) gets 300 drops... one from each bottle (000-999) that has a digit in its number that matches the prisoner's number. So, Prisoner 0 would get drops from all bottles that are numbered 0XX, X0X, and XX0, where X could be any digit.
Now, let's see who gets sick (assume A, B, and C each represent a distinct digit from 0 to 9)...
Option #1 -- 3 prisoners, A, B, & C get sick -- we have limited the poison to 6 bottles -- ABC, ACB, BAC, BCA, CAB, or CBA. 994 bottles are available to be served.
Option #2 -- only 2 prisoners, A & B get sick -- we have also limited the poison to 6 bottles -- AAB, ABA, ABB, BAA, BBA, or BAB. 994 bottles can be served.
Option #3 -- only 1 prisoner, A gets sick -- we have found the bottle, it's #AAA. 999 bottles can be served.
So, the emperor may serve at least 994 bottles safely. Or did I just poison some of the guests?
Now, let's see who gets sick (assume A, B, and C each represent a distinct digit from 0 to 9)...
Option #1 -- 3 prisoners, A, B, & C get sick -- we have limited the poison to 6 bottles -- ABC, ACB, BAC, BCA, CAB, or CBA. 994 bottles are available to be served.
Option #2 -- only 2 prisoners, A & B get sick -- we have also limited the poison to 6 bottles -- AAB, ABA, ABB, BAA, BBA, or BAB. 994 bottles can be served.
Option #3 -- only 1 prisoner, A gets sick -- we have found the bottle, it's #AAA. 999 bottles can be served.
So, the emperor may serve at least 994 bottles safely. Or did I just poison some of the guests?
On a personal note, this was messy business. I think I'll stick to beer at the banquet!
LOL!! :)Quote: MoscaThey are all poisoned. I spent the last 2 years building an immunity to iocaine powder.
Actually, each prisoner would get fewer than 300 drops at the beginning. I'm thinking now the number of bottles each prisoner would sample from is 271. But the method should remain the same.
"Dealer has 'rock'... Pay 'paper!'"
October 29th, 2015 at 11:33:01 AM
permalink
Ahh. I missed that part of the question, about the onset time of the poison.
October 29th, 2015 at 11:46:02 AM
permalink
I edited to the wording of the OP to show that you should assume the worst case scenario for any given set of tests. For example, if you just give prisoner #1 a drop of bottle #1, then you'll narrow down the number of safe bottles to either 999 or 1, depending on if he gets sick. Assume the lower number of 1, so you would have only one bottle for the banquet.
To BBB and CP -- That is indeed an improvement but you can improve it further.
ME -- You're right. Please nobody click on his answer or solution unless you've completely given up. His hint is a pretty big hint.
Finally, I'd like to emphasize that it takes a day to see the results of a test and you've only got just over a day. So just ONE round of tests.
To BBB and CP -- That is indeed an improvement but you can improve it further.
ME -- You're right. Please nobody click on his answer or solution unless you've completely given up. His hint is a pretty big hint.
Finally, I'd like to emphasize that it takes a day to see the results of a test and you've only got just over a day. So just ONE round of tests.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
October 29th, 2015 at 12:30:35 PM
permalink
Assign each of the 10 prisoners an integer from 1 to 10, and assign each bottle a 10-digit binary integer representing the decimal numbers 1 to 1000.
If the Nth digit of a bottle has a 1 (with 1 as the leftmost digit and 10 as the rightmost), then give a drop of that bottle's wine to prisoner number N.
The next day, the numbers of the dead prisoners are the positions of the 1s in the poisoned bottle's number, and the numbers of the living prisoners are the positions of the 0s. You know which bottle is poisoned, so you may safely serve the other 999.
For example, if prisoners 1, 2, 5, 6, 8, and 10 are dead, then the poisoned bottle is 1100110101.
October 29th, 2015 at 12:54:47 PM
permalink
Quote: ThatDonGuy
Assign each of the 10 prisoners an integer from 1 to 10, and assign each bottle a 10-digit binary integer representing the decimal numbers 1 to 1000.
If the Nth digit of a bottle has a 1 (with 1 as the leftmost digit and 10 as the rightmost), then give a drop of that bottle's wine to prisoner number N.
The next day, the numbers of the dead prisoners are the positions of the 1s in the poisoned bottle's number, and the numbers of the living prisoners are the positions of the 0s. You know which bottle is poisoned, so you may safely serve the other 999.
For example, if prisoners 1, 2, 5, 6, 8, and 10 are dead, then the poisoned bottle is 1100110101.
Correct!
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
October 29th, 2015 at 12:55:27 PM
permalink
Quote: MoscaThey are all poisoned. I spent the last 2 years building an immunity to iocaine powder.
Dammit. You beat me to it =p
The opinions of this moderator are for entertainment purposes only.
October 29th, 2015 at 1:55:00 PM
permalink
Actually for me it gave it immediately!Quote: WizardME -- ...His hint is a pretty big hint.
Many years ago at school we were given a deck on 6x4 index cards with holes across the top. Some of the holes were intact while others were cut to the top. This represented the binary digits of the card number. Thus if you put a knitting needle through (say position 1) half the cards would be picked up and the others wouldn't. The way to sort them was to put knitting needles through holes 1, 2, 3 etc. This puzzle is similar except you keep the part of the deck you want. Thus with 1000 cards and 10 holes, you can eventually select the just the one card you want.
October 29th, 2015 at 3:24:34 PM
permalink
That's a good quiz. I am going to give that to my daughter to solve.
-----
You want the truth! You can't handle the truth!
October 29th, 2015 at 3:52:53 PM
permalink
If I ask my dad....he won't sleep for a week!
October 29th, 2015 at 7:27:50 PM
permalink
Quote: MoscaThey are all poisoned. I spent the last 2 years building an immunity to iocaine powder.
So, clearly, I cannot choose the wine in front of you.
I heart Crystal Math.
October 30th, 2015 at 9:22:09 PM
permalink
Follow up question if I may…
Assuming the emperor uses the testing strategy which maximizes the minimum number of bottles he can safely serve…
How many “drops” of wine must he give to the prisoners?
Assuming the emperor uses the testing strategy which maximizes the minimum number of bottles he can safely serve…
How many “drops” of wine must he give to the prisoners?
October 30th, 2015 at 10:51:08 PM
permalink
Quote: PeeMcGeeFollow up question if I may…
Assuming the emperor uses the testing strategy which maximizes the minimum number of bottles he can safely serve…
How many “drops” of wine must he give to the prisoners?
Add up the total number of set bits in the binary representations of [0..999]. I get 4932.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
October 31st, 2015 at 12:22:07 AM
permalink
How would the answer change if there were 2 poisoned bottles? How many prisoners would he need to safely identify the 998 safe bottles?
October 31st, 2015 at 2:13:42 PM
permalink
Quote: PeeMcGeeFollow up question if I may…
Assuming the emperor uses the testing strategy which maximizes the minimum number of bottles he can safely serve…
How many “drops” of wine must he give to the prisoners?
If there were 1024 bottles, there would be every combination of a sequence of 10 zeros and ones. A "1" corresponds to a drop and there are an average of 5 ones per prisoner number. So 1024*5/2 = 2,560.
It would save a few drops of wine to start numbering the prisoners with zero, so we eliminate prisoners number 1000 to 1027.
Here is the binary representation of 1000 to 1027:
1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 0 1 0 0 1
1 1 1 1 1 0 1 0 1 0
1 1 1 1 1 0 1 0 1 1
1 1 1 1 1 0 1 1 0 0
1 1 1 1 1 0 1 1 0 1
1 1 1 1 1 0 1 1 1 0
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 0 0 0
1 1 1 1 1 1 0 0 0 1
1 1 1 1 1 1 0 0 1 0
1 1 1 1 1 1 0 0 1 1
1 1 1 1 1 1 0 1 0 0
1 1 1 1 1 1 0 1 0 1
1 1 1 1 1 1 0 1 1 0
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 1
1 1 1 1 1 1 1 0 1 0
1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
The number of ones above is 188. So, the total drops of wine is 2560 - 188 = 2372.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
October 31st, 2015 at 2:17:57 PM
permalink
Quote: jopkeHow would the answer change if there were 2 poisoned bottles? How many prisoners would he need to safely identify the 998 safe bottles?
There are combin(1000,2)=499,500 combinations of the two poisoned bottles.
With 19 prisoners we would have 2^19=524,288 combinations of possible outcomes, which is enough.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
October 31st, 2015 at 6:50:44 PM
permalink
Quote: WizardQuote: PeeMcGeeFollow up question if I may…
Assuming the emperor uses the testing strategy which maximizes the minimum number of bottles he can safely serve…
How many “drops” of wine must he give to the prisoners?
If there were 1024 bottles, there would be every combination of a sequence of 10 zeros and ones. A "1" corresponds to a drop and there are an average of 5 ones per prisoner number. So 1024*5/2 = 2,560.
It would save a few drops of wine to start numbering the prisoners with zero, so we eliminate prisoners number 1000 to 1027.
Here is the binary representation of 1000 to 1027:
1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 0 1 0 0 1
1 1 1 1 1 0 1 0 1 0
1 1 1 1 1 0 1 0 1 1
1 1 1 1 1 0 1 1 0 0
1 1 1 1 1 0 1 1 0 1
1 1 1 1 1 0 1 1 1 0
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 0 0 0
1 1 1 1 1 1 0 0 0 1
1 1 1 1 1 1 0 0 1 0
1 1 1 1 1 1 0 0 1 1
1 1 1 1 1 1 0 1 0 0
1 1 1 1 1 1 0 1 0 1
1 1 1 1 1 1 0 1 1 0
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 1
1 1 1 1 1 1 1 0 1 0
1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
The number of ones above is 188. So, the total drops of wine is 2560 - 188 = 2372.
Cool, that’s what I did. I do think you intended to do 1024*10/2 though. Which would agree with MathExtremist’s count.
But hopefully these drops don’t have to be too large ;). Even if they’re just 5ml the emperor will lose like 33 bottles in the testing (assuming 750ml bottles).
Quote: Wizard
There are combin(1000,2)=499,500 combinations of the two poisoned bottles.
With 19 prisoners we would have 2^19=524,288 combinations of possible outcomes, which is enough.
But this would only work if the prisoner can only die from drinking the pair which contains both poisoned bottles, correct? So let say bottle A and bottle B contains the poison…then drinking a drop from AC (for example) cannot be lethal. Also if a prisoner drinks from AC and BC, then that cannot be lethal as well (even though he did drink from both poisoned bottles). I hope that makes sense….
