Given any integer $ n \geq 2,$ assume that the integers $ a_1, a_2, \ldots, a_n$ are not divisible by $ n$ and, moreover, that $ n$ does not divide $ \sum^n_{i=1} a_i.$ Prove that there exist at least $ n$ different sequences $ (e_1, e_2, \ldots, e_n)$ consisting of zeros or ones such $ \sum^n_{i=1} e_i \cdot a_i$ is divisible by $ n.$
Problem
Source: IMO ShortList 1991, Problem 13 (POL 4)
Tags: algebra, Divisibility, Sequence, IMO Shortlist
Aiscrim
02.11.2016 21:26
For $k=1$ and any $n$ is is obvious. Induct on $k+n$. A $1\times 1$ square is called special if it either is the only zero on its row, or one of the only two ones on its row. On each line there are at most $2$ special squares, so there is a column with at most $1$ special square. Suppose wlog that it is the first column. If there exists a special square on this column, suppose wlog that it is the top one. Apply the induction hypothesis on the matrix obtained by removing the first row and the first column and permute the rows and columns of the original matrix accordingly. If there is a zero in the top-left square, move the first column right after the column of the first one that appears in the first row. If there is an one in the top-left square, either keep the first column the same or move it after the column of the first zero that appears in the first row (depending on whether the second square in the first row contains a zero or not). This new matrix satisfies the lemma.
The problem is equivalent to finding $n-1$ sums of $a_i$s that are divisible by $n$ (as the trivial case when $e_i=0$ for all $i$ also satisfies the requirments). Note that given $x_1,...\ ,x_n$ integers, one can find $1\le i<j\le n$ such that $n$ divides $x_{i}+x_{i+1}+...+x_j$; by looking at the sums $x_1,x_1+x_2,...,x_1+...+x_n$ we either find one divisible by $n$, or we find two congruent sums which we then substract $(*)$. By applying $(*)$ for $x_i=a_i$s we find a sum $a_{i_1}+...+a_{i_j}$ divisible by $n$ (with $1<j<n$). Suppose that we have found $k\le n-2$ sums of $a_i$s divisible by $n$. By our lemma, we can find a permutation $\sigma \in S_n$ such that $\{a_{\sigma (i)},...,a_{\sigma (j)}\}$ does not have exactly the terms of one of the already $k$ found sums for any $1\le i<j\le n$. Apply $(*)$ to $x_i=a_{\sigma (i)}$ to find a new sum of $a_i$s divisible by $n$. By continuing this procedure, we obtain $n-1$ distinct sums of $a_i$s divisble by $n$.
P-H-David-Clarence
05.01.2017 15:32
fantastic solution！