Long time back, there was a wine lover King with a cellar of 1000 bottles of delightful and very expensive wine. A neighboring queen once planned to kill the wine lover King and sent a servant to poison the wine. Fortunately (or say unfortunately) the king’s guards caught the servant after he had only poisoned one bottle. Though the guards did’t know which bottle but knew that the poison was so strong that even if diluted 100,000 times it would still kill the king. Furthermore, it would take one month to have an effect. The king decided he would get some of the prisoners in his vast dungeons to drink the wine. Being a clever king he knews he only required to murder not more than 10 prisoners – which was not a high death rate by any means – and would still be able to drink the rest of the wine (999 bottles) at his anniversary party in 5 weeks time. Explain what was in mind of the king, how would he be able to do so ?
Think in terms of binary numbers.
Number the bottles from 1 to 1000 and write the numbers in binary format for each bottle.
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(first bit). Let prisoner 10 take a sip from every bottle with a 1 in its most significant bit(tenth 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
For instance, bottle no. 924 would be sipped by 10,9,8,5,4 and 3. That way if bottle no. 924 was the poisoned one, only those prisoners would die.
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.
Think in terms of binary numbers.
Number the bottles from 1 to 1000 and write the numbers in binary format for each bottle.
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(first bit). Let prisoner 10 take a sip from every bottle with a 1 in its most significant bit(tenth 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
For instance, bottle no. 924 would be sipped by 10,9,8,5,4 and 3. That way if bottle no. 924 was the poisoned one, only those prisoners would die.
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.
Long time back, there was a wine lover King with a cellar of 1000 bottles of delightful and very expensive wine. A neighboring queen once planned to kill the wine lover King and sent a servant to poison the wine. Fortunately (or say unfortunately) the king’s guards caught the servant after he had only poisoned one bottle. Though the guards did’t know which bottle but knew that the poison was so strong that even if diluted 100,000 times it would still kill the king. Furthermore, it would take one month to have an effect. The king decided he would get some of the prisoners in his vast dungeons to drink the wine. Being a clever king he knews he only required to murder not more than 10 prisoners – which was not a high death rate by any means – and would still be able to drink the rest of the wine (999 bottles) at his anniversary party in 5 weeks time. Explain what was in mind of the king, how would he be able to do so ?
|
Post Answer
Think in terms of binary numbers.
Reply 11Number the bottles from 1 to 1000 and write the numbers in binary format for each bottle.
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(first bit). Let prisoner 10 take a sip from every bottle with a 1 in its most significant bit(tenth 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
For instance, bottle no. 924 would be sipped by 10,9,8,5,4 and 3. That way if bottle no. 924 was the poisoned one, only those prisoners would die.
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.