An enemy spy has poisoned one out of 1000 barrels of wine in a king’s cellar. Even a sip of the poisoned wine has potency to kill. However, the effects of the poison show only in 30 days. The king asks the royal jailor to identify the poisoned barrel within 30 days. What is the least number of prisoners the jailor must employ to identify the poisoned barrel
Source : http://gurmeetsingh.wordpress.com/2008/09/12/puzzle-poisoned-wine-barrels/
 
|
|
 
|
Subscribe to:
Post Comments (Atom)
1 comment:
Short Answer :
2^n bottles can be tested using 'n' prisoners
For 1000 bottles, we will need 10 prisoners
Long answer :
Suren helped me with this. Lets divide and conqer and work our way other way up.
Q1. Say we had one prisoner, how many bottles could we test?
A1. 2. Here are the combinations we will have :
P1 drinks B1
Q2. Say we had two prisoners, how many bottles could we test?
A3. 4. Here are the combinations we will have :
P1 drinks B1
P2 drinks B2
P1 and P2 both drink B3
Q3. Say we had three prisoners, how many bottles could we test?
A3. 8. Here are the combinations we will have :
P1 drinks B1
P2 drinks B2
P3 drinks B3
P1 and P2 both drink B4
P1 and P3 both drink B5
P2 and P3 both drink B6
P1, P2 and P3 all drink B7
The pattern :
We need to form combinations of how many bottels can be arranged (drunk) amogsts the prisoners. First we make a group of '1' prisoner each, then for '2' prisoners, then '3' and so on. Each group drinks a unique bottle. Also, there is one bottle that no one drinks. Hence, when one or more prisoner dies we know exactly which group(s) he belonged to and can identify which bottle is the poisonous one. If none of them die, the last bottle (which no one drank) is the poisonous one.
What this means that we need to solve this equation
nC1 + nC2 + nC3 + .... nCn
to find the number of bottles 'n' prisoners can test. This series has been proved to be equal to 2^n (http://www.themathpage.com/aprecalc/permutations-combinations-2.htm#sum)
Hence, number of prisoners to test 'x' bottles is lg(x) (base 2)
Post a Comment