IMO Shortlist 2013 A4

I will show the general the answer to be $n^2$ . When $n=2013$ this gives 4052169.

We will prove that $a_1+a_2+...+a_n\leq n^2$ by contradiction. First of all, if $a_1+a_2+...+a_n> n^2$ then one of the $n$ terms must be greater than $n$ . Let $a_k$ be the first term which satisfies this property. We will show that $k>1$ . Using the fact that $a_1\leq a_2\leq ... \leq a_n$ , $n = n+1-1 \geq a_{a_1} \geq a_1$ . If $a_1 = n$ then $a_n = a_{a_1} \leq n$ and because $a_n \geq a_1$ , $a_n=n$ . Since $a_1\leq a_i \leq a_n$ for all $i$ , we must have that $a_i = n$ . Thus $a_1+a_2+...+a_n = n^2$ , a contradiction. This means that $a_1 < n$ so $k > 1$ .

Now by the definition of $k$ , $a_1, a_2, ..., a_{k-1} \leq n$ and $a_k, a_{k+1}, ..., a_n \geq a_k \geq n+1$ . Since $a_{a_1} \leq n+1-1 = n$ , we know that $a_1$ must have a remainder of at most $k-1$ when divided by $n$ . $a_1 \leq n$ so we can go further and state that $a_1$ is at most $k-1$ . Now let $a_i$ be the first term so that $a_i \geq k$ . Now $a_1, a_2, ..., a_{i-1} \leq k-1$ , $k \leq a_i, a_{i+1}, ..., a_{k-1} \leq n$ , and $n+k-1 \geq n+a_1\geq a_n, a_{n-1}, ..., a_k \geq n+1$ .

Now $i\leq k$ since $a_k>n\geq k$ . If $i=k$ then our first $k-1$ terms are at most $k-1$ and the remaining $n-k+1$ terms are at most $a_1+n \leq n+k-1$ , giving an upper bound of $(n-(k-1))(n+(k-1))+(k-1)^2 = n^2$ on the sum of the terms. This is impossible since we assumed the sum to be greater than $n^2$ . Thus $i<k$ and $i>1$ since $a_1\leq k-1$ .

First of all the first $i-1$ terms are at most $k-1$ and the $i$ to $k-1$ -th terms are just equal to themselves. Now the $k$ through $a_i$ -th terms are all at most $a_{a_i} \leq n+i-1$ (the $a_i$ -th term is exactly $a_{a_i}$ ). Next the $a_i+1$ through $a_{i+1}$ -th terms are at most $a_{a_{i+1}} \leq n+i$ . This repeats until we get that the $a_{k-2}+1$ through $a_{k-1}$ -th terms are at most $a_{a_{k-1}} \leq n+k-2$ . Finally, the $a_{k-1}+1$ through the $n$ -th terms are at most $a_1+n \leq n+k-1$ . Thus the sum of all $n$ terms is at most $(i-1)(k-1)+\sum_{l=i}^{l=k-1}{a_l}+(a_i-(k-1))(n+(i-1))+\sum_{l = i}^{l=k-2}{(a_{l+1}-a_l)(n+l)}+(n-a_{k-1})(n+(k-1))$ Now $(a_i-(k-1))(n+(i-1))+\sum_{l = i}^{l=k-2}{(a_{l+1}-a_l)(n+l)}+(n-a_{k-1})(n+(k-1))$ telescopes into $n(n+(k-1))-\sum_{l=i}^{l=k-1}{a_l}-(k-1)(n+(i-1))$ so we can use this substitution to reduce our original value down to $(i-1)(k-1)+\sum_{l=i}^{l=k-1}{a_l}+n(n+(k-1))-\sum_{l=i}^{l=k-1}{a_l}-(k-1)(n+(i-1))$ $(i-1)(k-1)+n(n+(k-1))-(k-1)(n+(i-1))$ With some expanding this can be compressed into $(i-1)(k-1)+n(n+(k-1))-(k-1)(n+(i-1))= (i-1)(k-1)+n^2+n(k-1)-(k-1)n-(k-1)(i-1)=n^2$ Thus the sum of all of the terms is at most $n^2$ , a contradiction. This completes our proof so $a_1+a_2+...+a_n\leq n^2$ . Q.E.D.