4 ms·

Here's my solution to Poisoned wine. 48 hours, and a prisoner will die 24 hours after drinking from the poisoned wine. you only need one prisoner, and a decen

Here's my solution to Poisoned wine. 48 hours, and a prisoner will die 24 hours after drinking from the poisoned wine. you only need one prisoner, and a decent stopwatch. Have him drink from a barrel of wine every 6 minutes, watch the exact moment he dies. Take the time in minutes, divide by 6 and that's the wine barrel that's poisoned (zero indexed).

anatoly 16y ago
Yeah, "within 24 hours" doesn't mean "in exactly 24 hours". Edit: Here's my hint to those who have trouble solving this puzzle. Don't read it before trying to solve yourself! http://pastehtml.com/view/1c02p65.txt http://pastehtml.com/view/1c02p65.txt
124816 16y ago
> one dies within 24 hours Is it really correct to interpret that as "dies in exactly 24 hours"? Edit: My solution, which assumes that after tasting wine it could take any time between 0 and 24h to die; and that it could vary between tastings: Given N slaves, you can test 2^N wines in a single iteration, as so: - A set of size N has 2**N distinct sub-sets. - Have each distinct sub-set taste a different wine. - After 24h, everyone who drank the poisoned wine will be dead, and, provided you took notes about which set consumed which wine, you can look up which wine they drank. - (Note also, you leave one wine untasted; if nobody dies, it is the poisoned one.) For our first iteration, we have each set taste multiple wines, like so: - The set with five slaves will taste a single wine. - Sets with four slaves will taste 2 wines. - Sets with three slaves will taste 4 wines. - Sets with two slaves will taste 8 wines. - Sets with one slave will taste 16 wines. - We leave 32 wines untouched. Of course, in general: a set with N slaves will taste 2^(5 - N) wines. After 24 hours, all slaves who drank poisoned wine will be dead, and we will have the following possible states: - One slave is dead. We know the 16 wines he drank, and we have 4 slaves left. As shown above, we can easily determine which of the 16 wines is poisoned in a single iteration. - N slaves are dead. We know which 2**(5-N) wines they drank, and we have 5-N slaves left. So we can easily determine which of the 2**(5-N) wines is poisoned in a single iteration. Note that N = 0 is a valid case above. So, we need to calculate how many wines we can test in this manner. Going through each set: - 5 choose 1 * 16 = 80 - 5 choose 2 * 8 = 80 - 5 choose 3 * 4 = 40 - 5 choose 4 * 2 = 10 - The one wine that all slaves drink the first time. - The 32 wines none of them drink the second time. The sum is 243. Garçon!!! Fetch three more barrels!
- jaekwon 16y ago
  i got the same result.
TheNewAndy 16y ago
Note that it says the prisoner will die "within 24 hours". My solution (which looks somewhat correct, so don't read unless you want it spoiled) Day 0: Where all numbers are base 6 (240 in base 6 == 104) d0 = last digit of barrel number (in base 6) d1 = second last digit of barrel number (in base 6) Servant 0: drink if d0 == 0 or d1 == 0 Servant 1: drink if d0 == 1 or d1 == 1 Servant 2: drink if d0 == 2 or d1 == 2 Servant 3: drink if d0 == 3 or d1 == 3 Servant 4: drink if d0 == 4 or d1 == 4 At the end of the day, we will have at least 3 servants alive. (i.e. a maximum of 2 can die) We now have 3 cases, depending on how many actually died: - If no servants die, then d1 == 5, d2 == 5. It is barrel 55 (in base 6) - If servant N dies, then d1 == N, d2 == 5 or d1 == 5, d2 == N. (note that the maximum barrel number is 104, so we can't have confusion between 105 and 5). So we have only two possibilities to test, which is easy with 3 servants alive. - If servants N1 and N2 die, then d1 == N1, d2 == N2 or d1 == N2, d2 == N1. This gives us at most 4 possible barrels that could be poisoned [1,N1,N2], [1,N2,N1], [0,N1,N2], [0,N2,N1]. So at the end of day 1, we have at least 3 servants, and at most 4 possibilities to test for. Assign possibility 0, 1, 2 to remaining servants. If they all survive, then untested possibility is poisoned. Otherwise, it is obvious.
- 124816 16y ago
  Except 240 in base 10 in 1040 in base 6. (When moving to a lower base the number will always 'look' higher.)
  - TheNewAndy 16y ago
    Gah. Excellent maths by me :)
- transphenomenal 16y ago
  240(base10) == 1040(base6)
