**A king has 1000 bottles of wines and some one has mixed poison in one bottle. Now how will the king find that poisoned bottle?**

**Given:**

**He has lots of prisoners to test.****The poison takes 4 weeks to have effect. i.e. A Prisoner taking wine from the poisonous bottle would die after 4 weeks.**

**Possible Solution:**

All the bottles are marked with numbers from 1 to 1000. You can get the binary representation of all the number.

So bottle 1=0000000001

bottle 1000=1111101000

Now you need 10 prisoners. Prisoners one will take a sip from the bottle which has 1 in the last significant bit and so on. So bottle 1000 ill be tried on prisoners 4, 6, 7, 8, 9 and 10. The king can get back the number of bottle by keeping all the dead and alive prisoners according to their number, assigning 1 to dead, 0 to alive prisoners and calculate the number of bottle.

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.

So bottle 1=0000000001

bottle 1000=1111101000

Now you need 10 prisoners. Prisoners one will take a sip from the bottle which has 1 in the last significant bit and so on. So bottle 1000 ill be tried on prisoners 4, 6, 7, 8, 9 and 10. The king can get back the number of bottle by keeping all the dead and alive prisoners according to their number, assigning 1 to dead, 0 to alive prisoners and calculate the number of bottle.

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.

## 0 comments:

## Post a Comment