27
$\begingroup$

I have seen many variations of the following puzzle:

Once upon a time, a farmer went to the market and purchased a fox, a goose, and a bag of beans. On his way home, the farmer came to the bank of a river and rented a small boat. The boat was so small that the farmer could carry only himself and a single one of his purchases - the fox, the goose, or the bag of the beans.

The farmer knew that if he left the fox and the goose together, the fox would eat the goose. Likewise, if left alone with the beans, the goose would eat them.

The farmer was able to get all of his purchases safely across the river. How did he do it?

I know that the solution is:

  1. Take the goose across, come back empty.
  2. Take the beans across, bring the goose back.
  3. Leave the goose on the bank, take the fox across, come back empty.
  4. Take the goose across.

(The fox and beans are interchangeable).

My question is this:
When given a problem in this format, what is the best way to begin solving it?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Go backwards! (Okay, that's useless here, but it's SO often the easiest brainteaser hack...) $\endgroup$
    – Jaydles
    May 14 '14 at 21:02
  • 3
    $\begingroup$ @Jaydles: Not useless at all! The puzzle is impossible if you don't realize you can take items from the destination back to the start. $\endgroup$
    – Michael Myers
    May 14 '14 at 21:38
  • 2
    $\begingroup$ @MichaelMyers, ha - you're right: The big "aha" in these is that you have to bring some things back to the "start side". I meant the "solve from a successful outcome and reverse steps" type of backward, but my ambiguous word choice accidentally worked! $\endgroup$
    – Jaydles
    May 14 '14 at 22:10
  • $\begingroup$ Piggy-backing on @Per Manne's answer, there is a reverse puzzling problem that creates a diagram to represent this very puzzle. $\endgroup$
    – potapeno
    Jul 4 '16 at 16:21
39
$\begingroup$

The quickest way may be by some form of intelligent trial and error, but there is one systematic method which will always work, and that is to translate the problem into the language of graph theory.

Start by making a complete list of all possible configurations of people and items. In this case, the boat will always be together with the farmer, so there are four objects, and \$2^4=16\$ possible configurations.

Cross out all configurations where something will be eaten, and number the remaining configurations. Here, six configurations are forbidden, leaving us with ten, which I describe by what is found on the left (original) river bank: $$1 : (M,F,G,B) \qquad 2: (M,F;G)\qquad 3:(M,F,B)$$ $$4 : (M,G;B)\qquad 5:(M,G) \qquad 6:(F,B)$$ $$7:(F)\qquad 8:(G)\qquad 9:(B)\qquad 10:(none)$$ I'm using the letter M for the farmer, who is described as "he", in order to avoid confusion with the fox (F).

Now we will make a graph with 10 nodes, where each node is one of the configurations above. Two nodes will be connected by an edge if and only if it is possible to get from one configuration to the other with a single boat trip.

Here, node 1 will be connected to node 6, and node 2 will be connected to node 7 and to node 8. We find that node 3 will be connected to three nodes; node 6, node 7, and node 9. Node 4 will be connected to node 8 and node 9, and node 5 will be connected to node 8 and node 10. Going through the remaining nodes 6 - 10, we find no new connections (the farmer has to return from the other river bank, resulting in one of the configurations 1 - 5).

The next step is to make a drawing of this graph. My computer abilities are very limited, but you should get something like this:

        7--2
       /    \
1--6--3      8--5--10
       \    /
        9--4

where you are allowed to go from node 3 to either 7 or 9, and from 2 or 4 to node 8.

Finally, we return to the original question, which can now be interpreted as: Find a path in our graph starting at node 1 and ending at node 10. The two solutions are immediately apparent!

Improve this answer
$\endgroup$
1
  • $\begingroup$ Very, very well thought out. Nice answer! The question becomes, though, can I write a program to solve it? But that's for another site/day. $\endgroup$
    – Xynariz
    May 21 '14 at 17:38
9
$\begingroup$

In this case, you can look at the first few moves.

You can't take the fox or the beans, and if you go solo you will come back solo and be back at the start. For the second move, if you take the goose back you are back where you started, so you come back solo. You are a long way into the puzzle by then.

Improve this answer
$\endgroup$
4
$\begingroup$

In most of these sorts of puzzles, there is a single moment when you crack it. For this one, it's the realization that

you can bring something back. I mean, that's kind of crazy, I am trying to get everything from this bank to that bank, why would I bring anything in the wrong direction?

If it never occurs to you to

bring anything back, the puzzle seems impossible. For the first step, you know it's ok to leave the fox with the beans, and it's not ok to leave the goose with anything, so you take it, fine. Then whatever you take over next you're going to have to leave with the goose while you go back for the third thing, and that won't work. If taking the goose back occurs to you here, you've cracked the puzzle and the rest is just mechanics.

Same thing with the limited-time lights and two-people-at-time-over-a-bridge thing. Most people want to pair slow with fast, or put two slows together but the key to solving it is actually pairing the two fastest. With the liars and truth tellers it's asking one what the other would say. And so on.

Improve this answer
$\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.