23rd Korean Mathematical Olympiad Final Round

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.(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 $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ 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.(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.(3)$$ (3) is equivalent to the following, which is true for all $k\ge 2$. $$\begin{array}{rl}& ⟺2k^2-2k+\frac{k^2-k}{2}\le 3(k^2-1)\\ & ⟺\frac{k^2}{2}+\frac{5}{2}k-3\ge 0.\end{array}$$ Hence (1) holds for $m=n$, which proves the mathematical induction. $\square$