kang 16y ago
Call the slaves a,b,c,d,& e Each slave (5 - a,b,c,d,e) drinks from 16 barrels - 80. Each unique pair (10 - ab,ac,ad,ae,bc,bd,be,cd,ce,de) drinks from 8 barrels - 80. Each unique trio (10 - abc,abd,abe,acd,ace,ade,bcd,bce,bdc,cde) drinks from 4 barrels - 40. Each unique quartet (5 - abcd,abce,abde,acde,bcde) drinks from 2 barrels - 10. Everyone (5 - abcd) drinks from 1 barrel - 1. Nobody drinks from remaining 9 barrels - 9. If 1 slave dies we have 16 suspect barrels Each remaining slave (4), pair (6), trio (4) and quartet (1) drink from 1 barrel - 15 If 2 slaves die we have 8 suspect barrels Each remaining slave (3), pair (3), and trio (1) drink from 1 barrel - 7 If 3 slaves die we have 4 suspect barrels Each remaining slave (2), pair (1) drink from 1 barrel - 3 If 4 slaves die we have 2 suspect barrels The remaining slave drinks from 1 barrel If 5 slaves die we have a positive ID on the barrel If 0 slaves die we have 9 suspect barrels Each remaining slave (5) and 3 pairs drink from 1 barrel - 8
hristov 16y ago
Ok, this is my solution. This may end up similar to the algorithm 124816 proposed, but I am not sure I understood his solution. So I will give you mine. I arrived at my solution independently from 124816 although it does seem similar. You label each barrel of wine with a 5 digit binary label. "But wait," you say "5 digits in binary can only enumerate 32 barrels from 00000 (0) to 11111 (31)." You are right, but I did not say the labels were unique. There is only one barrel labeled 11111. For every barrel that has a label that has exactly one zero, there are two barrels carrying that label. This there are two barrels with the label 01111 and two more barrels labeled 10111, etc. For every label with exactly two zeros, there are four barrels having that same label. In general, if a label has n zeros (0<=n<=5) there are 2^n barrels having that same label. Now lets see how many barrels we can label using this scheme. There will be 2^5=32 barrels having the number 000000. For numbers with 4 zeros there are 5 possible labels and 16 barrels per label. 5x16=80. For barrels with 3 zeros, there are 5 choose 3 = 10 possible labels, and 2^3=8 barrels per label. 8x10 = 80 total barrels that can be labeled. For barrels with 2 zeros, there 5 choose 2 = 10 possible labels again with 4 barrels per label. 10x4= 40 barrels. And for barrels with one zero there are 5 possible labels with 2 barrels per label, which equals 10 barrels. As mentioned before there is only one barrel that is labeled 11111. So the grand total is 32+80+80+40+10+1=243 barrels. Thus we can label 243 barrels using the above described scheme. We label 240 barrels and throw away three labels. Now we get to the slaves. We number the slaves from 1 to 5. Each slave number will be a significant position in a binary barrel label number. We take the slaves to each barrel, and look at the label for the barrel. The slaves whose numbers correspond to significant positions which have "1" on the barrels label drink. The slaves who correspond to significant positions which have "0" on the label don't drink. Thus, a label "10011" means that slaves number 1, 2 and 5 drink. A label "00100" means that only slave number 3 drinks. After 24 hours we have 0-5 dead slaves. At this point we get a little sad and wonder why couldn't the problem have been worded in terms of rats, or something similar. But we keep on going; by the numbers of the dead slaves, we can determine which label is associated with the poisonous wine. The label with the poisonous wine is the one that has 1's in the positions associated with dead slaves. Thus if the first and second slave died, the poisonous label was 00011. If all slaves died, it kind of sucks for them, but we are in luck - that means the poisonous label was 11111 and there is only one barrel with this label, so we know which was the poisonous barrel. But if some slaves survived we will know the poisonous label but will have multiple barrels carrying this label. The number of slaves surviving will be equal to the number of zeros in the poisonous label. That is because the number of dead slaves is equal to the number of ones in the poisonous label. As discussed above, the number of barrels carrying any label is equal to 2^n where n is the number of zeros in the label. Thus, after 24 hours we are left with n slaves still living and 2^n barrels that are still suspicious (i.e., one of them is poisonous). If you have followed me thus far, solving this part will be trivial. We tear down the old labels and relabel the 2^n barrels with new n digit binary numbers. This time there is only one barrel per label. We also number the slaves from 1 to n to signify a significant position. We have each slave drink from each barrel that has a "1" in his significant position. And then we wait to see who dies. The poisonous barrel is the one whose label has "1" in every significant position associated with a dead slave. Well, this is it, I hope you enjoyed it, and yes I am brilliant.
ashishb4u 16y ago
First, i dont think its exact time. And, second if it was, imho why would anyone wait for 6mins?? Have the prisoner drink every second!!
ashishb4u 16y ago
Came up with a beautiful and elegant solution. Have a look: http://ashishlive.blogspot.com/2010/11/puzzle-poisoned-wine-fun-with-bases.html http://ashishlive.blogspot.com/2010/11/puzzle-poisoned-wine-... (quite detailed, believe me explaining the approach in words was hard.)

