Question 194
When there is a link from a webpage $i$ to a webpage $j$, you can move from the webpage $i$ to the webpage $j$ directly. For $n \ge 2$, there are $n$ many webpages numbered from $1$ to $n$, and for all $i \in \{1, 2, \dots, n-1\}$, there is a link from the webpage $i$ to the webpage $(i+1)$.
Now you are allowed to add new links to the webpages so that new links can connect two webpages from $i$ to $j$ when $i \lt j$. Prove that there exist a way to add at most $3(n-1) \log_2(\log_2 n)$ many such new links so that for any two integers $1 \le i \lt j \le n$, you can move from the webpage $i$ to the webpage $j$ using at most 3 links.
Now you are allowed to add new links to the webpages so that new links can connect two webpages from $i$ to $j$ when $i \lt j$. Prove that there exist a way to add at most $3(n-1) \log_2(\log_2 n)$ many such new links so that for any two integers $1 \le i \lt j \le n$, you can move from the webpage $i$ to the webpage $j$ using at most 3 links.