Problem 2145

Let $T(n)$ be smallest number of new links so that the property holds. By using mathematical induction we will show that for all $n \ge 2$,
$$T(n) \le 3(n-1) \log_2 \log_2 n.$$

It is trivial that $T(2) = 0 \le 3(2-1)\log_2\log_2 2$, and $T(3) = 0 \le 3(3-1)\log_2\log_2 3$.
Let $n \ge 4$. When $2 \le m < n$, suppose that
$$T(m) \le 3(m - 1) \log_2 \log_2 m. \qquad (1)$$
Now we will show that (1) is true when $m = n$. Let $k \ge 2$ be an integer so that $k^2 \le n < (k+1)^2$. Since $T$ is an increasing function, $T(n) \le T((k+1)^2 - 1)$.
Imagine a partition of the webpages $\{1, 2, \dots, (k+1)^2 - 1\}$ into $(k+1)$ many groups of $(k+1)$ many webpages. Only the last group has $k$ many webpages. Precisely, $\{1, 2, 3, \dots, k+1\}$ is the first group, $\{k+2, k+3, \dots, 2(k+1)\}$ is the second group, and $\{k(k+1)+1, k(k+1)+2, \dots, (k+1)^2 - 1\}$ is the last group.
Now, for each $r = 0, 1, 2, \dots, k-1$, for all $1 \le i \le k-1$, add a new link from the webpage $r(k+1)+i$ to the webpage $r(k+1)+(k+1)$. The total number of new links of this type is $(k-1)k$. Similarly for each $r = 1, 2, \dots, k$, for all $2 \le i \le k$, add a new link from the webpage $r(k+1)$ to the webpage $r(k+1)+i$. The total number of new links of this type is also $(k-1)k$. Also add $\binom{k}{2}$ many new links between all two webpages whose numbers are multiples of $(k+1)$.
Using these new links, any two webpages that belong to different groups are connected by at most 3 links, by taking webpages whose numbers are multiples of $(k+1)$ as webpages in the middle of the link path. From the definition of $T(k)$, if we add $T(k)$ many links to the $k$ many webpages in each group, the required property holds. Hence,
$$T(n) \le T(k^2 + 2k) \le 2k(k-1) + \frac{k(k-1)}{2} + (k+1)T(k).$$
Since
$$3(k^2 - 1) \log_2 \log_2 k^2 \le 3(n - 1) \log_2 \log_2 n.$$
to finish the induction argument, it is enough to show that
$$2k(k-1) + \frac{k(k-1)}{2} + (k+1)T(k) \le 3(k^2 - 1) \log_2 \log_2 k^2. \qquad (2)$$
By applying the induction hypothesis on $T(k)$ to (2), it is enough to show that
$$2k(k-1) + \frac{k(k-1)}{2} + (k+1)3(k-1)\log_2\log_2 k \le 3(k^2-1)\log_2\log_2 k^2. \quad (3)$$
(3) is equivalent to the following, which is true for all $k \ge 2$.
$$\begin{align*} & \iff 2k^2 - 2k + \frac{k^2 - k}{2} \le 3(k^2 - 1) \\ & \iff \frac{k^2}{2} + \frac{5}{2}k - 3 \ge 0. \end{align*}$$
Hence (1) holds for $m = n$, which proves the mathematical induction. $\square$