IMO 1983 SL 6

Origin: CAN

Problem

Suppose that {x1, x2, . . . , xn} are positive integers for which x1 + x2 + \cdot \cdot \cdot + xn = 2(n + 1). Show that there exists an integer r with 0 \leqr \leqn −1 for which the following n −1 inequalities hold: xr+1 + \cdot \cdot \cdot + xr+i \leq2i + 1 \foralli, 1 \leqi \leqn −r; xr+1 + \cdot \cdot \cdot + xn + x1 + \cdot \cdot \cdot + xi \leq2(n −r + i) + 1 \foralli, 1 \leqi \leqr −1. Prove that if all the inequalities are strict, then r is unique and that otherwise there are exactly two such r.

Solution

The existence of r: Let S = {x1 + x2 + \cdot \cdot \cdot + xi −2i | i = 1, 2, . . . , n}. Let max S be attained for the first time at r′. If r′ = n, then x1 + x2 + \cdot \cdot \cdot + xi −2i < 2 for 1 \leqi \leqn −1, so one can take r = r′. Suppose that r′ < n. Then for l < n−r′ we have xr′+1+xr′+2+\cdot \cdot \cdot+xr′+l = (x1 + \cdot \cdot \cdot + xr′+l −2(r′ + l)) −(x1 + \cdot \cdot \cdot + xr′ −2r′) + 2l \leq2l; also, for i < r′ we have (xr′+1 + \cdot \cdot \cdot + xn) + (x1 + \cdot \cdot \cdot + xi −2i) < (xr′+1 + \cdot \cdot \cdot + xn) + (x1 + \cdot \cdot \cdot + xr′ −2r′) = (x1 + \cdot \cdot \cdot + xn) −2r′ = 2(n −r′) + 2 ⇒ xr′+1 + \cdot \cdot \cdot + xn + x1 + \cdot \cdot \cdot + xi \leq2(n + i −r′) + 1, so we can again take r = r′. For the second part of the problem, we relabel the sequence so that r = 0 works. Suppose that the inequalities are strict. We have x1 + x2 + \cdot \cdot \cdot + xk \leq2k, k = 1, . . . , n −1. Now, 2n + 2 = (x1 + \cdot \cdot \cdot + xk) + (xk+1 + \cdot \cdot \cdot + xn) \leq 2k + xk+1 + \cdot \cdot \cdot + xn ⇒xk+1 + \cdot \cdot \cdot + xn \geq2(n −k) + 2 > 2(n −k) + 1. So we cannot begin with xk+1 for any k > 0. Now assume that there is an equality for some k. There are two cases: (i) Suppose x1+x2+\cdot \cdot \cdot+xi \leq2i (i = 1, . . . , k) and x1+\cdot \cdot \cdot+xk = 2k+1, x1 +\cdot \cdot \cdot+xk+l \leq2(k +l)+1 (1 \leql \leqn−1−k). For i \leqk −1 we have xi+1+\cdot \cdot \cdot+xn = 2(n+1)−(x1+\cdot \cdot \cdot+xi) > 2(n−i)+1, so we cannot take r = i. If there is a j \geq1 such that x1 +x2 +\cdot \cdot \cdot+xk+j \leq2(k+j), then also xk+j+1 +\cdot \cdot \cdot+xn > 2(n−k −j)+ 1. If (\forallj \geq1) x1 +\cdot \cdot \cdot+xk+j = 2(k + j) + 1, then xn = 3 and xk+1 = \cdot \cdot \cdot = xn−1 = 2. In this case we directly verify that we cannot take r = k+j. However, we can also take r = k: for k+l \leqn−1, xk+1+\cdot \cdot \cdot+xk+l \leq2(k+l)+1−(2k+1) = 2l, also xk+1 +\cdot \cdot \cdot+xn = 2(n−k)+ 1, and moreover x1 \leq2, x1 +x2 \leq4, . . . . (ii) Suppose x1 +\cdot \cdot \cdot+xi \leq2i (1 \leqi \leqn−2) and x1+\cdot \cdot \cdot+xn−1 = 2n−1. Then we can obviously take r = n −1. On the other hand, for any

1 \leqi \leqn −2, xi+1 + \cdot \cdot \cdot+ xn−1 + xn = (x1 + \cdot \cdot \cdot + xn−1) −(x1 + \cdot \cdot \cdot+ xi) + 3 > 2(n −i) + 1, so we cannot take another r ̸= 0.