IMO 2015 Problem 6

Working on Problem 6 of IMO 2015 was like playing a game. It is interesting in the sense that not too much advanced skill is required, but the involved visual thinking and the pursuit of the nature of seemingly simple yet complicated things made the experience enjoyable.


The problem is:

The sequence a(1), a(2), ... of integers satisfies the following conditions:

(i) 1 <= a(j) <= 2015 for j >= 1
(ii) k + a(k) != l + a(l) for all 1 <= k < l

Prove that there exist two positive integers b and N such that

|Summation from j = m + 1 to n {a(j) - b}| <= 1007^2

for all integers m and n satisfying n > m >= N

============================================================

Imagine an infinite number of columns numbered 1, 2,... from the left, each divided into d = 2015 cells numbered 1, 2, 3, ... to d from bottom to top. By (i) and (ii), starting from column 1 we are to sequentially select and mark one cell in each column with 'o', and then cross out its diagonal cells in the columns to the right. For an example with d = 5 where the first 4 columns are finished:

__o___
o__x__
_x__x_
_oxo_x
__xxx_

Intuitively, the statement to be proved essentially says that the sequence, i.e. the heights of o marks, will always stabilizes at some point N, meaning that after column N the average height within any window of consecutive columns will not differ too much from a constant b.

Proof:

I first played with the columns consisting of cells above for some time trying to find useful patterns of selected cells but found no pattern. However after a while I was led to something unexpected.  Consider sequence c(i), the number of cells not crossed out at column i when column i - 1 is finished. Clearly c(i) >= 1 because cell d is never crossed out. Note that sequence c never increases, and it decreases if and only if cell 1 is not selected when it's available!

Because c can only decrease and yet lower bounded, it stays at some constant d - k after some point N, i.e.

b(i) = d - k for all i >= N + 1

1 <= k <= d - 1

Here k is the number of crossed out cells in each column when it is being considered. k = 0 is the trivial case where all a(i) = 1 from the beginning of the sequence.

From now on we only consider columns after N. Since c stays constant, if cell 1 is available when we want to select a cell from a column, it must be selected.  Now think about diagonals. A diagonal D is defined as the set of cells such that i + a(i) = D. From (ii), there can only be at most one cell marked per diagonal. We say a diagonal is marked if one of its cells is. Now, when we are forced to select cell 1 in column i, this is the last chance that any cell in diagonal i + 1 gets marked. This means that no diagonals starting from diagonal N + 2 will be left unmarked permanently, because if there's any permanently unmarked diagonal y >= N + 2, it should've been marked as we see column y - 1 >= N + 1.

Consider any consecutive columns from m + 1 to n where m + 1 >= N + 1. At column m + 1, there are already k cells crossed out. Let's say they're in diagonals y(1), y(2), ... , y(k) where all y(i) are between m + 2 and m + d (m + 1 + d cannot be marked when column m is finished).  As we finish column n, diagonal n + 1 is already marked, and so is diagonal n, n - 1 ... etc. Therefore, all diagonals in [m + 2, n + 1] are marked at this point, plus k more in [n + 2, n + d], which we denote by z(1), z(2), ... , z(k).

Finally, since a(i) = diagonal index - i, we can do substitution:

  Summation from j = m + 1 to n {a(j) - b}
= Summation from j = m + 1 to n {diagonal index - j}
= Summation from j = m + 2 to n + 1 {j} + [z(1) - y(1) + z(2) - y(2) ... + z(k) - y(k)]
- Summation from j = m + 1 to n {j + b}
= (n - m)(1 - b) + [z(1) - y(1) + z(2) - y(2) ... + z(k) - y(k)]

Sum of y(1) to y(k) is upper bounded by (m + d) + ... + (m + d - k + 1) and lower bounded by (m + 2) + ... + (m + 1 + k). Sum of z(1) to z(k) is upper bounded by (n + d) + ... + (n + d - k + 1), and lower bounded by (n + 2) + ... + (n + 1 + k), so the quantity of interest is lower bounded by

(n - m)(1 - b) + (n - m - d + k + 1)k

and upper bounded by

(n - m)(1 - b) + (n - m + d - k - 1)k

Let b = k + 1, these bounds become [k - (d - 1)]k and (d - 1 - k)k, whose absolute values are bounded by [(d - 1)^2] / 4 for an odd d.

Q.E.D.

The result b = k + 1 also aligns well with intuition. For large k, many lower cells tend to be crossed out and we inevitably have to select a high one. With a small k, we could not pick too many high cells because cell 1 has to be marked whenever it's available.