International Mathematical Olympiad 1976 Problem 5

Consider the system of $p$ equations in $q = 2p$ unknowns $x_1, x_2, \cdots, x_q$: $$\begin{aligned} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1q}x_q &= 0\\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2q}x_q &= 0\\ &\cdots\\ a_{p1}x_1 + a_{p2}x_2 + \cdots + a_{pq}x_q &= 0 \end{aligned}$$ with every coefficient $a_{ij}$ member of the set $\{-1, 0, 1\}$. Prove that the system has a solution $(x_1, x_2, \cdots, x_q)$ such that

• (a) all $x_j$ $(j = 1, 2, \ldots, q)$ are integers,

• (b) there is at least one value of $j$ for which $x_j \neq 0$,

• (c) $|x_j| \leq q$ $(j = 1, 2, \ldots, q)$.