1000 bottles of wine, one poisoned

♠ Posted by GeekyFry in , at 10:12 AM

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.

0 comments:

Post a Comment