Four people must cross a rickety footbridge at night.
Many planks are missing, and the bridge can hold only two people at a time (any more than two, and the bridge collapses).
The travelers must use a flashlight to guide their steps; otherwise they're sure to step through a missing space and fall to their death. There is only one flashlight.
The four people each travel at different speeds.
Adam can cross the bridge in one minute; Larry in two minutes; Edge takes five minutes; and the slowest person, Bono, needs ten minutes.
The bridge is going to collapse in exactly seventeen minutes.
How can all four people cross the bridge?
Solution:
Since there is only one flashlight - this flashlight being indispensable - the only way to make progress is for two people to cross the bridge together to the far side and then to have one return to the nearside with the flashlight.
The net effect of a round-trip is to convey one person across the chasm.
When two people travel together, they go at the speed of the slower person.
Should Adam cross with Bono, Adam must slow down to Bono's pace, and it takes ten minutes to get across.
You might think that four round-trips would be needed to get all four people across.
Luckily, that's wrong.
The last trip is one-way and can convey two people across.
You need two and a half round-trips, the final one-way taking two people across.
The most appealing idea is probably to have Adam, who takes just one minute to cross, escort the slower people in succession.
On trip one, let Adam escort the slowest traveler, Bono (ten minutes needed), across the bridge.
This takes ten minutes.
Then Adam returns with the flashlight (taking a mere minute).
Adam next takes second-slowest Edge across (five minutes) and returns (one minute).
Finally, Adam and Larry cross the bridge (two minutes.) Total time: 10+1 + 5 + 1 + 2 = 19 minutes.
That's two minutes too long.
Were this situation to arise in real life, most people would probably conclude that it's hopeless.
They'd draw straws, or oust Bono.
It is probably only the fact that you know this is a puzzle guaranteed to have a solution that convinces you to seek it.
Try the old trick of listing the assumptions.
The most basic assumption is that people backtrack.
Somebody has to return the flashlight to the people still waiting to cross on the nearside, right? It's tough to see how you can get around that.
The puzzle makes it clear that no one goes anywhere without the flashlight.
(Should you suggest trick solutions, like tossing the flashlight across the chasm, or retrieving it with string, you'll be told that it's cheating.) We also assume that two people cross toward the far side and only one returns with the flashlight.
Would it do any good to try different numbers?
Well there's no point in a "trip" where no one crosses.
We're told that the bridge won't hold three or more people.
That leaves just two possibilities: one person, or two.
While you might conceivably do a "backward round-trip," sending one person across to the far side and then having him escort back someone who is already on the far side - that just makes things harder.
We're back to where we started.
Why not send the two slowest people across together? Bono is going to eat up most of the allotted seventeen minutes all by himself.
At least kill two birds with one stone by sending Edge across with him.
Then Edge won't be slowing anyone else down.
This idea is the keystone of the solution.
There's a good chance you're reading this and saying "I thought of that already! It doesn't work!" That's because this is one of those good ideas that gets easily derailed.
Most people's next thought is to imagine starting with Bono and Edge crossing together.
Then what? Then you've got two insufferably slow people on the far side with the only flashlight.
That means that one of them, presumably Edge, has to backtrack (slowly) to return the flashlight to the nearside.
Time elapsed: fifteen minutes.
Now there are three people on the nearside, including Edge, who alone dashes all hope of a seventeen-minute solution.
Some people give up there.
It's easy to assume that this fiasco means the basic idea was wrong.
Others are willing to take the next step and try the five/ten-minute trip at the very end.
The last crossing is special in that no one has to go back and return the flashlight.
This idea fares no better.
How do Edge and Bono end up on the nearside, with the flashlight, and with no one else with them? One of them (Edge most likely?) must have already 222 How Would You Move Mount Fuji? returned from the farside with the flashlight - in which case we're talking about a minimum ten-minute round-trip to the farside and back - or else the flashlight has been returned by one of the swifter travelers, who must also be waiting to cross again.
This leads to the same time problems as the previous case.
This is where many people throw in the towel.
They have examined the two extreme cases (the slow pair setting off first, and setting off last) and shown them to be unworkable.
The extremes are not the only possibilities.
The slow pair's trip can be in the middle.
That is what leads to the solution.
Round-trip one: The fastest pair, Adam and Larry, cross, taking two minutes.
One of them (let's say Adam - it doesn't matter) immediately returns with the flashlight (one minute).
Elapsed time: three minutes.
Round-trip two: The slow pair, Edge and Bono, cross, taking ten minutes.
As soon as they reach the farside, their bridge-crossing days are over.
They hand the flashlight to the faster person who is already there.
(That's Larry, assuming that Adam returned in the first round-trip.) Larry returns the flashlight to the nearside (two minutes).
Elapsed time: fifteen minutes.
Final, one-way trip: The fast pair is now reunited on the nearside.
They cross for the second and last time (two minutes).
Elapsed time: seventeen minutes.
This puzzle has roots in early medieval times.
Abbot Alcuin (735-804 A.D.) wrote a puzzle collection including an early version of the long-familiar brainteaser about a man taking a basket of cabbages, a goat, and a wolf across a river (the man mustn't leave the goat alone with the wolf, or the cabbages with an unsupervised goat).
Many variations have been devised in the past dozen centuries.
The river is Answers 223 sometimes replaced with a bridge that threatens to collapse or a pulley and bucket that the people use to escape from a tower.
The constraints may be a weight limit, a time limit, not allowing unchaperoned females, and the aforementioned predator-prey issues.
A puzzle about cannibals and missionaries crossing a river in a two-seat boat (any time the cannibals outnumber the missionaries, the cannibals eat them) played a role in early AI research.
Early AI programs were able to identify solutions.
The Microsoft puzzle is one of the hardest of the genre.
It has circulated as a much-forwarded e-mail, complete with its own "urban legend." The e-mail claims, "Reportedly, one guy solved it by writing a C program, although that took him 17 minutes to develop.
Another guy solved it in three minutes.
A group of 50, at Motorola, couldn't figure it out at all....Note: Microsoft expects you to answer this question in under 5 minutes." (They don't.)
Source:
"How Would You Move Mount Fuji?"
Microsoft's Cult Of The Puzzle
By William Poundstone
No comments:
Post a Comment