(5 votes, average: 3.40 out of 5)A bad king has a cellar of 1000 bottles of delightful and very expensive wine. A neighboring queen plots to kill the bad king and sends a servant to poison the wine. Fortunately (or say unfortunately) the bad king’s guards catch the servant after he has only poisoned one bottle. Alas, the guards don’t know which bottle but know that the poison is so strong that even if diluted 100,000 times it would still kill the king. Furthermore, it takes one month to have an effect. The bad king decides he will get some of the prisoners in his vast dungeons to drink the wine. Being a clever bad king he knows he needs to murder no more than 10 prisoners – believing he can fob off such a low death rate – and will still be able to drink the rest of the wine (999 bottles) at his anniversary party in 5 weeks time. Explain what is in mind of the king, how will he be able to do so ? (of course he has less then 1000 prisoners in his prisons)
See Solution : King and wine bottlesNumber the bottles 1 to 1000 and write the number in binary format.
bottle 1 = 0000000001 (10 digit binary)
bottle 2 = 0000000010
bottle 500 = 0111110100
bottle 1000 = 1111101000
Now take 10 prisoners and number them 1 to 10, now let prisoner 1 take a sip from every bottle that has a 1 in its least significant bit. Let prisoner 10 take a sip from every bottle with a 1 in its most significant bit. etc.
prisoner = 10 9 8 7 6 5 4 3 2 1
bottle 924 = 1 1 1 0 0 1 1 1 0 0
After four weeks, line the prisoners up in their bit order and read each living prisoner as a 0 bit and each dead prisoner as a 1 bit. The number that you get is the bottle of wine that was poisoned.
1000 is less than 1024 (2^10). If there were 1024 or more bottles of wine it would take more than 10 prisoners.
using combination,
there are 10C0 ways of giving bottle to 0 prisoners
there are 10C1 ways of giving bottle to 1 prisoner
……………………………………………………………………….
there are 10 C 10 ways of giving bottle to 10 prisoners
Adding everything, there are 1024 possible unique combinations
Ridiculous..Binary system is very recent invention!
Better solution is to arrange the bottles in a matrix of 100×10 and get 100 prisoners to sip wine from all bottles of each of 100 rows and 10 prisoners to sip from all bottles of each of 10 columns.
This way only 2 prisoners will die, 1 from row sippers and 1 from column sippers. The intersection of these row and column will be the poisoned bottle.
Nice thinking.
Though in binary solution, king can do it with only 10 prisoners with probability of all of them dying.
In your solution, king will need 110 prisoners with surety of 2 prisoners dying.
Matrix can also be of 50×20. This way we only need 70 prisoners and only 2 will die.
32×32 and 2 will die is better than 10×100 or 20×50.
But a 3D matrix of 10x10x10 is also possible, and exactly 3 of them will die. Or 6x6x6x5 and at most 4 will die, and so on, as you increase the dimensions (5 groups of 4 and at most 5 will die, 3x3x3x3x4x4 with at most 6 death, 2x2x3x3x3x3x3 and 7, etc.).
Actually, as in the example solution, you can always ommit one prisoner per group, because it’s also an information that noone of the others died. So the 7D-example would need 2×1+5×2=12 prisoner with 7 death at most, and 15 prisoner in 5D and at most 5 death, which possibilities are close enough to the original 10 prisoner but each of them have (almost) 50% to die.
How do you come up with the right dimension? In the above example, is 7D the most optimal? Why not 8? I also haven’t understood why one prisoner per group should be excluded. Can you please elaborate?
You need 10 prisoners to determine which one is poisonous, but you can guarantee that a maximum of 8 will die. I’m curios if anyone can explain why?
through the concept of 2^n….i hope you will have undestood
Among the 1024 different 10-binary digit numbers there are more than 1000 which have less than 9 ‘one’-s. You will number the bottles with 0,1,2, …, 510, 512,513,…, 766, 768,769,…, 894, 896,897,…,958, 960,961,…,990, 992,993,…,1004.
You mean a maximum of 9?
“read each living prisoner as a 0 bit and each dead prisoner as a 1
bit.” This is confusing. How can you be sure that dead prisoner belongs
to 1 bit? I think I have not understood the last line. But the problem
is amazing. Hats off. Will appreciate if you make the last line more
clear.
I am thinking that if I know that 10,9,8,5,4,3 are dead then
I can make the Number and can get the bottle number. Why to assume dead
as 1 and living as 0?
Each prisoner represents a bit in what would turn out later to be the bottle number.
A prisoner which represents the bit 0 would consume from a bottle only if the bottle’s binary representation has 1 in it.
Since all the prisoners who die would have consumed from the poisoned bottle. Their bit, when represented as 1, would give us the poisoned bottle’s number.
Eg. If the 10th bottle is poisned – 00001010
Then the prisoner 2nd and the 4th from the right would consume from it and others would not and would also die. So when you represent the dead prisoners as 1 and others as 0 you would get the bottle’s binary representation.
Assumption – Prisoners drink all the wine they are supposed to and dont pass out after drinking too much wine!
Cheers!
Amazing!!!