25
$\begingroup$

When you're looking at a logical word puzzle, what sorts of clues should you try to look for to solve them? There have been quite a few puzzles posted to this site so far that I spent a few minutes pondering, and I just had no idea where to start. Once I saw the answers they usually made sense, but I don't seem to have a good gameplan for trying to figure it out on my own (which is the fun part!) I'd like to get better at solving puzzles like this, and I imagine there are techniques I'm unaware of to finding the important information and where to begin (because part of the trick to puzzles like these is that they give you extra information you don't need to throw you off, right?)

So here's a good example of one such puzzle. (Source; solution also displays at link).

You are the ruler of a medieval empire and you are about to have a celebration tomorrow. The celebration is the most important party you have ever hosted. You've got 1000 bottles of wine you were planning to open for the celebration, but you find out that one of them is poisoned.

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?

I thought about it for a little while, and I just had no idea where to start. All I could think is that, since you have 24 hours and it takes less than 24 hours to die of the poisoning, each of the 1000 people should test one bottle of wine. But that's clearly not the best answer, because that's obvious; they're asking what's the smallest number of testers. I reread the problem several times trying to pick out the piece of information that should be my starting point, but I was unsuccessful.

Once I read the solution it made sense, but it would never have occurred to me. How do you figure out where to start solving a puzzle like this when you're completely flummoxed?

$\endgroup$
  • 2
    $\begingroup$ I have ethical objections to this puzzle. If you read wikipedia on en.wikipedia.org/wiki/Nazi_human_experimentation, this sort of thing has literally been done, and the Soviet Union was also engaged in some similar "experiments". $\endgroup$ – osa Apr 27 '15 at 16:28
11
$\begingroup$

As I've said in many other questions, puzzles like the one you posted are what I call information puzzles – that is, puzzles where you perform some trial to get as much information as possible about a certain unknown fact.

In this case, you can notice that each slave you use can either die or not die, which is 2 possible outcomes. If you then use $n$ slaves, then there are a total of $2^n$ possible outcomes, and the smallest $n$ for which $2^n \ge 1000$ is $10$. If you think about it in this fashion from the beginning, you will probably realize that each prisoner can sample from more than one bottle in the process, because that's the only way this method can really work.

There is a similar problem in which you have two days to figure out which bottle out of 27 is poisoned, which only requires three slaves instead of the five it would require if you only had one day. Why is this?

Because each slave now has three possible states - not dead, dead in one day, dead in two days. So $3^3 = 27$, as required. But even knowing that a prisoner can sample from more than one bottle, it's still somewhat difficult to devise an algorithm for which bottles each slave should drink each day.

P.S. I don't personally like the formulation of "anywhere between 10 to 20 hours, and you don't know how long" to imply that you can't use a timing attack on the test. I prefer instead that "anyone who drinks the poison dies at the stroke of midnight, regardless of when they drank it".


As for the more general problem of how to solve word problems (which is what your question is about), there is only really a general set of principles you can follow.

First, identify the problem. This puzzle was an information puzzle. Generally, information puzzles will ask you to "find out which [something] [has some property]" – in this case, figuring out which bottle of wine was poisoned. There might be some puzzles that are about direct calculation or traversing a graph or solving an equation.

Then, identify common steps to solve problems like these. In the case of information puzzles, you'll want to identify how many possible results you want, and how many possible outcomes the trial will give you.

Finally, try and solve the problem using those methods. In the case of information puzzles, this involves trying to map each desired result to an outcome of the trial. In the case of the prisoners having two days to sample wine bottles, you need some way of configuring the bottles on the first day, so that on the second day, there are still enough prisoners alive that you can carry on with the bottles you still don't know aren't poisoned.

If these don't work, generally the most you can do is keep thinking about it until you do find some way to solve it. Sometimes, if you go looking for a solution, you won't even understand it or how it solves the problem.

As an exercise, try to devise the schedule that three slaves would follow for sampling wine if they had two days to test 27 bottles.

$\endgroup$
  • 1
    $\begingroup$ Excellent, thank you so much! I appreciate the other answers I got as well, but my main goal was for general tips, and I feel like the tips you gave will help me to solve other problems in the future. I hadn't considered the "each has two states, dead or not dead" approach, which makes a lot of sense and seems applicable to other word problems. So thanks very much; wish I could upvote more than once! :) $\endgroup$ – WendiKidd May 25 '14 at 21:07
  • 1
    $\begingroup$ You're welcome. That's what we're here for, to help :P $\endgroup$ – Joe Z. May 25 '14 at 21:09
9
$\begingroup$

As Ross already mentioned, the first aha! moment should be when you realize that a prisoner can drink from multiple bottles. From this the next step is realizing that you can only perform the test once, so you cannot do separate tests based on the results of the previous test.

The key concept you should first realize after this is: this means that each prisoner can only signal you two states: he will die, or he will live.

Based on the fact that you now know that you have tons of prisoners who can each signal you two different states you now need to think on something that can represent a number between 1 and 1000 in the least amount of died/lived states.

Now, what is the concept that resembles this?

to use prisoners as binary digits!

So the solution: you have to label each bottle from 1 to 1000, and label each prisoner with the powers of two. You can easily see, you need ceil(log_2(1000)) = 10 prisoners for this. Then each prisoner should drink from bottles which also have the specific power of two in its given representation.

So prisoner 1 will drink from the odd numbered bottles, prisoner 2 will drink from bottles numbered 2,3,6,7,10,11,..., prisoner 3 (or more exactly 4) will drink from bottles 4,5,6,7,12,13,14,15,..., prisoner 4 (8) will drink from 8,9,10,11,12,13,14,15,24,25,..., etc.

After the drinking you have to wait for the prisoners to die. There will be exactly one bottle, from which excactly those prisoners who have died drank. Just add the prisoner's numbers together and you'll get to the specific bottle you shouldn't drink from

The result again is 10.

$\endgroup$
  • $\begingroup$ It's easier to consider that you have to give some from each bottle to a different subset of prisoners, so if that subset of prisoners dies, you know the bottle that corresponds to that subset is the poisoned one. $\endgroup$ – Joe Z. May 26 '14 at 1:05
  • $\begingroup$ One thing to keep in mind is that each prisoner would have to drink from, on average, around 500 bottles. Let's hope you got a way to hand out that wine in really small dosages, because every ml you need per bottle means your prisoner will have to drink 500 ml of wine. so even if you only feed a quarter shot glass, that's still 2.5 liters of wine. $\endgroup$ – Nzall Nov 3 '14 at 10:00
  • $\begingroup$ @NateKerkhofs: even miniscule amounts are deadly, so you can simply give everyone the same amount of total wine, mixed together from the bottles. They are doomed prisoners anyway, probably won't mind that they have to drink wine mixed from various sources. $\endgroup$ – SztupY Nov 3 '14 at 10:04
8
$\begingroup$

I'll give an answer that pertains to puzzles in general, not specifically this puzzle or information puzzles. You asked about "word puzzles", but I don't think there is anything specific to word puzzles as opposed to other kinds. Anyway, most puzzles are word puzzles (one kind of a non-word puzzle is a cryptarithmetic puzzle).

A puzzle, by definition, doesn't have an algorithm for solving it. This is different from word problems you were taught at school. (Although the first time you encounter a word problem of a certain kind, it's still a puzzle for you, because you don't know the algorithm for it yet.) Nevertheless, I can give you some tips.

First, you write that you "spent a few minutes pondering". Here's your problem. You need to think for a long while. You try to think of one way of solving a puzzle. It doesn't lead you anywhere, so you think of another approach and so on. You might find certain environments stimulative. For example, I like to think while walking or showering, but some people like to think on the toilet. So instead of giving up after a few minutes, try to think of the puzzle at different times during the day, for at least one day.

Try to think of any other problems your puzzle resembles.

One general approach is to try to reach a partial solution. There are several kinds of "partial solutions". For example, if you are trying to solve an optimization problem (e.g., "what is the smallest number of prisoners?"), usually there is an obviously-not-optimal answer (e.g., "Make every prisoner taste a single bottle. I'll need 1000 prisoners."), then try to improve it ("can I involve only 500 prisoners?"). A partial solution can also be a solution to a simpler problem. For example, in the case of the camel transporting bananas problem, try first solving the problem for 2000 bananas instead of 3000.

Make sure you understand the significance of every detail in the puzzle. For example, why is it important that death occurs after at most 20 hours? Because it means that you can't make a prisoner taste a bottle, wait to make sure he doesn't die, and only then test another bottle on the same prisoner. Why is it important that death occurs after at least 10 hours? No reason, because you always might be out of luck. Such cases of useless information are quite rare, so make sure you understand the significance of everything. Sometimes you have the opposite situation: It seems that you don't have enough info. If that happens, think why.

Good luck and have fun!

$\endgroup$
5
$\begingroup$

There is an aha! moment when you realize that one person can sample more than one bottle of wine. Those are hard to describe how to come to. Problems that involving find 1 out of N often come down to partitioning N in some useful way. (The classic 12 balls and a scalesplits them in thirds). Maybe you have seen the problem of guessing somebody's number where you are allowed a small number of guesses and are told higher/lower. You want to split the possibilities in half, then in half again etc. Here you can think of lining up the bottles in order and you are asked to find the chosen number. However, because of the time it takes to die, you have to do all the tests simultaneously. If you have played with binary numbers this problem is much easier.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.