Problem 1912

Answer: The largest $k$ is $k=\left\lfloor\log_{2} n\right\rfloor$.

We reformulate the problem using graph theory. We have a complete graph $K_{n}$ on $n$ nodes (corresponding to islands), and we want to colour the edges (corresponding to ferry lines) with $k$ colours (corresponding to companies), so that every Hamiltonian path contains all $k$ different colours. For a fixed set of $k$ colours, we say that an edge colouring of $K_{n}$ is good if every Hamiltonian path contains an edge of each one of these $k$ colours.

We first construct a good colouring of $K_{n}$ using $k=\left\lfloor\log_{2} n\right\rfloor$ colours.

Claim 1. Take $k=\left\lfloor\log_{2} n\right\rfloor$. Consider the complete graph $K_{n}$ in which the nodes are labelled by $1,2, \ldots, n$. Colour node $i$ with colour $\min \left(\left\lfloor\log_{2} i\right\rfloor+1, k\right)$ (so the colours of the first nodes are $1,2,2,3,3,3,3,4, \ldots$ and the last $n-2^{k-1}+1$ nodes have colour $k$ ), and for $1 \leqslant i<j \leqslant n$, colour the edge $ij$ with the colour of the node $i$. Then the resulting edge colouring of $K_{n}$ is good.

Proof. We need to check that every Hamiltonian path contains edges of every single colour. We first observe that the number of nodes assigned colour $k$ is $n-2^{k-1}+1$. Since $n \geqslant 2^{k}$, we have
$$n-2^{k-1}+1 \geqslant \frac{n}{2}+1$$
This implies that in any Hamiltonian path, there exists an edge between two nodes with colour $k$. Then that edge must have colour $k$.

We next show that for each $1 \leqslant i<k$, every Hamiltonian path contains an edge of colour $i$. Suppose the contrary, that some Hamiltonian path does not contain an edge of colour $i$. Then nodes with colour $i$ can only be adjacent to nodes with colour less than $i$ inside the Hamiltonian path. Since there are $2^{i-1}$ nodes with colour $i$ and $2^{i-1}-1$ nodes with colour less than $i$, the Hamiltonian path must take the form
$$(i) \leftrightarrow(<i) \leftrightarrow(i) \leftrightarrow(<i) \leftrightarrow \cdots \leftrightarrow(<i) \leftrightarrow(i),$$
where $(i)$ denotes a node with colour $i$, $(<i)$ denotes a node with colour less than $i$, and $\leftrightarrow$ denotes an edge. But this is impossible, as the Hamiltonian path would not have any nodes with colours greater than $i$.

Fix a set of $k$ colours, we now prove that if there exists a good colouring of $K_{n}$, then $k \leqslant\left\lfloor\log_{2} n\right\rfloor$. For $n=2$, this is trivial, so we assume $n \geqslant 3$. For any node $v$ of $K_{n}$ and $1 \leqslant i \leqslant k$, we denote by $d_{i}(v)$ the number of edges with colour $i$ incident with the node $v$.

Lemma 1. Consider a good colouring of $K_{n}$, and let $AB$ be an arbitrary edge with colour $i$. If $d_{i}(A)+d_{i}(B) \leqslant n-1$, then the colouring will remain good after recolouring edge $AB$ with any other colour.

Proof. Suppose there exists a good colouring together with an edge $AB$ of colour $i$, such that if $AB$ is recoloured with another colour, the colouring will no longer be good. The failure of the new colouring being good will come from colour $i$, and thus there exists a Hamiltonian path containing edge $AB$ such that initially (i.e. before recolouring) $AB$ is the only edge of colour $i$ in this path. Writing $A=A_{0}$ and $B=B_{0}$, denote this Hamiltonian path by
$$A_{s} \leftrightarrow A_{s-1} \leftrightarrow \cdots \leftrightarrow A_{1} \leftrightarrow A_{0} \leftrightarrow B_{0} \leftrightarrow B_{1} \leftrightarrow \cdots \leftrightarrow B_{t-1} \leftrightarrow B_{t},$$
where $s, t \geqslant 0$ and $s+t+2=n$.

