IMO 3J, Independent Study 1

Consider the following general proposition:
Let $N$ be a positive integer, and let $a_1, a_2, \dots, a_{2N-1}$ be positive integers satisfying the following conditions:
• $a_1, a_2, \dots, a_{2N-1}$ is a permutation of $1, 2, \dots, 2N-1$
• $|a_1 - a_2|, |a_2 - a_3|, \dots, |a_{2N-2} - a_{2N-1}|$ is a permutation of $1, 2, \dots, 2N-2$
Then $a_1 + a_{2N-1} \ge N + 1$, from which it follows that $\max(a_1, a_{2N-1}) \ge \lfloor \frac{N+1}{2} \rfloor$. The original problem is the case $N = 62$.

We prove the general proposition. Define the score of a number $a \in \{1, 2, \dots, 2N-1\}$ to be
$$s(a) := |a - N|.$$
By the triangle inequality we know
$$|a - b| \ge |a - N| + |N - b| = s(a) + s(b).$$
Considering the sum $|a_1 - a_2| + |a_2 - a_3| + \dots + |a_{2N-2} - a_{2N-1}|$, we obtain
$$\begin{aligned} (N-1)(2N-1) &= |a_1 - a_2| + |a_2 - a_3| + \dots + |a_{2N-2} - a_{2N-1}| \\ &\le 2(s(a_1) + s(a_2) + \dots + s(a_{2N-1})) - (s(a_1) + s(a_{2N-1})) \\ &= 2N(N-1) - (s(a_1) + s(a_{2N-1})). \end{aligned}$$
Here the last equality holds because $s(a_1), s(a_2), \dots, s(a_{2N-1})$ is a permutation of $0, 1, 1, 2, 2, \dots, N-1, N-1$.

Hence, $s(a_1) + s(a_{2N-1}) \le 2N(N-1) - (N-1)(2N-1) = N-1$. From this we obtain
$$(N - a_1) + (N - a_{2N-1}) \le s(a_1) + s(a_{2N-1}) \le N - 1,$$
that is, $a_1 + a_{2N-1} \ge N + 1$.

Therefore $\max(a_1, a_{2N-1}) \ge \lceil \frac{N+1}{2} \rceil$. For $N = 62$, $\lceil \frac{62+1}{2} \rceil = 32$, so $\max(a_1, a_{123}) \ge 32$.