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

combinationswe will have :P1 drinks B1

Q2. Say we had two prisoners, how many bottles could we test?

A3. 4. Here are the

combinationswe 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

combinationswe 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

combinationsof 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