## Thursday, April 14, 2011

### boat puzzle

There's a classic puzzle where a farmer needs to get a fox, a sheep, and a cabbage across a river on a boat. I don't have much experience with transporting fox or sheep, and cabbage aren't very exciting, so I'll recast the problem in terms of cats.

Consider I want to transport three cats across a river on a boat. I can watch over the cats while they're on the boat, but when they're on one shore or the other, they need to get along. The names of the three cats are Mac, Flannel, and Nadia.

If I can watch them they're fine, but if Nadia is left unsupervised with Flannel, Flannel will harrass Nadia. who needs her rest. And if Flannel is left unsupervised with Mac, Mac will turd, so we need to be careful not to let that happen. On the other hand, if Mac and Nada are left with each other, they'll just lick each others faces, so that's fine.

The challenge is there is only one extra spot on the boat for cats. For example, I can transport Nadia, but if Nadia's on the boat and Mac steps on, Mac will sink the boat.

The goal is to get the three across the river without leaving Nadia and Flannel unsupervised or Flannel and Mac unsupervised. How to proceed?

Well, I can represent the relationships between the cats with a graph. Each cat is a node in the graph, and lines connect cats which cannot be left together without supervision. Here is the graph for this problem:

I can make the problem slightly harder by adding in a tray of cat food cans which must be transported with the cats. If I carry the cans, that's all I can carry. Cats can't open cans, so the cans can be left with any of the cats. The diagram becomes:

So far, not much new. Now suppose I consider another problem. Instead of carrying Nadia, I want to carry Molly. Molly will rip to shreds any other cats if she's not supervised, so the diagram (without cans) now becomes:

I can solve this one trivially with two or three seats on the boat, but with one seat, is it possible?

In general, I can construct arbitrary graphs with an arbitrary number of connections. The question posed to me during my commute was: how many seats does the boat need to have to transport everything across?