International Mathematical Olympiad Shortlisted Problems

First, we claim that $$\begin{array}{c}{a}_i⩽n+i-1\text{ for }i=1,2,\dots ,n.\end{array}\text{\hspace{1em}(3)}$$ Assume contrariwise that $i$ is the smallest counterexample. From $a_n⩾a_{n-1}⩾\cdots ⩾a_i⩾n+i$ and $a_{a_i}⩽n+i-1$, taking into account the periodicity of our sequence, it follows that $$\begin{array}{c}{a}_i\text{ cannot be congruent to }i,i+1,\dots ,n-1\text{, or }n(\mathrm{mod}n)\text{. }\end{array}\text{\hspace{1em}(4)}$$ Thus our assumption that $a_i⩾n+i$ implies the stronger statement that $a_i⩾2n+1$, which by $a_1+n⩾a_n⩾a_i$ gives $a_1⩾n+1$. The minimality of $i$ then yields $i=1$, and (4) becomes contradictory. This establishes our first claim.

In particular we now know that $a_1⩽n$. If $a_n⩽n$, then $a_1⩽\cdots ⩽a_n⩽n$ and the desired inequality holds trivially. Otherwise, consider the number $t$ with $1⩽t⩽n-1$ such that $$\begin{array}{c}{a}_1⩽a_2⩽\dots ⩽a_t⩽n<a_{t+1}⩽\dots ⩽a_n\end{array}\text{\hspace{1em}(5)}$$ Since $1⩽a_1⩽n$ and $a_{a_1}⩽n$ by (2), we have $a_1⩽t$ and hence $a_n⩽n+t$. Therefore if for each positive integer $i$ we let $b_i$ be the number of indices $j\in \{t+1,\dots ,n\}$ satisfying $a_j⩾n+i$, we have $$b_1⩾b_2⩾\dots ⩾b_t⩾b_{t+1}=0$$ Next we claim that $a_i+b_i⩽n$ for $1⩽i⩽t$. Indeed, by $n+i-1⩾a_{a_i}$ and $a_i⩽n$, each $j$ with $a_j⩾n+i$ (thus $a_j>a_{a_i}$ ) belongs to $\left\{a_i+1,\dots ,n\right\}$, and for this reason $b_i⩽n-a_i$.

It follows from the definition of the $b_i$\,s and (5) that $$a_{t+1}+\dots +a_n⩽n(n-t)+b_1+\dots +b_t.$$ Adding $a_1+\dots +a_t$ to both sides and using that $a_i+b_i⩽n$ for $1⩽i⩽t$, we get $$a_1+a_2+\cdots +a_n⩽n(n-t)+nt=n^2$$ as we wished to prove.

---

Alternative solution.

In the first quadrant of an infinite grid, consider the increasing "staircase" obtained by shading in dark the bottom $a_i$ cells of the $i$th column for $1⩽i⩽n$. We will prove that there are at most $n^2$ dark cells.

To do it, consider the $n\times n$ square $S$ in the first quadrant with a vertex at the origin. Also consider the $n\times n$ square directly to the left of $S$. Starting from its lower left corner, shade in light the leftmost $a_j$ cells of the $j$th row for $1⩽j⩽n$. Equivalently, the light shading is obtained by reflecting the dark shading across the line $x=y$ and translating it $n$ units to the left. The figure below illustrates this construction for the sequence $6,6,6,7,7,7,8,12,12,14$.



We claim that there is no cell in $S$ which is both dark and light. Assume, contrariwise, that there is such a cell in column $i$. Consider the highest dark cell in column $i$ which is inside $S$. Since it is above a light cell and inside $S$, it must be light as well. There are two cases:

Case 1. $a_i⩽n$

If $a_i⩽n$ then this dark and light cell is $(i,a_i)$, as highlighted in the figure. However, this is the $(n+i)$-th cell in row $a_i$, and we only shaded $a_{a_i}<n+i$ light cells in that row, a contradiction.

Case 2. $a_i⩾n+1$

If $a_i⩾n+1$, this dark and light cell is $(i,n)$. This is the $(n+i)$-th cell in row $n$ and we shaded $a_n⩽a_1+n$ light cells in this row, so we must have $i⩽a_1$. But $a_1⩽a_{a_1}⩽n$ by (1) and (2), so $i⩽a_1$ implies $a_i⩽a_{a_1}⩽n$, contradicting our assumption.

We conclude that there are no cells in $S$ which are both dark and light. It follows that the number of shaded cells in $S$ is at most $n^2$.

Finally, observe that if we had a light cell to the right of $S$, then by symmetry we would have a dark cell above $S$, and then the cell $(n,n)$ would be dark and light. It follows that the number of light cells in $S$ equals the number of dark cells outside of $S$, and therefore the number of shaded cells in $S$ equals $a_1+\cdots +a_n$. The desired result follows.

---

Alternative solution.

As in Solution 1, we first establish that $a_i⩽n+i-1$ for $1⩽i⩽n$. Now define $c_i=\max \left(a_i,i\right)$ for $1⩽i⩽n$ and extend the sequence $c_1,c_2,\dots$ periodically modulo $n$. We claim that this sequence also satisfies the conditions of the problem.

For $1⩽i<j⩽n$ we have $a_i⩽a_j$ and $i<j$, so $c_i⩽c_j$. Also $a_n⩽a_1+n$ and $n<1+n$ imply $c_n⩽c_1+n$. Finally, the definitions imply that $c_{c_i}\in \left\{a_{a_i},a_i,a_i-n,i\right\}$ so $c_{c_i}⩽n+i-1$ by (2) and (3). This establishes (1) and (2) for $c_1,c_2,\dots$.

Our new sequence has the additional property that $$\begin{array}{c}{c}_i⩾i\text{ for }i=1,2,\dots ,n\end{array}\text{\hspace{1em}(6)}$$ which allows us to construct the following visualization: Consider $n$ equally spaced points on a circle, sequentially labelled $1,2,\dots ,n(\mathrm{mod}n)$, so point $k$ is also labelled $n+k$. We draw arrows from vertex $i$ to vertices $i+1,\dots ,c_i$ for $1⩽i⩽n$, keeping in mind that $c_i⩾i$ by (6). Since $c_i⩽n+i-1$ by (3), no arrow will be drawn twice, and there is no arrow from a vertex to itself. The total number of arrows is $$\text{ number of arrows }=\sum _{i=1}^n\left(c_i-i\right)=\sum _{i=1}^n{c}_i-\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)$$ Now we show that we never draw both arrows $i\to j$ and $j\to i$ for $1⩽i<j⩽n$. Assume contrariwise. This means, respectively, that $$i<j⩽c_i\text{ and }j<n+i⩽c_j.$$ We have $n+i⩽c_j⩽c_1+n$ by (1), so $i⩽c_1$. Since $c_1⩽n$ by (3), this implies that $c_i⩽c_{c_1}⩽n$ using (1) and (3). But then, using (1) again, $j⩽c_i⩽n$ implies $c_j⩽c_{c_i}$, which combined with $n+i⩽c_j$ gives us that $n+i⩽c_{c_i}$. This contradicts (2).

This means that the number of arrows is at most $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, which implies that $$\sum _{i=1}^n{c}_i⩽\left(\genfrac{}{}{0ex}{}{n}{2}\right)+\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)=n^2.$$ Recalling that $a_i⩽c_i$ for $1⩽i⩽n$, the desired inequality follows.