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.

A Divided Kingdom

A kingdom has the shape of a convex $n$-sided polygon $A_1 \dots A_n$. The King owns a castle at point $O$ in the interior of the kingdom, and he has $n$ princes, $P_1, \dots P_n$. They are each given a castle at the vertices of the polygon, so that prince $P_i$ has a castle precisely at $A_i$. The area $OA_iA_{i+1}$ is called the province $i$.

One day, a strife breaks out in the kingdom and each prince declares independence from the King. As a result, each province is divided into one or more vassals, each of which is shaped like a triangle. (Note that each province is a triangle to begin with, so some of the more stable province do not necessarily break apart into multiple vassals). At the vertices of these triangles, a citadel (a smaller castle) was erected.

Each castle and fort then declares an allegiance to King or one of the princes while following these rules:
1. Each castle declares allegiance to its original owner. That is, castle at $O$ keeps its allegiance to the King and castle at $A_i$ keeps its allegiance to prince $P_i$.

2. Each citadel that lies in the province border declares allegiance to either one of the owner of the castles at the endpoints of the province border. For example, a citadel that lies in the line $A_1 A_2$ may declare allegiance to prince $P_1$ or $P_2$, and a citadel that lies in the line $OA_3$ may declare allegiance to either the King or prince $P_3$.

3. Each citadel that lies in the interior of a province declares an allegiance to either one of the owner of the castles at the vertices of the province. For example, a citadel that lies in the province 1 may declare allegiance to either the King, prince $P_1$, or prince $P_2$ (because province 1 is the triangle $OA_1A_2$).

Now, with all citadels and forts having declared allegiance, each vassal's ownership is resolved as follows. Note that each vassal is shaped like a triangle, so it has precisely three citadels or castles on the vertices. If two or more of those citadels or castles declare allegiance to an entity, then the vassal is owned by that entity. For example, if a vassal has vertices declaring allegiance to $P_1, P_2, P_1$, then that vassal is owned by prince $P_1$.

A vassal whose vertices declare allegiance to three different entities is then left in a constant state of war. Prove that the number of such vassals is $n+2k$ where $k$is a non-negative integer.