- Prepare
All Platforms Programming Aptitude Syllabus Interview Preparation Interview Exp. Off Campus - Prime Video
- Prime Mock

- Interview Experience
- Prime VideoNew
- Prime Mock
- Discussion Forum
- Nano Degree
- Prime Video
- Prime Mock

# King & Wine Bottle Puzzle

## King & Wine Bottle Puzzle

The poison exhibits no symptoms until death. Death occurs within ten to twenty hours after consuming even the minutest amount of poison.

You have over a thousand slaves at your disposal and just under 24 hours to determine which single bottle is poisoned.

You have a handful of prisoners about to be executed, and it would mar your celebration to have anyone else killed.

What is the smallest number of prisoners you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?

king and poisioned wine puzzle

## Solution

**Solution:**

In the above image we can explain that,

To test 10 bottle we need only 3 Prisoners because by using 3 prisoners there will be total of 8 possibility i.e., 2^{3}

So if we go by case to case we can see that:

**Case 1:** If all the 3 prisoners live than all the bottles are safe.

**Case 2:** If only A dies than only bottle 2 is poisoned.

**Case 3:** If only B dies, then bottle 3 is poisoned.

**Case 4:** If only C dies, than bottle 5 is poisoned.

**Case 5:** If both A & B dies, then bottle 4 is poisoned.

**Case 6:** If A & C dies, than bottle 6 is poisoned

**Case 7:** If B & C dies, than bottle 7 is poisoned.

**Case 8:** If all three i.e., A, B, and C dies, than bottle 8 is poisoned.

Hence we can conclude that by using 3 prisoners we can find the defective bottle within 8.

Thus, by using only 10 Prisoners, we can find the poisoned bottle among all the 1000 ones as possibility after using 10 prisoners will be 2^{10} = 1024, and there are only 1000 bottles.

**Alternate method:**

Number the bottles 1 to 1000, and write the number in binary format.**bottle 1** = 0000000001**bottle 250** = 0011111010**bottle 1000** = 1111101000

Now take your prisoner’s 1 through 10

and

Let prisoner 1 take a sip from every bottle that has a 1 in its least significant bit.

Let prisoner 10 take a sip from every bottle with a 1 in its most significant bit. etc.

**Prisoner** – 10 9 8 7 6 5 4 3 2 1**Bottle 924** – 1 1 1 0 0 1 1 1 0 0

In this, bottle #924 would be sipped by 10,9,8,5,4 and 3

That way if bottle #924 was the poisoned one, only those prisoners would die.

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.

Login/Signup to comment