Taiwan IMO Selection Camp

Define $d(a, b)$ to be the distance between cities $a$ and $b$, and let
$$S_i(a) = \{c : d(a, c) = i\}$$
be the set of cities whose distance from city $a$ is exactly $i$.

We proceed by contradiction: suppose there exists a city $x$ such that $D = S_4(x)$ satisfies $|D| \geq 2551$. Let $A = S_1(x)$. We say that a set $A'$ is essential with respect to $A$ if and only if every city in $D$ can reach $x$ in 4 flights while passing through some city of $A'$ along the way (for example, $A$ is of course essential with respect to itself.) In other words, every city of $D$ is at distance exactly 3 from some city of $A'$, that is, $D \subset \bigcup_{a \in A'} S_3(a)$.

Consider an essential set $A^*$ with the smallest number of cities, and let $m = |A^*|$. Since
$$m(101 - m) \leq 50 \times 51 = 2550,$$
there must exist a city $a \in A^*$ such that $|S_3(a) \cap D| \geq 102 - m$ (otherwise $2551 \geq |D| \leq \sum_{a \in A^*} |S_3(a)| \leq m \times (101 - m) \leq 2550$, a contradiction!). But by the hypothesis, $|S_3(a)| \leq 100$,

so $S_3(a)$ contains at most $100 - (102 - m) = m - 2$ cities whose distance from $c$ is at most 3. Let $T = \{c \in S_3(a) : d(x,c) \le 3\}$ be the set of these cities, so we have $|T| \le m - 2$.

We will now show that $|T| \ge m - 1$, thereby obtaining a contradiction. Take any $a \in A^*$, and let $A_a = A^* \setminus \{a\}$.
Since $A^*$ is minimal, for each $y \in A_a$ there must exist a city $d_y \in D$ such that any flight sequence connecting $x$ and $d_y$ must pass through $y$. Therefore $x$ and $d_y$ can be connected in the form $x - y - b_y - c_y - d_y$; note that $d(x, b_y) = 2$ and $d(x, c_y) = 3$ (since $A^*$ is minimal.) Since $|A_a| = m - 1$, there are altogether $2(m - 1)$ cities of the form $b_y, c_y$.

Lemma 1. All the $b_y$'s and $c_y$'s are distinct.
Proof: Since $d(x, b_y) = 2$ and $d(x, c_z) = 3$, $b_y$ and $c_z$ must be different. Also, if $y \ne z$ but $b_y = b_z$, then there would exist $x - y - b_z - c_z - d_z$; but this would contradict the way $d_z$ was originally constructed, so we must have $b_y \ne b_z$. Similarly, if $y \ne z$, then $c_y \ne c_z$. Hence $b_y$ and $c_y$ give $2(m - 1)$ distinct cities.

Lemma 2. For each $y \in A_a$, one of $b_y$ and $c_y$ must be at distance 3 from $a$, and therefore belongs to $T$.
Proof: Since there is a flight sequence $a - x - y$, $d(a, y) \le 2$. On the other hand, clearly $d(a, d_y) \ge d(x, d_y) - d(x, a) = 3$. Moreover, by the choice of $d_y$ we know $d(a, d_y) \ne 3$, so $d(a, d_y) > 3$. Finally, note that $d(a, y)$, $d(a, b_y)$, $d(a, c_y)$, $d(a, d_y)$ each differ from the next by at most 1, with the first term less than 3 and the last term greater than 3, so one of $d(a, b_y)$ and $d(a, c_y)$ must equal 3. This completes the proof.

Combining the two lemmas above, we know $|T| \ge m - 1$, which contradicts $|T| \le m - 2$. Contradiction!