BMO 2024 | Problem 2 | Solution - 30 April 2024

Problem 2.
Let n≥k≥3 be integers. Show that for every integer sequence 1≤a₁<a₂<…<a_k≤n one can choose non-negative integers b₁,b₂,…,b_k , satisfying the following conditions:

0≤b_i≤n for each 1≤i≤k,
all the positive b_i are distinct,
the sums a_i+b_i, 1≤i≤k, form a permutation of the first k terms of a non-constant arithmetic progression.

Solution

For a solution involving induction.
We induct on n with the claim:
- For all $n \geq k \geq 3$ there exist $b_i$ which fulfil the problem condition as well as:
- either all $b_i$ are 0
- the only time we have $b_i$ = 0 is if $a_{k-s}= n-s$ in which case $b_t= 0$ for all $t \geq k-s$

The base case $n=3$ is obvious.
Assume it is true for $n=q$ , and now we prove it for $q+1$
Now obviously if $k=q+1$ the result is obvious. From here on assume $k<=q$ .
If $a_k<q+1$ then our $b_i$ exist by induction.

So now we have to show that our desired $b_i$ exist for a sequence $(a_1,... a_s, q-f, q-f +1,...,q+1)$ , $f$ could also be -1, whats important that starting from $a_k=q+1$ there exists an index $s$ such that $a_s< a_(s+1)-1$ . If this is not the case then the sequence is already an arithmetic progresion.

Now consider the $b_i$ for the sequence $(a_1,...a_s, a_{s+1}-1,a_{s+2}-1,...,q)$ . Notice by our induction claim , $b_i=0$ for $s+1<=i<=k$ and only these b. So now perform the following operation:
If $b_i=0$ , replace $a_i$ with $a_i +1$
Else replace $b_i$ with $b_i +1$ . It is not difficult to see that these $b_i$ work.;