Problem 2

Emperor Zorg wishes to found a colony on a new planet. Each of the $n$ cities he establishes there must speak exactly one of the 2020 official languages of the empire. Some of the cities in the colony will be connected by direct air routes, each of which can be used in both directions. The emperor has set the cost of the ticket for each route at 1 galactic credit. He wishes that, given any two cities speaking the same language, it should always be possible to travel from one to the other via these air routes, and that the cheapest travel between these two cities costs exactly 2020 galactic credits.

For which values of $n$ can Emperor Zorg realize his dream?

## $\S$
Solution $\mathbf{n}^{\circ} 1$

In the following, we will set $k=2020$, and then represent Emperor Zorg's dream colony by an undirected graph with $n$ vertices, which are colored with one of the integers $0,1, \ldots, k-1$.

First, any integer $n \leqslant 2 k$ works: indeed, it suffices to color the integers from 1 to $n$ by assigning the integer $i$ the color $i(\bmod k)$, and then adding an edge between each pair of adjacent integers. Similarly, the integer $n=3 k$ works: it suffices to color the integers from 1 to $n$ by assigning the integer $i$ the color $i(\bmod k)$, and then adding an edge between each pair of adjacent integers as well as between the integers 1 and $n$.

Conversely, let $n \geqslant 2 k+1$ be a suitable value: we will prove that $n=3 k$. First, the pigeonhole principle indicates that a color, say 0, has been used to color at least three vertices of the graph. We then consider a path $v_{0}-v_{1}-\ldots-v_{k}$ between two vertices of color 0. The other vertices $v_{i}$ are all of different colors, and, by renumbering the colors if necessary, we assume that the vertex $v_{i}$ has been colored with the color $i$.

Now suppose that one of the vertices $v_{i}$, with $1 \leqslant i \leqslant k-1$, has a neighbor $w$ other than $v_{i-1}$ and $v_{i+1}$. If $w$ is another vertex $v_{j}$, going directly from $v_{i}$ to $v_{j}$ allows us to go directly from $v_{0}$ to $v_{k}$ in fewer than $k$ steps, which is impossible. Otherwise, let $j$ be the color of $w$. Then $w$ is at most $1+|j-i|$ away from $v_{j}$, so $|j-i| \geqslant k-1$. Since $1 \leqslant i \leqslant k-1$ and $0 \leqslant i \leqslant k-1$, this means that $i=k-1$ and $j=0$. But then $w$ is at most 2 away from $v_{k}$, which is impossible since $k \geqslant 3$.

We then consider a path of length $k$ between $v_{k}$ and a third vertex of color 0. This path cannot coincide with the path $v_{k}-v_{k-1}-\ldots-v_{0}$. Therefore, it is a new path $v_{k}-v_{k+1}-\ldots-v_{2 k}$, where the $2 k+1$ vertices $v_{i}$ are all distinct. Then, by an immediate induction on $i$, we observe that $v_{2 k-i}$ is of color $k-i$. Similarly, there is a path of length $k$ between $v_{2 k}$ and $v_{0}$, which cannot use any of the vertices $v_{1}, \ldots, v_{2 k-1}$. We therefore have a cycle $v_{0}-v_{1}-\ldots-v_{3 k-1}-v_{0}$, where each vertex $v_{i}$ is of color $i$.

We have already mentioned that the only neighbors of $v_{1}$ were $v_{0}$ and $v_{2}$. But then, for similar reasons, the only neighbors of each vertex $v_{i}$ are $v_{i-1}(\bmod 3 k)$ and $v_{i+1}(\bmod 3 k)$. Our cycle thus forms a connected component of the graph. Moreover, any vertex of the graph is at most $k$ away from one of the vertices of the cycle: the graph is therefore connected. Consequently, our cycle contains all the vertices of the graph, which means that $n=3 k$.

## $\S$