Maximal non-intersecting boat tours

In a country, there are $n$ islands, and each island has exactly one port. A travel agency is planning a series of boat tours where it would employ a number of boats that start and end on these ports. They must obey these rules:

1. Each tour starts and ends at the same port and does not stop at any other port. That is, each tour is a loop that passes through exactly one port.

2. No two tours may intersect each other, except at ports.

3. For two distinct tours A and B, either A must circle an island that B doesn't, or B circles an island that A doesn't. By "circling" an island we mean: the region created by the tour contains the island.

Assuming that all islands have non-zero area and all boats are treated as points, what is the largest number of tours that can be run at the same time?

Solution

Answer: $2n$

First we will show an arrangement of $2n$ tours that satisfy the given constraints, and then we shall show that it is the largest attainable number.

For each island, have a tour that starts at that island and circle it closely to the shore so that we don't greatly alter the shape of the island. Altogether, there are $n$ of such tours.

Then, label the island $I_1, \dots, I_n$. For each $i = 2, \dots, n$, have a tour that starts at $I_1$, circles $I_1, \dots, I_i$ and comes back to $I_1$. There are $n-1$ such tour. Finally we can have a tour that doesn't circle any island. In total, there are $2n$ tours.

The proof for maximality is similar to our construction. There can be at most one tour that doesn't circle any island, and there can be at most $n$ tours that circle exactly one island. Now we show that there are at most $n-1$ tours that circle multiple islands. Let's call a tour that circles multiple islands a "complex" tour.

Suppose $T_1$ and $T_2$ are both complex tours and both circle an island in common $I_1$. Furthermore, WLOG, we can assume that $T_1$ circle an island $I_2$ that $T_2$ doesn't. We assert that $T_2$ must be inside $T_1$. Otherwise, the possibilities are either $T_1$ is inside $T_2$, which is impossible since $T_2$ doesn't contain $I_2$, or that they are disjointed, which is impossible because they both contain $I_1$, or that they intersect. There must be at least two points of intersection, but they can only intersect in ports and they each can stop in oneport only, also impossible. Thus, we have just proved the following statement:

Given two complex tours, either they are disjoint or one is inside the other.

From here, it's matter of induction to show that there can be at most $n-1$ complex tours given $n$ islands. Take the smallest complex tour $T$ that does not contain another complex tour. $T$ circles at least two islands, and any other complex tour either contains $T$ or is disjoint from $T$. So as far as other complex tours are concerned, we can regard $T$ as an island on its own, thereby reducing the number islands by at least 1. Since there are now at most $n-1$ "islands", then there are at most $n-2$ complex tours. Altogether with $T$, we have at most $n-1$ tours.