The rich man and the 1000 casks of wine

Question

I recently came across an interesting logic puzzle during a challenge at a programming competition. Neither of the people on the two-person team completing that challenge could figure out an answer that worked in every scenario, and neither could the other people on the school team.

The problem was described as follows:

You are a rich and unscrupulous man who owns ten slaves. You are hosting a large dinner party in six hours at which you intend to serve one thousand casks of wine.

Unfortunately, exactly one of the casks is poisoned. You know the poison takes effect between 30 minutes and five hours after ingestion, varying from person to person.

You decide to use your slaves to figure out which cask contains the poison before the dinner party.

Working under the assumptions that you cannot cancel the dinner party, and that there's no limit on how much wine a slave can drink, propose a way to figure out which single cask is poisoned before the dinner part begins.

The most obvious solution was to use a divide-and-conquer algorithm: assign 100 casks to each of the 10 slaves, then assign the 9 remaining healthy/living slaves to the 100 casks that incapacitated a slave, and repeat.

While this approach works assuming the poison acts in 30 minutes (or an otherwise short period of time), it fails assuming anything near the worst-case time of 5 hours.

Is there an approach which can be taken to determine which cask contains the poisoned wine within the 6 hours before the dinner party?

Answer 1

$10$ slaves can do it in $5$ hours. The key is that $2^{10} = 1024 > 1000$.

For a solution, see a hint:

Work in binary.

For more details,

Number the casks and label the slaves according to places in binary; the slaves sample a cask according to whether there is a $0$ or $1$ at their position. The status of the slaves after $5$ hours determines a number in binary accordingly, with $0$ and $1$ representing dead and alive, respectively. The cask with the corresponding number is poisoned.

Answer 2

A very uninteresting way. (I THINK) . make $10$ slaves to drink $1000$ glasses resprectively by making different sections . let them start drinking . Assuming they take 1/2hr for this purpose. Now do this again by interchanging section of each slave . this can be done $5$ times. Now assume 5 slaves react at $30$ mins and 5 at $5hrs$ and we know who reacts with what time . But while drinking record the time and name of the person on the cask or on the paper . The time at which a person died would then be known and as we know the reaction timings then comparing with time on the cask he drank the poisonous glass can be removed out . If time periods are different and if you can make assumptions then assume that somehow you know in what time a person will react. That would make it little bit easy