IMO 1991 SL 13

Origin: POL

Problem

Given any integer n \geq2, assume that the integers a1, a2, . . . , an are not divisible by n and, moreover, that n does not divide a1 + a2 + \cdot \cdot \cdot+an. Prove that there exist at least n different sequences (e1, e2, \cdot \cdot \cdot , en) consisting of zeros or ones such that e1a1 + e2a2 + \cdot \cdot \cdot + enan is divisible by n.

Solution

Call a sequence e1, . . . , en good if e1a1+\cdot \cdot \cdot+enan is divisible by n. Among the sums s0 = 0, s1 = a1, s2 = a1 + a2, . . . , sn = a1 + \cdot \cdot \cdot + an, two give the same remainder modulo n, and their difference corresponds to a good sequence. To show that, permuting the ai’s, we can find n −1 different sequences, we use the following Lemma. Let A be a k\timesn (k \leqn−2) matrix of zeros and ones, whose every row contains at least one 0 and at least two 1’s. Then it is possible to permute columns of A is such a way that in any row 1’s do not form a block. Proof. We will use the induction on k. The case k = 1 and arbitrary n \geq3 is trivial. Suppose that k \geq2 and that for k −1 and any n \geqk + 1 the lemma is true. Consider a k \times n matrix A, n \geqk + 2. We mark an element aij if either it is the only zero in the i-th row, or one of the 1’s in the row if it contains exactly two 1’s. Since n \geq4, every row contains at most two marked elements, which adds up to at most 2k < 2n marked elements in total. It follows that there is a column with at most one marked element. Assume w.l.o.g. that it is the first column and that a1j isn’t marked for j > 1. The matrix B, obtained by omitting the first row and first column from A, satisfies the conditions of the lemma. Therefore, we can permute columns of B and get the required form. Considered as a permutation of column of A, this permutation may leave a block of 1’s only in the first row of A. In the case that it is so, if a11 = 1 we put the first column in the last place, otherwise we put it between any two columns having 1’s in the first row. The obtained matrix has the required property. Suppose now that we have got k different nontrivial good sequences ei 1, . . . , ei n, i = 1, . . . , k, and that k \leqn −2. The matrix A = (ei j)

fulfils the conditions of Lemma, hence there is a permutation \sigma from Lemma. Now among the sums s0 = 0, s1 = a\sigma(1), s2 = a\sigma(1) + a\sigma(2), . . . , sn = a\sigma(1) + \cdot \cdot \cdot + a\sigma(n), two give the same remainder modulo n. Let sp \equivsq (mod n), p < q. Then n | sq −sp = a\sigma(p+1) + \cdot \cdot \cdot + a\sigma(q), and this yields a good sequence e1, . . . , en with e\sigma(p+1) = \cdot \cdot \cdot = e\sigma(q) = 1 and other e’s equal to zero. Since from the construction we see that none of the sequences e\sigma(j)i has all 1’s in a block, in this way we have got a new nontrivial good sequence, and we can continue this procedure until there are n −1 sequences. Together with the trivial 0, . . . , 0 sequence, we have found n good sequences.