olymmath

ISL 2007 C4

Let A0=(a1,…,an)A_{0}=\left(a_{1}, \ldots, a_{n}\right) be a finite sequence of real numbers. For each k≥0k \geq 0, from the sequence Ak=(x1,…,xn)A_{k}=\left(x_{1}, \ldots, x_{n}\right) we construct a new sequence Ak+1A_{k+1} in the following way. 1. We choose a partition {1,…,n}=I∪J\{1, \ldots, n\}=I \cup J, where II and JJ are two disjoint sets, such that the expression ∣∑i∈Ixi−∑j∈Jxj∣\left|\sum_{i \in I} x_{i}-\sum_{j \in J} x_{j}\right| attains the smallest possible value. (We allow the sets II or JJ 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)A_{k+1}=\left(y_{1}, \ldots, y_{n}\right), where yi=xi+1y_{i}=x_{i}+1 if i∈Ii \in I, and yi=xi−1y_{i}=x_{i}-1 if i∈Ji \in J. Prove that for some kk, the sequence AkA_{k} contains an element xx such that ∣x∣≥n/2|x| \geq n / 2. (Iran)

Official text Transcription from NuminaMath olympiads, checked word for word against the official paper. Quoted with source.

Official text: IMO 2007 Shortlist booklet, page 32.

Solutions

Official solution Solution 1 by the IMO Problem Selection Committee

The terms of the source let olymmath link to this solution but not copy it. Read the solution (IMO official site).

Similar problems

These problems have the most words in common with this statement.

Locator isl/2007/c4 · Tag W2HSFRZ1KC · Edit this page on GitHub · Keys: j next, k previous