Recently I have moved and since I've basically exchanged flats with somebody else and her friend, I have been driving around three locations for a whole weekend. I would try to figure out which stuff to load into the car, where to drive next, which person to bring along on the free seat. One would of course need to drive the car where the stuff should go to, but also have a sufficient number of people to carry stuff and put up furniture.

This has reminded me of the classical salad-sheep-fox riddle, which goes like this: You have a salad, a sheep and a fox. They are all on one bank of a river and you want to cross it. You have a raft which can only hold one thing at a time. But you cannot leave the sheep unattended with the fox, otherwise the fox will kill the sheep. Yet you cannot leave the salad unattended with the sheep, as the sheep will eat it. You need to figure out a way to transfer the stuff without leaving something unattended.

So you cannot start ferrying the salad, the fox will kill the sheep. You cannot start ferrying the fox, the sheep will eat the salad. You will need to ferry the sheep first. Then you ferry back. We can take either the salad or the fox. Let us try the salad. We end up with the salad and the sheep on the other bank, the fox at the start. We cannot just leave them there together unattended. But ferrying back the salad makes no sense, so we ferry back the sheep. On the starting bank we exchange the sheep for the fox, ferry over the fox. We then got the salad and the fox together on the other bank, the sheep left behind. We sail back, load in the sheep, and ferry it to the other bank. Done.

This should be solvable systematically. We have three objects, and three places where they can be. This makes for 27 states, but we can already rule out the states where more than one element is on the raft. This gives us the following states, with the original river bank on the right and the other bank on the left. The raft is in the middle.

Read more…