IMO 1976/B2 solution

IMO 1976

Problem B2

n is a positive integer and m = 2n. a_ij = 0, 1 or -1 for 1 ≤ i ≤ n, 1 ≤ j ≤ m. The m unknowns x₁, x₂, ... , x_m satisfy the n equations:

a_i1x₁ + a_i2x₂ + ... + a_imx_m = 0,

for i = 1, 2, ... , n. Prove that the system has a solution in integers of absolute value at most m, not all zero.

Solution

We use a counting argument. If the modulus of each x_i is at most n, then each of the linear combinations has a value between -2n² and 2n², so there are at most (4n² + 1) possible values for each linear combination and at most (2n² + 1)ⁿ possible sets of values. But there are 2n+1 values for each x_i with modulus at most n, and hence (2n+1)²ⁿ = (4n²+4n+1)ⁿ sets of values. So two distinct sets must give the same set of values for the linear combinations. But now if these sets are x_i and x_i', then the values x_i-x_i' give zero for each linear combination, and have modulus at most 2n. Moreover they are not all zero, since the two sets of values were distinct.

Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

18th IMO 1976