Question 5
(NET 3) IMO5. Let a set of $p$ equations be given,
$$\begin{aligned}a_{11}x_1+\cdots+a_{1q}x_q&=0,\\a_{21}x_1+\cdots+a_{2q}x_q&=0,\\&\vdots\\a_{p1}x_1+\cdots+a_{pq}x_q&=0,\end{aligned}$$
with coefficients $a_{ij}$ satisfying $a_{ij}=-1,0$, or $+1$ for all $i=1,\ldots,p$ and $j=1,\ldots,q$. Prove that if $q=2p$, there exists a solution $x_1,\ldots,x_q$ of this system such that all $x_j$ ($j=1,\ldots,q$) are integers satisfying $|x_j|\le q$ and $x_j\ne0$ for at least one value of $j$.
$$\begin{aligned}a_{11}x_1+\cdots+a_{1q}x_q&=0,\\a_{21}x_1+\cdots+a_{2q}x_q&=0,\\&\vdots\\a_{p1}x_1+\cdots+a_{pq}x_q&=0,\end{aligned}$$
with coefficients $a_{ij}$ satisfying $a_{ij}=-1,0$, or $+1$ for all $i=1,\ldots,p$ and $j=1,\ldots,q$. Prove that if $q=2p$, there exists a solution $x_1,\ldots,x_q$ of this system such that all $x_j$ ($j=1,\ldots,q$) are integers satisfying $|x_j|\le q$ and $x_j\ne0$ for at least one value of $j$.