This is very similar to a problem is creating reliable computer communications - parity bits. How many bits do you need to identify and correct a single error in a 1000 bit message - the answer is the same as in this problem.
Number of testers needed:
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.
Could be solved by binary search method,though almost same approach but looks very straightforward,emperor should order his slaves to take a drop from each bottle,mix 500-500 drops seperately initialy wait for 20 minutes 1 would die of the two groups.Further take drops in two groups 250 drops each, in another 20 min again prisoner would die,proceed in the similiar fashion.After at max death of 10 prisoners ,bottle will be identified.Since there are thosands of slaves and 24 hours of time, time constraint would not be voilated.
I got the answer in one go! HORRAY!! I thought of the answer in like 2 minutes not including the reading time!! Isn't that cool! But the answer to this question is pretty hard to solve. You must understand alot of things! But I really like logical problems, it's really fun to play with. Especially the ones that are very hard! Hope there are harder problems for me to sovle!
Signed: Devine Girl
PS. Good luck to the ones that are doing this problem! ^_^
The answer is wrong - less than 10 are needed!
A guy showed me how 5 prisoners can examine all of the 1000 bottles in 16 hours and be enough in number to show which one is poisoned. I extended his logic and claim that only 4 (four) prisoners are needed to sample up to 4096 bottles within 24 hours.
Proof: (a little bit difficult for understanding)
The prisoners will drink wine in 0:00, 2:00, 4:00, 6:00, 8:00, 10:00 and 12:00 - 7 times, lets call them "rounds". Following this schedule we will be sure, that the result of each sampling will be available before 24:00. We will use a small trick - from one of the bottles no one will drink, lets label it "bottle 0".
Here comes the difficult part: lets label each bottle with the octal representation of its number (beginning with 0 and leaving the leading zeros). Our "bottle 0" will have now label "0000" and the 1000th bottle will have label "1747". We "assign" each of the 4 prisoners to a position in the labels - the first to position 1, the second to position 2, etc. The rule of drinking is this: Prisoner number N (N is 1 to 4) will drink from the bottles, that have the current "round" in "his position" in their labels. For example at 2:00 (2nd round) prisoner number 3 will drink from all the bottles that have label "XX2X", at 4:00 (3rd round) he will drink from all the bottles labeled "XX3X", etc. If the number in "his position" is zero he does not drink from the bottle! As you can see from bottle "0000" no one will drink.
Using this technique we can provide unique combination of drinking (and time gaps) for 8^4 = 4096 bottles and this is the correct answer of the problem. :)
Lets see a sample result - prisoner 1 dies at 12:02, prisoner 2 dis at 19:30, prisoner 3 dies at 16:35 and prisoner 4 remains alive after 24 hours. So prisoner 1 has died from the bottles that he tasted at 0:00 (1st round), prisoner 2 - from bottles at 8:00 (5th round), prisoner 3 - from bottles at 6:00 (4th round). The label of the poisonous bottle will have "1" at its first position, "5" at second, "4" at third and "0" at fourth (prisoner 4 did not die from it because it has zero at "his position"). The octal representation of the bottle's number is thus 1540, which is the decimal number 864. The 864th bottle is poisonous :)
The 865th bottle is poisonous. I forgot that we started from 0 not from 1 :)
One addition - prisoner will have 51.2% chance to stay alive, prisoners 2 and 3 - 12.8% and prisoner 4 - 12.5%. From "0000" to "1747" there 512 zeros at first position, 128 zeros at 2nd and 3rd position and 125 zeros at 4th position.
You only half to risk a 50/50 chance for one prisoner if you take half the bottles ands mix them. Then make one prisoner drink it and if he dies you use the other half of bottles and if he dosent die you know that your big ass tub of wine isent poisoned
o man i am ashamed of myself, i am a EE major and i should have gotten this, and on a test today i was asked a similar question too. it was about precision and number of bits, o well, good stuff.
and for anyone else that doesnt understand it still, basically if only one prisoner dies then you look at which bottle they drank and if multiple prisoners die you look at the bottle that all of them drank
i think i,ve a better solution for this problem.... 3 persons can be chosen from 24 persons in 2024 different ways... we can take any 1000 of the 2024 combinations and ask them to have a sip from 1000 bottles.. a bottle for each group... finally the group in which all three members die has consumed the poissoned bottle.. by doing this we kill only 3 slaves
It is stated in the solution that there is one binary combination in which all ten prisoners must sip the wine, and ten combinations in which all but one (nine) prisoners must drink. Well, technically that's true. However, assuming we start with one or 0000000001 (which we must since nobody drinks/nobody dies tells us squat), the combination where all ten drink would be 1111111111, which would be the 1,023rd bottle. It wouldn't even come up. Also, of the ten combinations requiring nine prisoners to drink, only five would come up because 1111101111, 1111110111, 1111111011, 1111111101 and 1111111110 would represent the 1,007th, 1,015th, 1,019th, 1,021st and the 1,022nd bottles, respectively. They would never come up either. Only five of the nine-prisoner combinations would arise: 0111111111 (511th), 1011111111 (767th), 1101111111 (895th), 1110111111 (959th) and 1111011111 (991st). So we would only need to skip those five combinations and replace them with the as yet unused combinations corresponding to the numbers 1,001 through 1,005: 1111101001, 1111101010, 1111101011, 1111101100, and 1111101101.
Very good puzzle, thx G.R for explaining how to make sure only 8 people will die in the worst combination. I understood that bit only from your explanation!
01 PRISONER DRINKS FROM IST BOTTLE AND FROM 2ND NEXT SECOND AND FROM THIRD BOTTLE THE 3RD SECOND ... TILL 999TH BOTTLE.
AT THE SAME TIME , The 02 prisoner starts from 1000th bottle in reverse order every second till the 2nd bottle.
See, the time of death of 01 and 02nd prisoner/ prisoners will be unique for any particular poisoined bottle.
2(n) >= 1000 so n >= 10. based on total count of a set's subset is 2(n). For example, if 8 bottle wines, at least 3 prisoners need to die. A 3 set{a, b, c} has a total 8 subset including the empty set. That is{}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}. Each subset correspondences to a bootle of wine. we know which subset of prisoner die, we know which bottle of wine is poisoned.
RE: if you assign 1 bottle per slave and each takes a tiny sip, the one who dies after 10-20 hours must have drank from the poisoned bottle.
#21 - Paul - 07/31/2008 - 08:48
I thought the exact same thing but then realised that you have 1000 slaves at your disposal, but only a handful of prisoners. It would mar your celebrations if you killed anyone else.
I dont think you can kill the slaves, only the prisoners. That and this puzzle is in the "very difficult" section =)
The puzzle asks for SMALLEST possible number of prisoners to involve in test drink. What would be the solution if the king want to keep the number of deaths at a minimum, even if that means using some more test-drinkers within those handful of prisoners keeping all other things same?
In other words, KEEPING the number of prisoners is much less the figure of 1000, (say, upto 100) and you can use as many as you want among these; what would be the SMALLEST possible number of deaths to figure out the poisoined bottle, keeping all other things same.
Also It would be fine if we set the hours in which one die after getting poisened. lets set it ~20 hrs. It would be interesting to find the correlation between the number of prisoners user v/s deaths.
Well, for one thing you could get rid of the wine and give the guests water. Not as festive, but still.
Or you could postpone the party and order new wine.
Or (my personal favorite) you could make the guy who gave you the wine tell you which one was poisoned. After all, this is the middle ages. The bottles won't be identical and the guy could probably tell which one he had poisoned. Then make him drink from it for spoiling your party.
999 of the slaves, starting with the handful of those to be executed, take a sip of 999 bottles. If none die its the one remaining bottle that is poisoned. But if someone drinks the poison the king replaces the dead slave with one of the handful who is to be executed if one of the handful has not drank from the poisoned bottle so we have no problem with the party. Solved. One slave dies. One king doesn't.
I'd like to amend the above brilliant solution. Not one prisoner drinks from a bottle if in fact a minute portion of each bottle is poured into a glass first.
That's a great solution. But there's one problem. If the slave is killed and replaced with a prisoner, then think about it. He's sentenced to be killed. Who knows what he'll try to do? He could kill someone, which would really spoil the party. It would be better to replace the slave with another slave, and then go on as if nothing happens. After all, you have more than a thousand slaves. You can replace #999, for example, with #1001 and be fine. Unless you need al those slaves in a certain place. In that case, use the prisoner. But have someone with a crossbow watching him the whole time
You need 10 slaves and the explanation.
10 slaves each drink 110, if one slave dies then the other 990 bottles are good and if two slaves die then the 10 that the bottle that they drunk that was identical is the one. out of the the 10 bottles leftover each of the 9 remaining slaves drink 1 and then if one dies thats the bottle.
This was a hard problem if you tried doing some sort of statistical analysis and didn't have all the facts straight. A lot of people didn't read the question very well.
I got the answer in about 10 seconds. No I'm not awesome, it was a guess. But I laughed.
01 PRISONER DRINKS FROM IST BOTTLE AND FROM 2ND NEXT SECOND AND FROM THIRD BOTTLE THE 3RD SECOND ... TILL 999TH BOTTLE.
AT THE SAME TIME , The 02 prisoner starts from 1000th bottle in reverse order every second till the 2nd bottle.
See, the time of death of 01 and 02nd prisoner/ prisoners will be unique for any particular poisoined bottle.
=>only 01 prisoner dies if the poison is in 1st or 1000th bottle
=>02 prisoner dies in case of any other bottle
ITS 10 PRISONERS , MAN.
10 PRISONERS CAN BE SET INTO UNIQUE 1023 DIFFERENT GROUPS.( CONSISTING OF GROUPS OF 1,2,3...., 10 DIFFERENT PRISONERS). MAKE LIST OF ALL THE 1023 COMBINATION AND MAKE EACH COMBINATION DRINK FROM EACH BOTTLE. THE PRISONER COMBINATION DYING WILL POINT OUT THE PARTICULAR POISONED WINE BOTTLE. SO MINIMUM 10 PRISONERS ARE REQUIRED TO DRINK WINE.
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.
Signed: Devine Girl
PS. Good luck to the ones that are doing this problem! ^_^
If there are two poisoned bottles, what is the minimum number of slaves required to locate them within 24 hours?
A generalized case: If there are n (n>2) poisoned bottles, what is the number?
A guy showed me how 5 prisoners can examine all of the 1000 bottles in 16 hours and be enough in number to show which one is poisoned. I extended his logic and claim that only 4 (four) prisoners are needed to sample up to 4096 bottles within 24 hours.
Proof: (a little bit difficult for understanding)
The prisoners will drink wine in 0:00, 2:00, 4:00, 6:00, 8:00, 10:00 and 12:00 - 7 times, lets call them "rounds". Following this schedule we will be sure, that the result of each sampling will be available before 24:00. We will use a small trick - from one of the bottles no one will drink, lets label it "bottle 0".
Here comes the difficult part: lets label each bottle with the octal representation of its number (beginning with 0 and leaving the leading zeros). Our "bottle 0" will have now label "0000" and the 1000th bottle will have label "1747". We "assign" each of the 4 prisoners to a position in the labels - the first to position 1, the second to position 2, etc. The rule of drinking is this: Prisoner number N (N is 1 to 4) will drink from the bottles, that have the current "round" in "his position" in their labels. For example at 2:00 (2nd round) prisoner number 3 will drink from all the bottles that have label "XX2X", at 4:00 (3rd round) he will drink from all the bottles labeled "XX3X", etc. If the number in "his position" is zero he does not drink from the bottle! As you can see from bottle "0000" no one will drink.
Using this technique we can provide unique combination of drinking (and time gaps) for 8^4 = 4096 bottles and this is the correct answer of the problem. :)
Lets see a sample result - prisoner 1 dies at 12:02, prisoner 2 dis at 19:30, prisoner 3 dies at 16:35 and prisoner 4 remains alive after 24 hours. So prisoner 1 has died from the bottles that he tasted at 0:00 (1st round), prisoner 2 - from bottles at 8:00 (5th round), prisoner 3 - from bottles at 6:00 (4th round). The label of the poisonous bottle will have "1" at its first position, "5" at second, "4" at third and "0" at fourth (prisoner 4 did not die from it because it has zero at "his position"). The octal representation of the bottle's number is thus 1540, which is the decimal number 864. The 864th bottle is poisonous :)
One addition - prisoner will have 51.2% chance to stay alive, prisoners 2 and 3 - 12.8% and prisoner 4 - 12.5%. From "0000" to "1747" there 512 zeros at first position, 128 zeros at 2nd and 3rd position and 125 zeros at 4th position.
and for anyone else that doesnt understand it still, basically if only one prisoner dies then you look at which bottle they drank and if multiple prisoners die you look at the bottle that all of them drank
It is stated in the solution that there is one binary combination in which all ten prisoners must sip the wine, and ten combinations in which all but one (nine) prisoners must drink. Well, technically that's true. However, assuming we start with one or 0000000001 (which we must since nobody drinks/nobody dies tells us squat), the combination where all ten drink would be 1111111111, which would be the 1,023rd bottle. It wouldn't even come up. Also, of the ten combinations requiring nine prisoners to drink, only five would come up because 1111101111, 1111110111, 1111111011, 1111111101 and 1111111110 would represent the 1,007th, 1,015th, 1,019th, 1,021st and the 1,022nd bottles, respectively. They would never come up either. Only five of the nine-prisoner combinations would arise: 0111111111 (511th), 1011111111 (767th), 1101111111 (895th), 1110111111 (959th) and 1111011111 (991st). So we would only need to skip those five combinations and replace them with the as yet unused combinations corresponding to the numbers 1,001 through 1,005: 1111101001, 1111101010, 1111101011, 1111101100, and 1111101101.
Then exactly one prisoner is sacrificed.
What in the problem statement disallows this?
AT THE SAME TIME , The 02 prisoner starts from 1000th bottle in reverse order every second till the 2nd bottle.
See, the time of death of 01 and 02nd prisoner/ prisoners will be unique for any particular poisoined bottle.
: )
#21 - Paul - 07/31/2008 - 08:48
I thought the exact same thing but then realised that you have 1000 slaves at your disposal, but only a handful of prisoners. It would mar your celebrations if you killed anyone else.
I dont think you can kill the slaves, only the prisoners. That and this puzzle is in the "very difficult" section =)
In other words, KEEPING the number of prisoners is much less the figure of 1000, (say, upto 100) and you can use as many as you want among these; what would be the SMALLEST possible number of deaths to figure out the poisoined bottle, keeping all other things same.
Also It would be fine if we set the hours in which one die after getting poisened. lets set it ~20 hrs. It would be interesting to find the correlation between the number of prisoners user v/s deaths.
Or you could postpone the party and order new wine.
Or (my personal favorite) you could make the guy who gave you the wine tell you which one was poisoned. After all, this is the middle ages. The bottles won't be identical and the guy could probably tell which one he had poisoned. Then make him drink from it for spoiling your party.
10 slaves each drink 110, if one slave dies then the other 990 bottles are good and if two slaves die then the 10 that the bottle that they drunk that was identical is the one. out of the the 10 bottles leftover each of the 9 remaining slaves drink 1 and then if one dies thats the bottle.
I got the answer in about 10 seconds. No I'm not awesome, it was a guess. But I laughed.
sliver are able to detect poison
it is even faster than using persioner and wait a min 10 hrs
which is a waste of time.
AT THE SAME TIME , The 02 prisoner starts from 1000th bottle in reverse order every second till the 2nd bottle.
See, the time of death of 01 and 02nd prisoner/ prisoners will be unique for any particular poisoined bottle.
=>only 01 prisoner dies if the poison is in 1st or 1000th bottle
=>02 prisoner dies in case of any other bottle
10 PRISONERS CAN BE SET INTO UNIQUE 1023 DIFFERENT GROUPS.( CONSISTING OF GROUPS OF 1,2,3...., 10 DIFFERENT PRISONERS). MAKE LIST OF ALL THE 1023 COMBINATION AND MAKE EACH COMBINATION DRINK FROM EACH BOTTLE. THE PRISONER COMBINATION DYING WILL POINT OUT THE PARTICULAR POISONED WINE BOTTLE. SO MINIMUM 10 PRISONERS ARE REQUIRED TO DRINK WINE.