48th International Mathematical Olympiad Vietnam 2007 Shortlisted Problems with Solutions

Lemma. Suppose that all terms of the sequence $(x_1,\dots ,x_n)$ satisfy the inequality $|x_i|<a$. Then there exists a partition $\{1,2,\dots ,n\}=I\cup J$ into two disjoint sets such that $$|\sum _{i\in I}{x}_i-\sum _{j\in J}{x}_j|<a.\text{\hspace{1em}(1)}$$ Proof. Apply an induction on $n$. The base case $n=1$ is trivial. For the induction step, consider a sequence $(x_1,\dots ,x_n)$ ($n>1$). By the induction hypothesis there exists a splitting $\{1,\dots ,n-1\}=I^{\prime }\cup J^{\prime }$ such that $$|\sum _{i\in I^{\prime }}{x}_i-\sum _{j\in J^{\prime }}{x}_j|<a$$ For convenience, suppose that ${\sum }_{i\in I^{\prime }}{x}_i\ge {\sum }_{j\in J^{\prime }}{x}_j$. If $x_n\ge 0$ then choose $I=I^{\prime }$, $J=J^{\prime }\cup \{n\}$; otherwise choose $I=I^{\prime }\cup \{n\}$, $J=J^{\prime }$. In both cases, we have ${\sum }_{i\in I^{\prime }}{x}_i-{\sum }_{j\in J^{\prime }}{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^{\prime }}{x}_i-\sum _{j\in J^{\prime }}{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,\dots ,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,\dots ,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,\dots ,x_n)$ and $A_{k+1}=(y_1,\dots ,y_n)$. Let $\{1,2,\dots ,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$.