In the initial colouring, we observe the following.
- The edge $B_{0}A_{s}$ must have colour $i$, since otherwise the path
$$A_{0} \leftrightarrow A_{1} \leftrightarrow \cdots \leftrightarrow A_{s-1} \leftrightarrow A_{s} \leftrightarrow B_{0} \leftrightarrow B_{1} \leftrightarrow \cdots \leftrightarrow B_{t-1} \leftrightarrow B_{t}$$
has no edges of colour $i$.
- Similarly, the edge $A_{0}B_{t}$ must have colour $i$.
- For each $0 \leqslant p<s$, at least one of the edges $B_{0}A_{p}$ and $A_{0}A_{p+1}$ must have colour $i$, since otherwise the path
$$A_{s} \leftrightarrow \cdots \leftrightarrow A_{p+2} \leftrightarrow A_{p+1} \leftrightarrow A_{0} \leftrightarrow A_{1} \leftrightarrow \cdots \leftrightarrow A_{p-1} \leftrightarrow A_{p} \leftrightarrow B_{0} \leftrightarrow B_{1} \leftrightarrow \cdots \leftrightarrow B_{t}$$
has no edges of colour $i$.
- Similarly, for each $0 \leqslant q<t$, at least one of the edges $A_{0}B_{q}$ and $B_{0}B_{q+1}$ must have colour $i$.

In the above list, each edge $A_{0}X$ appears exactly once and also each edge $B_{0}X$ appears exactly once (where $A_{0}B_{0}$ and $B_{0}A_{0}$ are counted separately). Adding up the contributions to $d_{i}(A)+ d_{i}(B)$, we obtain
$$d_{i}(A)+d_{i}(B) \geqslant(s+1)+(t+1)=n .$$
This contradicts our assumption that $d_{i}(A)+d_{i}(B) \leqslant n-1$.

Our strategy now is to repeatedly recolour the edges using Lemma 1 until the colouring has a simple structure. For a node $v$, we define $m(v)$ to be the largest value of $d_{i}(v)$ over all colours $i$.

Lemma 2. Assume we have a good colouring of $K_{n}$. Let $A, B$ be two distinct nodes, and let $j$ be the colour of edge $AB$ where $1 \leqslant j \leqslant k$. If
- $m(A) \geqslant m(B)$ and
- $m(A)=d_{i}(A)$ for some $i \neq j$,
then after recolouring edge $AB$ with colour $i$, the colouring remains good.

Proof. Note that
$$d_{j}(A)+d_{j}(B) \leqslant(n-1-m(A))+m(B) \leqslant n-1,$$
and so we may apply Lemma 1.

Lemma 3. Assume we have a good colouring of $K_{n}$. Let $S$ be a nonempty set of nodes. Let $A \in S$ be a node such that $m(A) \geqslant m(B)$ for all $B \in S$, and choose $1 \leqslant i \leqslant k$ for which $d_{i}(A)=m(A)$. Then after recolouring the edge $AB$ with colour $i$ for all $B \in S$ distinct from $A$, the colouring remains good.

Proof. We repeatedly perform the following operation until all edges $AB$ with $B \in S$ have colour $i$ :
> choose an edge $AB$ with $B \in S$ that does not have colour $i$, and recolour it with colour $i$.
By Lemma 2, the colouring remains good after one operation. Moreover, $m(A)$ increase by 1 during an operation, and all other $m(B)$ may increase by at most 1 . This shows that $m(A)$ will remain maximal amongst $m(B)$ for $B \in S$. We will also have $d_{i}(A)=m(A)$ after the operation, since both sides increase by 1 . Therefore the operation can be performed repeatedly, and the colouring remains good.

We first apply Lemma 3 to the set of all $n$ nodes in $K_{n}$. After recolouring, there exists a node $A_{1}$ such that every edge incident with $A_{1}$ has colour $c_{1}$. We then apply Lemma 3 to the set of nodes excluding $A_{1}$, and we obtain a colouring where
- every edge incident with $A_{1}$ has colour $c_{1}$,
- every edge incident with $A_{2}$ except for $A_{1}A_{2}$ has colour $c_{2}$.
Repeating this process, we arrive at the following configuration:
- the $n$ nodes of $K_{n}$ are labelled $A_{1}, A_{2}, \ldots, A_{n}$,
- the node $A_{i}$ has a corresponding colour $c_{i}$ (as a convention, we also colour $A_{i}$ with $c_{i}$ ),
- for all $1 \leqslant u<v \leqslant n$, the edge between $A_{u}$ and $A_{v}$ has colour $c_{u}$,
- this colouring is good.

