Writeup: IMO Shortlist 2001 C1

19 Apr, 2025

Problem Statement:

Let $A = (a_{1}, a_{2}, \dots, a_{2001})$ be a sequence of positive integers. Let $m$ be the number of 3-element subsequences $(a_{i}, a_{j}, a_{k})$ with $1 \leq i < j < k \leq 2001$ , such that $a_{j} = a_{i} + 1$ and $a_{k} = a_{j} + 1$ . Considering all such sequences $A$ , find the greatest value of $m$ .

My Solution:

Note that sorting $A$ can't destroy any already valid 3-element subsequences and can only create new ones. So there will be a sorted sequence $A$ achieving a value of $m$ .

Then $A$ can be divided into blocks of identical elements. Let the first (and smallest) block have length $b_{0}$ , then number them ascending $b_{1}, b_{2}, . . ., b_{n}$ . It's apparent that the number of blocks is bounded above by

b_{0} b_{1} b_{2} + b_{1} b_{2} b_{3} + \dots + b_{n - 2} b_{n - 1} b_{n} .

Note that replacing adding converting all the elements in block $b_{0}$ to add on to the block $b_{3}$ can only increase this upper bound.

If we keep repeating this process, eventually we are left with 3 blocks bounded above by $b_{0} b_{1} b_{2}$ with the constraint $b_{0} + b_{1} + b_{2} = 2001$ . By $A M - G M$ the maximum number $m$ must therefore be $667^{3}$ where we have $667$ ones, $667$ two's, and $667$ three's as a valid construction.