anatoly 16y ago

Yeah, "within 24 hours" doesn't mean "in exactly 24 hours". Edit: Here's my hint to those who have trouble solving this puzzle. Don't read it before trying to solve yourself! http://pastehtml.com/view/1c02p65.txt http://pastehtml.com/view/1c02p65.txt

124816 16y ago

> one dies within 24 hours Is it really correct to interpret that as "dies in exactly 24 hours"? Edit: My solution, which assumes that after tasting wine it could take any time between 0 and 24h to die; and that it could vary between tastings: Given N slaves, you can test 2^N wines in a single iteration, as so: - A set of size N has 2**N distinct sub-sets. - Have each distinct sub-set taste a different wine. - After 24h, everyone who drank the poisoned wine will be dead, and, provided you took notes about which set consumed which wine, you can look up which wine they drank. - (Note also, you leave one wine untasted; if nobody dies, it is the poisoned one.) For our first iteration, we have each set taste multiple wines, like so: - The set with five slaves will taste a single wine. - Sets with four slaves will taste 2 wines. - Sets with three slaves will taste 4 wines. - Sets with two slaves will taste 8 wines. - Sets with one slave will taste 16 wines. - We leave 32 wines untouched. Of course, in general: a set with N slaves will taste 2^(5 - N) wines. After 24 hours, all slaves who drank poisoned wine will be dead, and we will have the following possible states: - One slave is dead. We know the 16 wines he drank, and we have 4 slaves left. As shown above, we can easily determine which of the 16 wines is poisoned in a single iteration. - N slaves are dead. We know which 2**(5-N) wines they drank, and we have 5-N slaves left. So we can easily determine which of the 2**(5-N) wines is poisoned in a single iteration. Note that N = 0 is a valid case above. So, we need to calculate how many wines we can test in this manner. Going through each set: - 5 choose 1 * 16 = 80 - 5 choose 2 * 8 = 80 - 5 choose 3 * 4 = 40 - 5 choose 4 * 2 = 10 - The one wine that all slaves drink the first time. - The 32 wines none of them drink the second time. The sum is 243. Garçon!!! Fetch three more barrels!

jaekwon 16y ago
i got the same result.

TheNewAndy 16y ago

Note that it says the prisoner will die "within 24 hours". My solution (which looks somewhat correct, so don't read unless you want it spoiled) Day 0: Where all numbers are base 6 (240 in base 6 == 104) d0 = last digit of barrel number (in base 6) d1 = second last digit of barrel number (in base 6) Servant 0: drink if d0 == 0 or d1 == 0 Servant 1: drink if d0 == 1 or d1 == 1 Servant 2: drink if d0 == 2 or d1 == 2 Servant 3: drink if d0 == 3 or d1 == 3 Servant 4: drink if d0 == 4 or d1 == 4 At the end of the day, we will have at least 3 servants alive. (i.e. a maximum of 2 can die) We now have 3 cases, depending on how many actually died: - If no servants die, then d1 == 5, d2 == 5. It is barrel 55 (in base 6) - If servant N dies, then d1 == N, d2 == 5 or d1 == 5, d2 == N. (note that the maximum barrel number is 104, so we can't have confusion between 105 and 5). So we have only two possibilities to test, which is easy with 3 servants alive. - If servants N1 and N2 die, then d1 == N1, d2 == N2 or d1 == N2, d2 == N1. This gives us at most 4 possible barrels that could be poisoned [1,N1,N2], [1,N2,N1], [0,N1,N2], [0,N2,N1]. So at the end of day 1, we have at least 3 servants, and at most 4 possibilities to test for. Assign possibility 0, 1, 2 to remaining servants. If they all survive, then untested possibility is poisoned. Otherwise, it is obvious.

124816 16y ago
Except 240 in base 10 in 1040 in base 6. (When moving to a lower base the number will always 'look' higher.)
- TheNewAndy 16y ago
  Gah. Excellent maths by me :)
transphenomenal 16y ago
240(base10) == 1040(base6)

kang 16y ago

