Friday, April 22, 2011

boat puzzle: solving the simple cases

Previously I described the boat puzzle and how it's provided some mental exercise for my train commutes.

The traditional example is the Mac-Flannel-Nadia case:



The solution, as I described, is to identify a maximum independent set, in this case Mac and Nadia. Then you need a number of seats on the boats sufficient to transport the rest, in this case Flannel. So:

1. Flannel taken from shore A to shore B.
2. return with empty boat.

Next step doesn't matter, as Mac and Nadia are identical in this problem. I'll pick Mac:
3. Mac taken from shore A to shore B.

Now Mac and Flannel are together. I need to return with Flannel on the boat, as I cannot leave the two, or Mac will turd.

4. Flannel taken from shore B to shore A (leave Mac on B).

But then....

5. Take Nadia from A to B (leave Flannel alone). Nadia is now with Mac, and they lick each others faces, so that's fine.
6. Return with empty boat.
7. Bring Flannel from A to B.

When I add in the cans, it's only slightly more complex. I circle the maximum independent set, the cats which need to be left behind on the first boat trip:

Mac-Nadia-Flannel-cans

Here I add steps between steps 2 and 3 in the above:

2.1 bring cans from shore A to shore B. Leave those with Flannel, who can't open them.
2.2 return with empty boat.

Then continue with step 3.

Here is a problem which cannot be solved in a nontrivial number of seats on the boat. Recall if I have more than the number of seats sufficient to isolate the maximum independent set, then a solution becomes trivial, so I am only interested in problems with non-trivial solutions.

Another problem: I add Joshua to Mac, Nadia, and Flannel. Joshua is very friendly, but Flannel is a pest, and due to certain issues, Joshua can't defend himself as well as he might. So I don't want to leave Joshua with Flannel, either. The maximal independent set is obviously Joshua, Nadia, and Mac. I therefore want to be able to solve it with only one seat on the boat:

Mac-Nadia-Flannel-Joshua


Out of luck here: I know of no solution.

So I conjectured that all problems can be reduced to either Mac-Nadia-Flannel-cans or Mac-Nadia-Flannel-Joshua. If the former, I can solve them. If the latter, I cannot. That was my conjecture, but I no longer believe it to be true.

No comments: