Taiwan IMO Selection Camp

The claimed maximal value is achieved at
$$a_1 = a_2 = \cdots = a_{2016} = 1, \quad a_{2017} = \frac{a_{2016} + \cdots + a_0}{2017} = 1 - \frac{1}{2017},$$
$$a_{2018} = \frac{a_{2017} + \cdots + a_1}{2017} = 1 - \frac{1}{2017^2}.$$

Now we need to show that this value is optimal. For brevity, we use the notation
$$S(n, k) = a_{n-1} + a_{n-2} + \cdots + a_{n-k} \text{ for nonnegative integers } k \le n.$$
In particular, $S(n, 0) = 0$ and $S(n, 1) = a_{n-1}$. In these terms, for every integer $n \ge 2$ there exists a positive integer $k \le n$ such that $a_n = S(n, k)/k$.
For every integer $n \ge 1$ we define
$$M_n = \max_{1 \le k \le n} \frac{S(n, k)}{k}, \quad m_n = \min_{1 \le k \le n} \frac{S(n, k)}{k}, \quad \text{and} \quad \Delta_n = M_n - m_n \ge 0.$$
By definition, $a_n \in [m_n, M_n]$ for all $n \ge 2$; on the other hand,
$$a_{n-1} = \frac{S(n, 1)}{1} \in [m_n, M_n].$$
Therefore,
$$a_{2018} - a_{2017} \le M_{2018} - m_{2018} = \Delta_{2018},$$

Also by definition, for any $0 < k \le n$ we have
$$km_n \le S(n, k) \le kM_n;$$
notice that these inequalities are also valid for $k = 0$.

Claim 1. For every $n > 2$, we have $\Delta_n \le \frac{n-1}{n}\Delta_{n-1}$.

Proof. Choose positive integers $k, \ell \le n$ such that $M_n = S(n, k)/k$ and $m_n = S(n, \ell)/\ell$. We have
$$S(n, k) = a_{n-1} + S(n-1, k-1),$$
so
$$\begin{aligned} k(M_n - a_{n-1}) &= S(n, k) - ka_{n-1} = S(n-1, k-1) - (k-1)a_{n-1} \\ &\le (k-1)(M_{n-1} - a_{n-1}), \end{aligned}$$
since
$$S(n-1, k-1) \le (k-1)M_{n-1}.$$
Similarly, we get
$$\ell(a_{n-1} - m_n) = (\ell - 1)a_{n-1} - S(n-1, \ell-1) \le (\ell - 1)(a_{n-1} - m_{n-1}).$$
Since $m_{n-1} \le a_{n-1} \le M_{n-1}$ and $k, \ell \le n$, the obtained inequalities yield
$$\begin{aligned} M_n - a_{n-1} &\le \frac{k-1}{k}(M_{n-1} - a_{n-1}) \le \frac{n-1}{n}(M_{n-1} - a_{n-1}) \quad \text{and} \\ a_{n-1} - m_n &\le \frac{\ell-1}{\ell}(a_{n-1} - m_{n-1}) \le \frac{n-1}{n}(a_{n-1} - m_{n-1}). \end{aligned}$$

$$\begin{align*} \Delta_n &= (M_n - a_{n-1}) + (a_{n-1} - m_n) \\ &\le \frac{n-1}{n} \left( (M_{n-1} - a_{n-1}) + (a_{n-1} - m_{n-1}) \right) \\ &= \frac{n-1}{n} \Delta_{n-1}. \end{align*}$$
$$Back to the problem, if \$a_n = 1\$ for all \$n \le 2017\$, then \$a_{2018} \le 1\$ and hence \$a_{2018} - a_{2017} \le 0.\$ Otherwise, let \$2 \le q \le 2017\$ be the minimal index with \$a_q < 1\$. We have \$S(q, i) = i\$ for all \$i = 1, 2, \dots, q-1\$, while \$S(q, q) = q-1\$. Therefore, \$a_q < 1\$ yields$$
a_q = $\text{S(q,}$ q)}{q} = 1 - $\frac{1}{q}.$
$$Now we have$$
S(q + 1, i) = i - $\frac{1}{q} \text{}$ for } i = 1, 2, $\dots,$ q,
$$and$$
S(q + 1, q + 1) = q - $\frac{1}{q}.$
$$This gives us$$
$\text{m q+1 = S(q+1,}$ 1)}{1} = $\text{S(q+1,}$ q+1)}{q+1} = $\frac{q-1}{q} \quad \text{and}$
$$$$
$\text{M q+1 = S(q+1,}$ q)}{q} = $\text{q 2}$ - 1}{q^2},
$$so$$
$\Delta_{q+1} = M_{q+1} - m_{q+1} = \frac{(q-1)}{q^2}.$
$$$$