Claim 2. For every colour $i$, there exists a $1 \leqslant p \leqslant n$ such that the number of nodes of colour $i$ amongst $A_{1}, \ldots, A_{p}$ is greater than $p / 2$.

Proof. Suppose the contrary, that for every $1 \leqslant p \leqslant n$, there are at most $\lfloor p / 2\rfloor$ nodes of colour $i$. We then construct a Hamiltonian path not containing any edge of colour $i$. Let $A_{x_{1}}, \ldots, A_{x_{t}}$ be the nodes with colour $i$, where $x_{1}<x_{2}<\cdots<x_{t}$, and let $A_{y_{1}}, A_{y_{2}}, \ldots, A_{y_{s}}$ be the nodes with colour different from $i$, where $y_{1}<y_{2}<\cdots<y_{s}$. We have $s+t=n$ and $t \leqslant\lfloor n / 2\rfloor$, so $t \leqslant s$. We also see that $y_{j}<x_{j}$ for all $1 \leqslant j \leqslant t$, because otherwise, $A_{1}, A_{2}, \ldots, A_{x_{j}}$ will have $j$ nodes of colour $i$ and less than $j$ nodes of colour different from $i$. Then we can construct a Hamiltonian path
$$A_{x_{1}} \leftrightarrow A_{y_{1}} \leftrightarrow A_{x_{2}} \leftrightarrow A_{y_{2}} \leftrightarrow A_{x_{3}} \leftrightarrow \cdots \leftrightarrow A_{x_{t}} \leftrightarrow A_{y_{t}} \leftrightarrow A_{y_{t+1}} \leftrightarrow \cdots \leftrightarrow A_{y_{s}}$$
that does not contain an edge with colour $i$. This contradicts that the colouring is good.

So for every colour $i$, there has to be an integer $p_{i}$ with $1 \leqslant p_{i} \leqslant n$ such that there are more than $p_{i} / 2$ nodes assigned colour $i$ amongst $A_{1}, \ldots, A_{p_{i}}$. Choose the smallest such $p_{i}$ for every $i$, and without loss of generality assume
$$p_{1}<p_{2}<\cdots<p_{k}$$
Note that the inequalities are strict by the definition of $p_{i}$.

Then amongst the nodes $A_{1}, \ldots, A_{p_{i}}$, there are at least $\left\lceil\left(p_{j}+1\right) / 2\right\rceil$ nodes of colour $j$ for all $1 \leqslant j \leqslant i$. Then
$$p_{i} \geqslant\left\lceil\frac{p_{1}+1}{2}\right\rceil+\left\lceil\frac{p_{2}+1}{2}\right\rceil+\cdots+\left\lceil\frac{p_{i}+1}{2}\right\rceil .$$
This inductively shows that
$$p_{i} \geqslant 2^{i}-1$$
for all $1 \leqslant i \leqslant k$, and this already proves $n \geqslant 2^{k}-1$.

It remains to show that $n=2^{k}-1$ is not possible. If $n=2^{k}-1$, then all inequalities have to be equalities, so $p_{i}=2^{i}-1$ and there must be exactly $2^{i-1}$ nodes of colour $i$. Moreover, there cannot be a node of colour $i$ amongst $A_{1}, A_{2}, \ldots, A_{p_{i-1}}$, and so the set of nodes of colour $i$ must precisely be
$$A_{2^{i-1}}, A_{2^{i-1}+1}, \ldots, A_{2^{i}-1}$$
Then we can form a Hamiltonian path
$$A_{2^{k-1}} \leftrightarrow A_{1} \leftrightarrow A_{2^{k-1}+1} \leftrightarrow A_{2} \leftrightarrow A_{2^{k-1}+2} \leftrightarrow A_{3} \leftrightarrow \ldots \leftrightarrow A_{n},$$
which does not contain an edge of colour $k$. This is a contradiction, and therefore $n \geqslant 2^{k}$.