12 replies to this topic

[ujjagrawal]

There's a merciless emperor who has 500 bottles of very expensive wine in his cellar.

An assassin infiltrates the wine cellar to poison the wine. Fortunately the emperor’s guards catch the plotter after she has poisoned only one bottle. Unfortunately, the guards don’t know which one of the bottles is poisoned.

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

The emperor decides he will get some of the prisoners in his dungeons to test the wine as he has handful of them about to be executed.

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

[bonanova]

Spoiler for first guess

I'm thinking the search can be partitioned in a hierarchical binary fashion.
Since 1000 is almost, but less than, 2¹⁰, I'll throw 10 out as a first guess.

Now to formalize it.

Edit:
Number the wines in binary. Ten bits are sufficient.
Assign each of ten prisoners a bit, sipping the bottles that have a 1 in that place.
The ones who die spell out in binary the number of the poisoned bottle.

[David_Walker]

Spoiler for My thoughts...

You'd have to make sure you waited 20 hours to see the results (as if you waited 10 hours and it was a 20 hour dose of poison, you cannot be completely sure). And to test all the 500 bottles within 24 hours, you would need 499 people. Then, if they all survived, you'd know the leftover bottle is poisoned.

[jim]

bonanova would be correct if there were 1000 bottles.

[MikeD]

Spoiler for my try

The emperor would only need nine prisoners.

First each one if given one bottle to taste

Then each prisoner is pair up a number of times and each pair is given a bottle to try. (1&2 1&3 1&4 1&5 1&6 1&7 1&8 1&9 2&3 2&4...)

Then the prisoners are group in three's, four's five's six's, seven's, eight's and even nine's(ie they all try one bottle)

Then we wait 20 hours and see who dies.

If only three prisoners die then we know its form one of the bottle tried when the prisoners were group in three's and based on who die the poisoned wine can be
ID.

(of cause there could have been 512 bottles to try.)

[bonanova]

bonanova would be correct if there were 1000 bottles.

Being an engineer and not a mathematician, I built in some redundancy.
And next puzzle I solve, I'll wear my glasses.

[TheChad08]

Spoiler for my try

The emperor would only need nine prisoners.

First each one if given one bottle to taste

Then each prisoner is pair up a number of times and each pair is given a bottle to try. (1&2 1&3 1&4 1&5 1&6 1&7 1&8 1&9 2&3 2&4...)

Then the prisoners are group in three's, four's five's six's, seven's, eight's and even nine's(ie they all try one bottle)

Then we wait 20 hours and see who dies.

If only three prisoners die then we know its form one of the bottle tried when the prisoners were group in three's and based on who die the poisoned wine can be
ID.

(of cause there could have been 512 bottles to try.)

Spoiler for

Here's a simpler way of saying what he said. 9 slaves, if all 9 are in one group, that's 1 possibility.
Therefore one bottle tested.
For all 9, that's 1 bottle.
9 choose 8 = 9
9 choose 7 = 36
9 choose 6 = 84
9 choose 5 = 126
9 choose 4 = 126
9 choose 3 = 84
9 choose 2 = 36
9 choose 1 = 9

That's 510 possibilties.
511 total possibilities if you consider that all 9 could avoid drinking one bottle.

Edited by TheChad08, 26 July 2012 - 04:31 PM.

[MikeD]

Spoiler for

Here's a simpler way of saying what he said. 9 slaves, if all 9 are in one group, that's 1 possibility.
Therefore one bottle tested.
For all 9, that's 1 bottle.
9 choose 8 = 9
9 choose 7 = 36
9 choose 6 = 84
9 choose 5 = 126
9 choose 4 = 126
9 choose 3 = 84
9 choose 2 = 36
9 choose 1 = 9

That's 510 possibilties.
511 total possibilities if you consider that all 9 could avoid drinking one bottle.

I think you missed one, 511 bottles were tested, leaving one remaining one. So 512 bottle could have been tested.

[TheChad08]

I think you missed one, 511 bottles were tested, leaving one remaining one. So 512 bottle could have been tested.

You're right.
I didn't add the 9 choose 9.

My bad.
It is 512.

You're still right, I just tried to show it in a less convoluted way.

[jim]

bonanova As a math teacher I considered your solution to be correct except for one minor detail. As far as I am concerned you are the one who solved the problem.