I slept late last night after 3 hours of playing Age Of Empires. I guess, as an after effect, I had a peculiar dream. I was a king in the land of Anubis, had 1000 knights at my command, and had recently won a fierce battle against the followers of Osiris. I had few war prisoners set for execution.
As a gift, Anubis had given me 1000 bottles of sacred water, directly from the source of the Nile. I had organized a grand event to honor the knights with the bottles. The event was to take place exactly after 24 hours, and Anubis himself was attending. So postponing the event was out of question.
Upon learning about the event, Osiris played a trick. He poisoned one of the bottles with a deadly poison, which had no smell or color. The poison, even in minutest amount was sure to kill a person, and once consumed, there was no antidote, not even with Anubis. And Anubis even refused to replace the bottles, saying he trusted me to take the right decision.
The poison took 10 to 20 hours to take effect. The life of any knight was too precious to throw away. Moreover, the prisoners were set for execution in the celebration, so killing them before was a loss, but could not be helped.
I was facing one of the most difficult problems a king should ever face. What was the minimum number of prisoners I could use as scapegoat to find out the poisoned bottle?
Well that’s the classic one. I would say 10.
Every prisoner can either live or die, so with n prisoners we can have 2^n different possibilities. 2^n >= 1000 implies n>=10.
Arrange the 10 prisoners in a line and give the ith prisoner a pinch of all the 1000 sacred water bottles for whose index ith bit is 1. Depending upon which prisoners die, we can get the bottle index.
I have to do something such that the solution is not public!!
Number of prisoners who would be used to detect the poison would be 10 but at the most 9 would die. Any better answer?
There is only one binary combination where all prisoners must sip from the wine. If there are ten prisoners then there are ten more combinations where all but one prisoner must sip from the wine. By avoiding these two types of combinations you can ensure no more than 8 prisoners die.
Make n number of prisoner stand in a row where 2^n >=1000, i.e. n = 10
number each bother from 1-1000. Change those numbers in the binary. See what all bits are 1 in binary representation of bottle. Give the water from the bottle to the prisoner who are at the bit numbers we noted earlier.
Do this for all the bottles.
After 20 hours some prisoner should die (if any of the bottle actually contained poison). Now using the index of the prisoner died we can reconstruct the number in binary and then subsequently in decimal.