MathDB

Let A_0 \equal{} (a_1,\dots,a_n) be a finite sequence of real numbers. For each

k\geq 0

, from the sequence A_k \equal{} (x_1,\dots,x_k) we construct a new sequence A_{k \plus{} 1} in the following way. 1. We choose a partition \{1,\dots,n\} \equal{} I\cup J, where

I

and

J

are two disjoint sets, such that the expression \left|\sum_{i\in I}x_i \minus{} \sum_{j\in J}x_j\right| attains the smallest value. (We allow

I

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 \plus{} 1} \equal{} (y_1,\dots,y_n) where y_i \equal{} x_i \plus{} 1 if

i\in I

, and y_i \equal{} x_i \minus{} 1 if

i\in J

. Prove that for some

k

, the sequence

A_k

contains an element

x

such that

|x|\geq\frac n2

. Author: Omid Hatami, Iran

Problem Statement