IMO shortlist 1983/6 solution

24th IMO 1983 shortlist

Problem 6

The n positive integers a₁, a₂, ... , a_n have sum 2n+2. Show that we can find an integer r such that:
a_r+1 ≤ 3
a_r+1 + a_r+2 ≤ 5
...
a_r+1 + a_r+2 + ... + a_n + a₁ + ... + a_r-1 ≤ 2n-1
Note that a_r does not appear in the inequalities. Show that there are either one or two r for which the inequalities hold, and that if there is only one, then all the inequalities are strict.

For example, suppose n = 3, a₁ = 1, a₂ = 6, a₃ = 1. Then r = 1 and r = 3 do not work, but r = 2 does work: a₃ = 1 < 3, a₃ + a₁ = 2 < 5. So r is unique and the inequalities are strict.

Solution

Let s_i = a₁ + a₂ + ... + a_i - 2i. Let max s_i be attained for the first time at i = r. Suppose first that r = n. Then since ∑a_i = 2n+2, the maximum is 2. We have s_i < 2 for i < n, so a₁ + a₂ + ... + a_i ≤ 2i+1 for i = 1, 2, ... , n-1, which are the required inequalities. So suppose r < n. Then for k = r+1, ... , n we have a_r+1 + a_r+2 + ... + a_k = (a₁ + ... + a_k) - (a₁ + ... + a_r) = s_k - s_r + 2(k-r) ≤ 2(k-r) < 2(k-r)+1, as required. We also have a_r+1 + ... + a_n + s_i < a_r+1 + ... + a_n + s_r = 2n+2-2r, for i = 1, 2, ... , r-1. Hence a_r+1 + ... + a_n + a₁ + a₂ + ... + a_i < 2n+2-2r+2i. So a_r+1 + ... + a_n + a₁ + a₂ + ... + a_i ≤ 2n-2r+2i+1 = 2(n+i-r)+1, as required. That completes the proof that the inequalities hold.

Suppose that for some r the inequalities are all strict. wlog r = n, so that we have a₁ + ... + a_i ≤ 2i for i = 1, 2, ... , n-1. Then for any k < n we have a₁ + ... + a_k + a_k+1 + ... + a_n ≤ 2k + (a_k+1 + ... + a_n), so (a_k+1 + ... + a_n) ≥ 2n+2-2k > 2(n-k)+1 and so the inequalities do not all hold for k. Thus there is only one r for which the inequalities hold. Conversely, if the inequalities hold for r=n and k, then we have a₁ + ... + a_k = 2n+2 - (a_k+1 + ... + a_n) ≥ 2n+2 - (2(n-k)+1) = 2k+1. Hence (at least) one of the inequalities is not strict for r.

Suppose the inequalities hold for r < s < t. The same argument as above shows that a_r+1 + a_r+2 + ... + a_s = 2(s-r)+1, a_s+1 + ... + a_t = 2(t-s)+1 and a_t+1 + ... + a_r = 2(n-t+r)+1, so the sum of all the terms is 2n+3, not 2n+2. Contradiction.

Thanks to Lauri Ahlroth

24th IMO shortlist 1983