We present a different proof of the estimate $a_{2018} - a_{2017} \le \frac{2016}{2017^2}$.
We keep the same notations of $S(n, k)$, $m_k$ and $M_n$ from the previous solution.

Notice that $S(n, n) = S(n, n - 1)$, as $a_0 = 0$. Also notice that for $0 \le k \le l \le n$ we have
$$S(n, l) = S(n, k) + S(n - k, l - k).$$

Proof. Choose a positive integer $k \le n + 1$ such that
$$m_{n+1} = \frac{S(n+1, k)}{k}.$$
Then we have
$$km_{n+1} = S(n+1, k) = a_n + S(n, k-1) \ge m_n + (k-1)m_n = km_n,$$
which establishes the first inequality in the Claim. The proof of the second inequality is similar.

Proof. By Claim 2, we have
$$[m_k, M_k] \subseteq [m_{k-1}, M_{k-1}] \subseteq \dots \subseteq [m_n, M_n].$$
Since $a_k \in [m_k, M_k]$, the claim follows.

Proof. We use induction on $n$. The case $n = 2$ is routine. To perform the induction step, we need to prove the inequalities
$$\frac{S(n, n)}{n} \le \frac{S(n, k)}{k} \quad \text{and} \quad \frac{S(n, k)}{k} \le \frac{S(n, n-1)}{n-1} \qquad (1)$$
for every positive integer $k \le n$. Clearly, these inequalities hold for $k = n$ and $k = n - 1$, as $S(n, n) = S(n, n - 1) > 0$. In the sequel, we assume that $k < n - 1$.
Now the first inequality in Eq. (1) rewrites as
$$nS(n, k) \ge kS(n, n) = k(S(n, k) + S(n - k, n - k)),$$
or, cancelling the terms occurring on both parts, as
$$(n-k)S(n,k) \ge kS(n-k, n-k) \Leftrightarrow S(n,k) \ge k \cdot \frac{S(n-k, n-k)}{n-k}.$$
By the induction hypothesis, we have $S(n-k, n-k)/(n-k) = m_{n-k}$.
By Claim 3, we get $a_{n-i} \ge m_{n-k}$ for all $i = 1, 2, \dots, k$. Summing these $k$ inequalities we obtain
$$S(n, k) \ge k m_{n-k} = k \cdot \frac{S(n-k, n-k)}{n-k},$$
as required.

The second inequality in Eq. (1) is proved similarly. Indeed, this inequality is equivalent to
$$\begin{align*} (n-1)S(n,k) &\le kS(n,n-1) \\ \Leftrightarrow (n-k-1)S(n,k) &\le kS(n-k,n-k-1) \\ \Leftrightarrow S(n,k) &\le k \cdot \frac{S(n-k,n-k-1)}{n-k-1} = kM_{n-k}; \end{align*}$$
the last inequality follows again from Claim 3, as each term in $S(n, k)$ is at most $M_{n-k}$.

Now we can prove the required estimate for $a_{2018} - a_{2017}$. Set $N = 2017$. By Claim 4,
$$\begin{align*} a_{N+1} - a_N \le M_{N+1} - a_N &= \frac{S(N+1, N)}{N} - a_N \\ &= \frac{a_N + S(N, N-1)}{N} - a_N \\ &= \frac{S(N, N-1)}{N} - \frac{N-1}{N} \cdot a_N. \end{align*}$$
On the other hand, the same Claim yields
$$a_N \ge m_N = \frac{S(N, N)}{N} = \frac{S(N, N-1)}{N}.$$
Noticing that each term in $S(N, N-1)$ is at most 1, so
$$S(N, N-1) \le N-1,$$
we finally obtain
$$\begin{align*} a_{N+1} - a_N &\le \frac{S(N, N-1)}{N} - \frac{N-1}{N} \cdot \frac{S(N, N-1)}{N} \\ &= \frac{S(N, N-1)}{N^2} \le \frac{N-1}{N^2}. \end{align*}$$