Call the slaves a,b,c,d,& e Each slave (5 - a,b,c,d,e) drinks from 16 barrels - 80. Each unique pair (10 - ab,ac,ad,ae,bc,bd,be,cd,ce,de) drinks from 8 barrels - 80. Each unique trio (10 - abc,abd,abe,acd,ace,ade,bcd,bce,bdc,cde) drinks from 4 barrels - 40. Each unique quartet (5 - abcd,abce,abde,acde,bcde) drinks from 2 barrels - 10. Everyone (5 - abcd) drinks from 1 barrel - 1. Nobody drinks from remaining 9 barrels - 9. If 1 slave dies we have 16 suspect barrels Each remaining slave (4), pair (6), trio (4) and quartet (1) drink from 1 barrel - 15 If 2 slaves die we have 8 suspect barrels Each remaining slave (3), pair (3), and trio (1) drink from 1 barrel - 7 If 3 slaves die we have 4 suspect barrels Each remaining slave (2), pair (1) drink from 1 barrel - 3 If 4 slaves die we have 2 suspect barrels The remaining slave drinks from 1 barrel If 5 slaves die we have a positive ID on the barrel If 0 slaves die we have 9 suspect barrels Each remaining slave (5) and 3 pairs drink from 1 barrel - 8

hristov 16y ago

Ok, this is my solution. This may end up similar to the algorithm 124816 proposed, but I am not sure I understood his solution. So I will give you mine. I arrived at my solution independently from 124816 although it does seem similar. You label each barrel of wine with a 5 digit binary label. "But wait," you say "5 digits in binary can only enumerate 32 barrels from 00000 (0) to 11111 (31)." You are right, but I did not say the labels were unique. There is only one barrel labeled 11111. For every barrel that has a label that has exactly one zero, there are two barrels carrying that label. This there are two barrels with the label 01111 and two more barrels labeled 10111, etc. For every label with exactly two zeros, there are four barrels having that same label. In general, if a label has n zeros (0<=n<=5) there are 2^n barrels having that same label. Now lets see how many barrels we can label using this scheme. There will be 2^5=32 barrels having the number 000000. For numbers with 4 zeros there are 5 possible labels and 16 barrels per label. 5x16=80. For barrels with 3 zeros, there are 5 choose 3 = 10 possible labels, and 2^3=8 barrels per label. 8x10 = 80 total barrels that can be labeled. For barrels with 2 zeros, there 5 choose 2 = 10 possible labels again with 4 barrels per label. 10x4= 40 barrels. And for barrels with one zero there are 5 possible labels with 2 barrels per label, which equals 10 barrels. As mentioned before there is only one barrel that is labeled 11111. So the grand total is 32+80+80+40+10+1=243 barrels. Thus we can label 243 barrels using the above described scheme. We label 240 barrels and throw away three labels. Now we get to the slaves. We number the slaves from 1 to 5. Each slave number will be a significant position in a binary barrel label number. We take the slaves to each barrel, and look at the label for the barrel. The slaves whose numbers correspond to significant positions which have "1" on the barrels label drink. The slaves who correspond to significant positions which have "0" on the label don't drink. Thus, a label "10011" means that slaves number 1, 2 and 5 drink. A label "00100" means that only slave number 3 drinks. After 24 hours we have 0-5 dead slaves. At this point we get a little sad and wonder why couldn't the problem have been worded in terms of rats, or something similar. But we keep on going; by the numbers of the dead slaves, we can determine which label is associated with the poisonous wine. The label with the poisonous wine is the one that has 1's in the positions associated with dead slaves. Thus if the first and second slave died, the poisonous label was 00011. If all slaves died, it kind of sucks for them, but we are in luck - that means the poisonous label was 11111 and there is only one barrel with this label, so we know which was the poisonous barrel. But if some slaves survived we will know the poisonous label but will have multiple barrels carrying this label. The number of slaves surviving will be equal to the number of zeros in the poisonous label. That is because the number of dead slaves is equal to the number of ones in the poisonous label. As discussed above, the number of barrels carrying any label is equal to 2^n where n is the number of zeros in the label. Thus, after 24 hours we are left with n slaves still living and 2^n barrels that are still suspicious (i.e., one of them is poisonous). If you have followed me thus far, solving this part will be trivial. We tear down the old labels and relabel the 2^n barrels with new n digit binary numbers. This time there is only one barrel per label. We also number the slaves from 1 to n to signify a significant position. We have each slave drink from each barrel that has a "1" in his significant position. And then we wait to see who dies. The poisonous barrel is the one whose label has "1" in every significant position associated with a dead slave. Well, this is it, I hope you enjoyed it, and yes I am brilliant.

ashishb4u 16y ago

First, i dont think its exact time. And, second if it was, imho why would anyone wait for 6mins?? Have the prisoner drink every second!!

ashishb4u 16y ago

Came up with a beautiful and elegant solution. Have a look: http://ashishlive.blogspot.com/2010/11/puzzle-poisoned-wine-fun-with-bases.html http://ashishlive.blogspot.com/2010/11/puzzle-poisoned-wine-... (quite detailed, believe me explaining the approach in words was hard.)