Track / Stage 9 / 72 of 80 #1952 of 2000

Problem 1952

IMO P2/P5; hard shortlist

Combinatorics Difficulty 9.3 Prove it 48th International Mathematical Olympiad Vietnam 2007 Shortlisted Problems with Solutions · IMO · 2007

Let $A_{0} = (a_{1}, \ldots, a_{n})$ be a finite sequence of real numbers. For each $k \geq 0$ , from the sequence $A_{k} = (x_{1}, \ldots, x_{n})$ we construct a new sequence $A_{k+1}$ in the following way.
1. We choose a partition $\{1, \ldots, n\} = I \cup J$ , where $I$ and $J$ are two disjoint sets, such that the expression
$\left|\sum_{i \in I} x_{i} - \sum_{j \in J} x_{j}\right|$
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 $A_{k+1} = (y_{1}, \ldots, y_{n})$ , where $y_{i} = x_{i} + 1$ if $i \in I$ , and $y_{i} = x_{i} - 1$ if $i \in J$ .
Prove that for some $k$ , the sequence $A_{k}$ contains an element $x$ such that $|x| \geq n / 2$ .

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Lemma. Suppose that all terms of the sequence $(x_{1}, \ldots, x_{n})$ satisfy the inequality $|x_{i}| < a$ . Then there exists a partition $\{1,2, \ldots, n\} = I \cup J$ into two disjoint sets such that
$|\sum_{i \in I} x_{i} - \sum_{j \in J} x_{j}| < a. \tag{1}$
Proof. Apply an induction on $n$ . The base case $n = 1$ is trivial. For the induction step, consider a sequence $(x_{1}, \ldots, x_{n})$ ( $n > 1$ ). By the induction hypothesis there exists a splitting $\{1, \ldots, n-1\} = I' \cup J'$ such that
$|\sum_{i \in I'} x_{i} - \sum_{j \in J'} x_{j}| < a$
For convenience, suppose that $\sum_{i \in I'} x_{i} \geq \sum_{j \in J'} x_{j}$ . If $x_{n} \geq 0$ then choose $I = I'$ , $J = J' \cup \{n\}$ ; otherwise choose $I = I' \cup \{n\}$ , $J = J'$ . In both cases, we have $\sum_{i \in I'} x_{i} - \sum_{j \in J'} x_{j} \in [0, a)$ and $|x_{n}| \in [0, a)$ ; hence
$\sum_{i \in I} x_{i} - \sum_{j \in J} x_{j} = \sum_{i \in I'} x_{i} - \sum_{j \in J'} x_{j} - |x_{n}| \in (-a, a),$
as desired.
Let us turn now to the problem. To the contrary, assume that for all $k$ , all the numbers in $A_{k}$ lie in interval $(-n / 2, n / 2)$ . Consider an arbitrary sequence $A_{k} = (b_{1}, \ldots, b_{n})$ . To obtain the term $b_{i}$ , we increased and decreased number $a_{i}$ by one several times. Therefore $b_{i} - a_{i}$ is always an integer, and there are not more than $n$ possible values for $b_{i}$ . So, there are not more than $n^{n}$ distinct possible sequences $A_{k}$ , and hence two of the sequences $A_{1}, A_{2}, \ldots, A_{n^{n} + 1}$ should be identical, say $A_{p} = A_{q}$ for some $p < q$ .
For any positive integer $k$ , let $S_{k}$ be the sum of squares of elements in $A_{k}$ . Consider two consecutive sequences $A_{k} = (x_{1}, \ldots, x_{n})$ and $A_{k+1} = (y_{1}, \ldots, y_{n})$ . Let $\{1,2, \ldots, n\} = I \cup J$ be the partition used in this step - that is, $y_{i} = x_{i} + 1$ for all $i \in I$ and $y_{j} = x_{j} - 1$ for all $j \in J$ . Since the value of $|\sum_{i \in I} x_{i} - \sum_{j \in J} x_{j}|$ is the smallest possible, the Lemma implies that it is less than $n / 2$ . Then we have
$S_{k+1} - S_{k} = \sum_{i \in I} ((x_{i} + 1)^{2} - x_{i}^{2}) + \sum_{j \in J} ((x_{j} - 1)^{2} - x_{j}^{2}) = n + 2(\sum_{i \in I} x_{i} - \sum_{j \in J} x_{j}) > n - 2 \cdot \frac{n}{2} = 0$ .
Thus we obtain $S_{q} > S_{q-1} > \cdots > S_{p}$ . This is impossible since $A_{p} = A_{q}$ and hence $S_{p} = S_{q}$ .

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.