25th Turkish Mathematical Olympiad

Let us solve more general problem: Let $x_0,x_1,\dots ,x_n$ be a non-decreasing sequence of positive integers. Suppose that $x_0=1$ and the subsequence $x_1,x_2,\dots ,x_{2017}$ contains exactly $m$ distinct positive integers. Show that $$\sum _{i=2}^n{x}_i(x_i-x_{i-2})\ge m^2-2.$$ Since the sequence is non-decreasing we have $x_i-x_{i-2}-1\ge -1$ for $i\ge 2$. On the other hand, $x_i-x_{i-2}-1=-1$ implies $x_i=x_{i-1}$. Hence for $i=2,3,\dots ,n$ we obtain $$(x_i-x_{i-2}-1)(x_i-x_{i-1})\ge 0(1)$$

$$x_i^2-x_i{x}_{i-2}+x_{i-1}{x}_{i-2}-x_i{x}_{i-1}\ge x_i-x_{i-1}.$$ Summing up the last inequality for $i=2,3,\dots ,n$ side by side, we get $$\sum _{i=2}^n{x}_i(x_i-x_{i-2})\ge x_n(1+x_{n-1})-2x_1.$$ Since the set $\{x_1,x_2,\dots ,x_n\}$ includes $m$ distinct elements, we have $$x_n\ge x_1+m-1$$ $$x_{n-1}\ge x_1+m-2.$$ It follows that $$\sum _{i=2}^n{x}_i(x_i-x_{i-2})\ge (x_1+m-1{)}^2-2x_1(2)$$ $$(x_1+m-1{)}^2-2x_1-(m^2-2)=(x_1-1)(x_1+2m-3)\ge 0.(3)$$ Now (2) and (3) prove the required inequality. In the case of equality, we must have $$x_1=1,x_n=m,x_{n-1}=m-1$$ and for all $i=2,3,\dots ,n$ $$x_i-x_{i-2}=1\text{or}{x}_i=x_{i-1}.$$ Since $x_n\ne x_{n-1}$ we get $x_{n-2}=m-1$. For a $2\le j\le n$, since $$x_j-x_{j-1}>1\Rightarrow x_j-x_{j-2}\ge x_j-x_{j-1}>1,x_j\ne x_{j-1}$$ the difference between two consecutive terms can be at most 1. Furthermore, since $$x_j-x_{j-1}=x_{j-1}-x_{j-2}=1\Rightarrow x_j-x_{j-2}=2>1,x_j\ne x_{j-1}$$ +1 increases can not be in the neighbouring consecutive pairs. On the other hand, all conditions are satisfied if +1 increases are not in the neighbouring consecutive pairs. Therefore we need to count all possible places of +1 increases. Corresponding indices of the sequence can be in between 2 and $n-2$ and hence there are $n-3$ possibilities. Total number of +1 increases is $m-2$. This problem is equivalent to placing $m-2$ identical balls into $n-3$ boxes such that there are no neighbouring boxes both including a ball. The answer is $\left(\genfrac{}{}{0ex}{}{n-m}{m-2}\right)$ for $n\ge 2m-2\ge 2$, and 0 otherwise. In our case the answer is $\left(\genfrac{}{}{0ex}{}{1992}{23}\right)$.