Problem 1664

The answer is $\frac{3}{2}$ for $n \neq 4$ and $\frac{19}{12}$ for $n = 4$.

Note that for any distinct cities $A$ and $B$, exactly one of $d(A, B)$ and $d(B, A)$ is $1$, while the other is at least $2$. Thus it follows that $d(A, B) + d(B, A) \geq 3$. The average for this pair is at least $\frac{3}{2}$. Therefore, by considering all pairs of distinct cities, the average must be at least $\frac{3}{2}$. Equality holds if and only if $d(A, B) + d(B, A) = 3$ for all pairs of cities $A$ and $B$.

Now we show that this average is attainable for $n \neq 4$ by induction.

First of all, when $n = 3$, the average is attainable if there is a road from $A$ to $B$, $B$ to $C$, $C$ to $A$.

For $n = 6$, consider the map given by the following table:

| | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 1 | 0 | 0 |
| B | 0 | 0 | 1 | 0 | 1 | 1 |
| C | 0 | 0 | 0 | 1 | 1 | 1 |
| D | 0 | 1 | 0 | 0 | 0 | 1 |
| E | 1 | 0 | 0 | 1 | 0 | 0 |
| F | 1 | 0 | 0 | 0 | 1 | 0 |

(Here a ‘1’ in the $AB$-entry indicates a road from $A$ to $B$, etc., while a ‘0’ in the $AE$-entry indicates no direct road from $A$ to $E$, etc.). Using the table, we get the distance table:

| | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 1 | 2 | 2 |
| B | 2 | 0 | 1 | 2 | 1 | 1 |
| C | 2 | 2 | 0 | 1 | 1 | 1 |
| D | 2 | 1 | 2 | 0 | 2 | 1 |
| E | 1 | 2 | 2 | 1 | 0 | 2 |
| F | 1 | 2 | 2 | 2 | 1 | 0 |

So $d(X, Y) + d(Y, X) = 3$ for each pair of distinct cities $X$ and $Y$.

Assume when $n = k$, the average $\frac{3}{2}$ is attainable. Now, consider the case $n = k+2$. Label the $k+2$ cities by $A_1, A_2, \dots, A_n, X, Y$. By our assumption, there exists a way to build roads between $A_1, A_2, \dots, A_n$ such that $d(A_i, A_j) + d(A_j, A_i) = 3$ for all $1 \le i < j \le k$. We build a road from $A_i$ to $X$ for all $i$, a road from $Y$ to $A_i$ for all $i$, and a road from $X$ to $Y$. Thus,
$$\begin{aligned} d(X, Y) &= 1, \\ d(Y, X) &= 2 \quad (Y \to A_i \to X), \\ d(A_i, X) &= 1, \\ d(X, A_i) &= 2 \quad (X \to Y \to A_i), \\ d(A_i, Y) &= 2 \quad (A_i \to X \to Y), \\ d(Y, A_i) &= 1. \end{aligned}$$
Therefore, we see this road map produces an average distance of $\frac{3}{2}$ between any two cities.

By induction, the minimum average is attainable for all $n \ge 3$ except $n = 4$.

We first show that the average of $\frac{3}{2}$ is unattainable. Suppose on the contrary that this average is attainable. Let the four cities be $A_1, A_2, A_3, A_4$. Without loss of generality, assume there is a road from $A_1$ to $A_2$ and a road from $A_1$ to $A_3$. Since the distance from $A_2$ to $A_1$ is $2$, there must be a road from $A_2$ to $A_4$, and a road from $A_4$ to $A_1$. Similarly, there must be a road from $A_3$ to $A_4$. We may assume there is a road from $A_2$ to $A_3$. But then the distance from $A_3$ to $A_2$ is $3$. This is a contradiction.

The next smallest possible average is $\frac{3 \times C_2^4 + 1}{4 \times 3} = \frac{19}{12}$. The above construction actually attains an average of $\frac{19}{12}$. Thus the minimum average of $d(A, B)$ is $\frac{19}{12}$ for $n = 4$. This completes the proof.