You have a wolf, a goat, and a cabbage that you want to take across a river. (There are many versions of this puzzle in different cultures; the types of animals vary, but the problem is the same.) Your boat can only carry yourself and one other thing. The wolf will eat the goat if they’re left alone together, and the goat will eat the cabbage if you’re not there to stop it. How do you get all three across the river? Show answer

I’m going to use w for wolf, g for goat, and c for cabbage, and draw little diagrams with the destination to the right: You have to choose which one of the three to take first across the river. If you take the wolf, the goat will eat the cabbage, and if you take the cabbage, the wolf will eat the goat, so the only thing you can do is take the goat across. Then you come back. Now you have to decide to take either the wolf or cabbage across. It actually makes no difference (see Section 9.3: Symmetry) so let’s just pick one: the wolf. Now the problem is that the wolf and the goat are together. You can’t just take the boat back, because the wolf would eat the goat. You might think, well let’s take the wolf back, but that would be undoing what you just did, and if you took the cabbage across instead of the wolf, you’d run into the same problem. The only thing you can do is take the goat back with you. (We can be more confident about this if we consider working backwards from the target: the last move has to be bringing the goat across, with the wolf and cabbage already on the far bank of the river, so at some point the goat has to go back.)

Now you can take either the goat or the cabbage across. If you take the goat, you’d be undoing your last move, so let’s take the cabbage, then come straight back for the goat. The important lesson to learn is that although it seems useless to take the goat back and forth, it was necessary, and the most efficient way to get everything across the river.