IMO 2007 Shortlist C4

Let A0 = (a1,...,an) be a finite sequence of real numbers. For each k ≥ 0, from the sequence Ak = (x1,...,xn) we constru...

imomathematicsolympiadshortlistcombinatorics

IMO 2007 Shortlist C4

Category: Combinatorics

Problem

Let A0 = (a1,...,an) be a finite sequence of real numbers. For each k ≥ 0, from the sequence Ak = (x1,...,xn) we construct a new sequence Ak+1 in the following way.

  1. We choose a partition {1,...,n} = I ∪ J, where I and J are two disjoint sets, such that the expression X i∈I xi − X j∈J xj attains the smallest possible value. (We allow the sets I or J to be empty; in this case the corresponding sum is 0.) If there are several such partitions, one is chosen arbitrarily.
  2. We set Ak+1 = (y1,...,yn), where yi = xi + 1 if i ∈ I, and yi = xi − 1 if i ∈ J. Prove that for some k, the sequence Ak contains an element x such that |x| ≥ n/2. (Iran)