boat puzzle

Another puzzle... actually I spent quite a few train commutes thinking about this one.

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:

Mac-Flannel-Nadia


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:

Mac-Flannel-Nadia-cans


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:

Mac-Flannel-Molly


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?

Comments

Post a Comment

Popular posts from this blog

Marin Avenue (Berkeley)

Image
On Saturday, I got an email from Tim telling letting me know that Murphy's Spring Classics was going to start up Marin Ave. I'd missed that. Murphy announces his courses the day before, and indeed it was already well into the night before when the course announcement went out. I'd skipped over the details, jumping straight to middle and end games. Marin? I laughed at the irony, because not long before when he'd told me he was choosing to repeat the Nifty Twn Fifty which we'd done together last year versus selecting Murphy Mack's Stage Mullett two-day, I responded I didn't think I had it in me to ride Marin Ave two years in succession. Well, so much for that. I was committed, so I went downstairs to swap my 11-26 cassette for my Recon 12-27. The name is easily overlooked: "Marin Ave" fails to strike the same impression as, for example, "Redwood Gulch" or "China Grade". But among those in the know, Marin Ave is infamous i...
Read more

hummingbird feeder physics

Image
I couldn't figure out how the hummingbird feeder worked. Why didn't it overflow? Forces need to balance, of course. Neglecting surface tension, there liquid level is higher in the inner reservoir than in the feeding chamber, so there must be a corresponding pressure difference. Suppose the pressure in the inner chamber were zero. Then the column height difference would need to be atmospheric pressure / (density of liquid × gravity). But this is over 9 meters! Obviously the height difference is only approximately 1% of this. So the pressure difference inside versus outside is only approximately 1%. The inside is only slightly below atmosphere. So air is getting in. How? Does it diffuse through the liquid? If this were the dominant mechanism, it wouldn't take long for the pressure inside to go from 99% to 99.3%, for example, which should be plenty to push the column of liquid down in the inside chamber and thus push liquid out through the holes. It would over...
Read more

Gallium Pro geometry

Image
On Caltrain yesterday, I was surprised to see among the usual set of commuting bikes a SRAM Red-equipped Argon Gallium Pro. The bike immediately stole your attention. The design was one which has been trending: clear-coated carbon with plenty of text detail so the viewer is sure to realize he's gazing upon the result of advanced, proprietary engineering and not at yet another paint job on the same old OEM frames being pumped out of the same old Taiwanese factories. But it worked: the bottom bracket area was huge, the downtube a large-diameter "inverted Kamm tail" design seemingly designed to maximize wind resistance, the top tube a broad, eccentric shape which screamed "vertically compliant yet torsionally stiff". All it lacked were the pencil-think seat stays Cervelo popularized, but this was a machine designed for stiffness over anything else. It seemed dramatic overkill, since the bike was small (the Argon "XS" I suspect). There wasn't muc...
Read more