|
So yesterday's puzzle is still kind of up in the air. Although initially it seems the game is not worth it (as the early replies indicated), I pointed out a strategy which may make the game worth it after all. Have a look, let me know if there's a mistake in the logic -- like I said I haven't solved it but I don't think it's as simple as it was first thought to be.
Moving on!
Today's puzzle:
You're gonna host a cheese & wine party and decided to stock up on wine. It's gonna be big, so you filled your cellar with 240 barrels of wine. Unfortunately, 48 hours before the party, someone tips you off that one of the barrels is poisoned. You decide to trick five of your servants into helping you figure out which is the poisoned barrel. If someone drinks from that barrel, they will die sometime in the next 24 hours. How do you find out which one is poisoned before the party starts?
Also note: you don't want to risk dying (durr) so only the 5 servants will be drinking.
Bonus: Could you have been able to stock up on more barrels and still be able to figure out which one's poisoned in 48 hours? What's the max # of barrels?
GL!
edit:minor wording changes
|
You can add 3 more barrels and still solve it. 243 is the max number.
|
On February 12 2010 02:32 MayorITC wrote:
You can add 3 more barrels and still solve it. 243 is the max number.
Yea, each element could be {0,1,2}... thats 3^5 = 243 possible combinations.
|
Well, let's look at this from a pure namespace argument.
The maximum information that a servant can give is 3-fold.
They can
1-die in the first 24 hours.
2-not die in the first 24 hours, but die in the next 24 hours.
3-Not die by the time of the party.
Thus we can represent all such possibilities with the following notation:
[1-3]*5
For example, we could have the string 13231 mean
servant 1 died in the 1st 24 hours.
2 lived.
3 died in 2nd 24 hours.
4 lived
5 died in the first 24 hours.
Thus we have a simple answer to the Bonus question:
the maximum possible information that can be gleaned from 5 servants is bounded by
n <= 243 (though it might be +- 1 cuz I haven't really considered the boundary condition thoroughly)
Now a mapping between our string system and guilty barrel will be constructed through a decision tree, with each servant eliminating 2/3 of the remaining barrels.
Servant 1 Tries barrels 1-80 in the first 24 hours. Tries barrels 81-160 in the 2nd 24 hours. If he does not die, we know the guilty barrel is in the 161-240.
Servant 2 then tries, 1-25:81-106:161-186 in first 24 hours, then 26-52.... for the 2nd 24 hours etc.
As long as each subsequent servant's choice kills ~2/3 of the remaining universes, we are good.
Thus we have created a sufficient mapping. yay!
So what do I win?
Edit:I guess I probably shouldn't win anything until I devise a more concise algorithm.
Let us number the barrels from
00000 to 22212. 22220, 22221, 22222 aren't valid.
We want to create a mapping so that the first servant's status informs the first digit 0-2, the 2nd servant, 0-2, etc....
All we have to do then, is to have servant 1 drink from barrels labelled 0xxxx in the first 24 hours. Barrels labeled 1xxxxx in the 2nd 24 hours, and barrels labelled 2xxxx will be implicated if he is not dead.
Thus each servant contributes a single digit to the trinary string and we can easily find which barrel is poisoned.
If servant 1 dies in the first 24 hours, servant 2 lives, servant 3 lives, servant 4 dies in the 2nd 24 hours, and servant 5 lives, we know the poisoned barrel is
02212
Or converted to decimal
2* 3^0 + 1*3^1 + 2*3^2+2*3^3 + 0*3^4= 2+3 + 18+54= Barrel # 77
|
I just finish lol, well done love, guess the game its over now 
|
First step is understanding possible combinations for each number of slaves.
5 - 32
4 - 16
3 - 8
2 - 4
1- 2
What that means is that as long as you have 5 slaves alive, you can figure single out the poisoned barrel out of 32; 4 slaves alive means you can single it out from 16, and so on and so on.
So you give each slave 16 separate barrels to drink. In the event that one slave dies, you have 4 remaining slaves to test it from that batch of 16 and single it out.
Anyway, that's 16 x 5 barrels covered so far which is 80. 240 - 80 = 160 remaining barrels.
Next up, you give each combination of two slaves 8 barrels of wine to test. There are a total of 10 possible pairs of slaves. In the event that a pair dies, you have 3 remaining slaves to test that batch of 8 and single out the poisoned barrel on day two. That's another 80 barrels covered.
160 - 80 = 80 barrels left.
Then you give each combination of 3 slaves (10 total), 4 barrels of wine to test. In the event, 3 slaves die you know it's going to be from one of the batch of 4 barrels and will have 2 remaining slaves to single it out on day two. That's another 40 barrels covered.
80 - 40 = 40 left
Then you give each combination of 4 slaves (5 combinations total) 2 barrels of wine to drink. In the event, four slaves die, you will have 1 slave to single out the poisoned one from the two barrels on day two. That's 10 barrels covered.
40 - 10 = 30
Then the last grouping is all five slaves testing one barrel. There's only one combination of five slaves. If all five slaves die, then you know the one they drank is the poisoned one. That's another barrel covered.
30 - 1 = 29 barrels left.
In the event that no slave dies, they can cover the remaining 29 since the max number of possible testing with 5 slaves is 32.
Therefore you have a leeway of 3 more barrels since 32 - 29 = 3
32 + 5 x 16 + 10 x 8 + 10 x 4 + 5 x 2 + 1 = 243.
I just read love's explanation and all I can say is WTF? Aside from his edit of his answer, which was originally 253, some of the things in it makes no sense.
Servant 1 Tries barrels 1-80 in the first 24 hours. Tries barrels 81-160 in the 2nd 24 hours. If he does not die, we know the guilty barrel is in the 161-240.
Where did you come up with this magic number that each slave has to test 2/3 of the barrels?
|
My edit more clearly and eloquently explains my solution. Once converted into trinary, it's much more straightforward to show that each must test (and therefore eliminate) 2/3 of the barrels. Clearly, from my mapping, you can see that each digit is 0-2, and 0 and 1 correspond to direct tests. Since exactly 1/3 of the entire space we are looking at has the nth digit as 0, and exactly 1/3 has the nth digit as 1, and exactly 1/3 has the nth digit as 2, it's clear as day why my initial proposition is true.
|
Okay, but from a non-technical-usage-of-unnecessary-bullshit-jargon point of view, unless your mapping follows a different set of mathematical axioms than the ones we use in this dimension, your logic is flawed. Under no circumstances, should a single slave ever test 80 barrels of wine like how you proposed.
Anyway, there's a limit to how much of your namespace crap I want to wade in, but if trying to impress people with garbage disguised with sophisticated terms gets you off, then continue by all means. I'm done.
|
Well, there's very little point in arguing when the point at hand is nonpolitical, but rather, unshakeable proveable fact. My algorithm stands shamelessly as is 
|
I'm confused.. MayorITC you realize your solution (which is exactly how I came to mine as well btw ) is pretty much the same as love1another's? In fact, if you add up all the barrels that each person tests, you will see they individually test 80 barrels each (excluding the 32 for the last day if nobody dies)
Not sure where the hostility comes from ^_^
edit: Just to expand on that..
Consider slave A drinks:
-from 16 during the "if 4 are left" phase - only 1 possibility there 16*1=16
-from 8 during the "if 3 are left" phase - where there are 4 possibilities 8*4=32
-from 4 during the "if 2 are left" phase - where there are 6 possibilities 4*6=24
-from 2 during the "if 1 is left" phase - where there are 4 possibilities 2*4=8
total = 16+32+24+8 = 80
in fact, you could say 81, if you count the case where all 5 drink from another barrel for the "if 0 are left" phase
|
On February 12 2010 02:44 love1another wrote:+ Show Spoiler +
Well, let's look at this from a pure namespace argument.
The maximum information that a servant can give is 3-fold.
They can
1-die in the first 24 hours.
2-not die in the first 24 hours, but die in the next 24 hours.
3-Not die by the time of the party.
Thus we can represent all such possibilities with the following notation:
[1-3]*5
For example, we could have the string 13231 mean
servant 1 died in the 1st 24 hours.
2 lived.
3 died in 2nd 24 hours.
4 lived
5 died in the first 24 hours.
Thus we have a simple answer to the Bonus question:
the maximum possible information that can be gleaned from 5 servants is bounded by
n <= 243 (though it might be +- 1 cuz I haven't really considered the boundary condition thoroughly)
Now a mapping between our string system and guilty barrel will be constructed through a decision tree, with each servant eliminating 2/3 of the remaining barrels.
Servant 1 Tries barrels 1-80 in the first 24 hours. Tries barrels 81-160 in the 2nd 24 hours. If he does not die, we know the guilty barrel is in the 161-240.
Servant 2 then tries, 1-25:81-106:161-186 in first 24 hours, then 26-52.... for the 2nd 24 hours etc.
As long as each subsequent servant's choice kills ~2/3 of the remaining universes, we are good.
Thus we have created a sufficient mapping. yay!
So what do I win?
Edit:I guess I probably shouldn't win anything until I devise a more concise algorithm.
Let us number the barrels from
00000 to 22212. 22220, 22221, 22222 aren't valid.
We want to create a mapping so that the first servant's status informs the first digit 0-2, the 2nd servant, 0-2, etc....
All we have to do then, is to have servant 1 drink from barrels labelled 0xxxx in the first 24 hours. Barrels labeled 1xxxxx in the 2nd 24 hours, and barrels labelled 2xxxx will be implicated if he is not dead.
Thus each servant contributes a single digit to the trinary string and we can easily find which barrel is poisoned.
If servant 1 dies in the first 24 hours, servant 2 lives, servant 3 lives, servant 4 dies in the 2nd 24 hours, and servant 5 lives, we know the poisoned barrel is
02212
Or converted to decimal
2* 3^0 + 1*3^1 + 2*3^2+2*3^3 + 0*3^4= 2+3 + 18+54= Barrel # 77
This.
It's just trinary
I think this question (to me at least) would be harder without the bonus
real edit:
I absolutely love the two different approaches proposed in this thread
I think the trinary approach is more rigorous in terms of maths/computer science/computational mathematics, whereas the other approach is more or less "intuitive".
|
|
|
|
|
|
|
|
|
|
|
|
EPT
