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?
Answer
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.
No comments:
Post a Comment