Interview Question
Country: India
Interview Type: Written Test
nc0 + nC1+ nC2 +............. nCn = 2^n =1000
n=10;
this nC0 is for the barrel drank by no one -only one such barrel
..
nC1 for barrel drank by 1 person each.... n such barells..
.
.it goes this way
Your answer is correct if the question was "Find out the minimum prisoners he would need to find out that barrel" - but the question was "Find out the maximum prisoners he would need to find out that barrel."
Maybe this is a trick question or maybe it was misworded, but the maximum is 1000 (1 prisoner per barrel) or n where n >= 1000 since the king has unlimited prisonrs.
People have posted the correct answer but so far I haven't seen a clear explanation of why it works.
Suppose we label the barrels with integers from 0 up to 1000. In binary such a label can be represented with 10 bits. In order to identify the poisoned barrel we need only find its label which in turn means finding the values of the label's 10 bits.
Let's start with bit 0, the least significant zero. We take a drop from each barrel whose 0th bit equals 0, i.e. the even-numbered barrels, and mix them together. We then have a prisoner drink the mixture. After 20 hours, if the prisoner is dead, we know that the poisoned barrel's 0th bit was 0; if the prisoner is alive, the poisoned barrel's 0th bit was not 0, hence it was 1, i.e. the poisoned barrel is odd-numbered.
Doing the same for the 9 other bits determines the label of the poisoned barrel uniquely. We don't wait for the first test to conclude before we begin the remaining tests; we begin them all concurrently, as soon as possible, given that we have 24 - 20 = 4 hours to prepare the 10 different mixtures.
By the way, the proof that this solution is optimal in terms of number of prisoners used is a standard information-theoretic argument and goes as follows: a test involving a single prisoner gives 1 bit of information (dead/alive) upon completion. Thus to identify 1 out of 1000 possibilities requires lg(1000) tests, which rounded up is 10.
10 is the correct answer. consider the following
nC0 + nC1 +... +nCn= 2 power n
So upto 1024 barrels can be covered using upto 10 prisoners.
Think it like this. 1 drop from each barrel to ten prisoners. Then 11th barrel will be for both 1st and 2nd prisoner. 12th for 3rd and 4th prisoner. If they both die then this 11th barrel was poisened one. Keep making such combinations for all the barrels and considering all these 10 prisoners.
10 is the correct answer. consider the following
nC0 + nC1 +... +nCn= 2 power n
So upto 1024 barrels can be covered using upto 10 prisoners.
Think it like this. 1 drop from each barrel to ten prisoners. Then 11th barrel will be for both 1st and 2nd prisoner. 12th for 3rd and 4th prisoner. If they both die then this 11th barrel was poisened one. Keep making such combinations for all the barrels and considering all these 10 prisoners.
In tha above solution he has mentioned that one drop from each barrel is added to all ten prisioner..... All of them would die...:)
31 in total?
I don't understand why "Covering 1000 to binary, which is 11,1110,1000. The length of the result is 10. So 10 prisoners should be enough to cover 1000 barrels of wine." Can someone help?
imagine all the prisoners in a line, each prisoner represents a binary digit. one would represent he did drink, and 0 would represent he didn't drink.
let's say we only had 4 barrels. then we would only need 2 prisoners.
barrel 1 feed to: 0 0 (no prisoner)
barrel 2 feed to: 0 1 (prisoner 2 only)
barrel 3 feed to: 1 0 (prisoner 1 only)
barrel 4 feed to: 1 1 (prisoner 1 and 2)
now you know that prisoners will die in a unique way, depending on which one had poison.
so now, in the question, let's say 11 1110 1000, or barrel 1000 had the poison. then exactly prisoner 1, 2, 3, 4, 5, 7 who drank barrel 1000 would die, and prisoner, 6, 8, 9, 10 who didn't drink barrel 1000 wouldn't die.
Well this problem can be converted into binary representation
say we need k bits to represent the 1000 prisoners.
Now , we know that only one bottle is poisoned.
So represent 1000 bottles using binary numbers of length k.
Posion bottle X will be represented as sequence of k bits ...
and we use k soldiers
so if 000100101 first every bit represents a person set bits say that soldier drank it
so , there will such unique combination for poisoned bottle
depending on who died we can determine the bottle
in worst case takes O(lg 1000)
-Yogesh Hande
Well this problem can be converted into binary representation
say we need k bits to represent the 1000 prisoners.
Now , we know that only one bottle is poisoned.
So represent 1000 bottles using binary numbers of length k.
Posion bottle X will be represented as sequence of k bits ...
and we use k soldiers
so if 000100101 first every bit represents a person set bits say that soldier drank it
so , there will such unique combination for poisoned bottle
depending on who died we can determine the bottle
in worst case takes O(lg 1000)
-Yogesh Hande
Well this problem can be converted into binary representation
say we need k bits to represent the 1000 prisoners.
Now , we know that only one bottle is poisoned.
So represent 1000 bottles using binary numbers of length k.
Posion bottle X will be represented as sequence of k bits ...
and we use k soldiers
so if 000100101 first every bit represents a person set bits say that soldier drank it
so , there will such unique combination for poisoned bottle
depending on who died we can determine the bottle
in worst case takes O(lg 1000)
-Yogesh Hande
Well this problem can be converted into binary representation
say we need k bits to represent the 1000 prisoners.
Now , we know that only one bottle is poisoned.
So represent 1000 bottles using binary numbers of length k.
Posion bottle X will be represented as sequence of k bits ...
and we use k soldiers
so if 000100101 first every bit represents a person set bits say that soldier drank it
so , there will such unique combination for poisoned bottle
depending on who died we can determine the bottle
in worst case takes O(lg 1000)
-Yogesh Hande
Well this problem can be converted into binary representation
say we need k bits to represent the 1000 prisoners.
Now , we know that only one bottle is poisoned.
So represent 1000 bottles using binary numbers of length k.
Posion bottle X will be represented as sequence of k bits ...
and we use k soldiers
so if 000100101 first every bit represents a person set bits say that soldier drank it
so , there will such unique combination for poisoned bottle
depending on who died we can determine the bottle
in worst case takes O(lg 1000)
-Yogesh Hande
9. Divide the bottles into 2 parts. first part consisting of 0th to 511th bottle. Obtain there binary conversion. Similarly number the remaining bottles i.e. 512th to 999th bottles and map them to 0th to 487th bottle, obtain there binary conversion and give them to the nine prisoners after 3 hours.
lets say we have eight barrels..
write the binary representation for then as
001 - only 3rd person dies
010 - only 2nd person dies
011 - both 2nd and 3rd dies
100 - only first dies
101 - both 1st and 3rd dies
110 - both 1st and 2nd dies
111 - all of them die
1 being the case that prisoner dies and 0 being the case that prisoner survives..
Now if give the wine in this way,
1st person gets 1,2,3,4 2nd person gets 3,4,5,6 and 3rd person gets 1,3,5,7, these conditions satisfies..
for instance, 001 only 3rd person dies, because he is the only one drinking from 7th barrel.. in this way you can check rest of the conditions..
I will explain in simple way first the answer is 10.
take 4 barrels:
----------------------------
prisoner1 prisoner2
barrel 1 barrel2
barrel 3 barrel3
Here if p1 dies then barrel1 is poisoned if p2 dies then barrel2 is poisned.if both p1 and p2 dies the barrel3 is poisned.if both survive then barrel4 is poisned
take 8 barrels:
-----------------------
prisoner1 prisoner2 prisoner3
b1 b2 b3
b4 b4
b5 b5
b6 b6
b7 b7 b7
mix wine in above combination.
if p1 dies then b1 is fault one
if p2 diels then b2 is fault one
if p3 dies then b3 is fault one
if p1 and p2 dies then b4 is fault one
if p2 and p3 dies then b5 is fault one
if p1 and p3 dies then b6 is fault one
if p1,p2,p3 all dies then b7 is fault one
if all survive then b8 is fault one
Lets give prisoners type as A,B and C.
Since there are 1000 barrels, divide them into set of 100 barrels and assign each prisoner(type A) a set of barrels to taste. So, they will be A1...10.
Now under each type A prisoners assign 10 prisoners of type B, So they will be number as B1..10 and each one of them will test 10 barrels. Now, under each type of B
Would this be cheating?
You can halve the prisoners.
They drink the first batch at hour zero. At hour 7 they drink the second batch. If the poison is in the first batch, one will die between 13 and 20 hours. If it's in the second batch, he can't die before hour 21. Of course that death might run 3 hours into the following day, but half the wine is already available for the party.
let's say you are identifying 4 barrels - you need two prisoners - you can mix the wine (or whatever it is) in such a way that either first prisoner dies, second prisoner dies, both die or none die, identifying the right barrel.
- stenlis February 23, 2012Let's say there are eight barrels. Let's number them 1 through 8. You need just three prisoners. First prisoner gets a mixture of 1, 2, 3, 4, second 3, 4, 5, 6 and third gets 1, 3, 5, 7. There are exactly eight combinations of the three prisoners dying or staying alive and with the above mixture each combination of the prisoner's deaths shows exactly which barrel was poisoned.
With 16 barrels you would need 4 prisoners.
The point is that with N prisoners you can 'encode' 2 to the N-th power barrels. With 1000 barrels you would need 10 prisoners.