IMO 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\ne0\),

(c) \(|x_j|\le q\) \((j=1,2,\ldots,q)\).

Official text of the problem. Official problem paper (PDF)

Solution

Consider the set \[ S=\{-p,-p+1,\ldots,p\}^{q} \] of integer vectors. It contains \((2p+1)^q=(q+1)^{2p}\) vectors.

To each \(y=(y_1,\ldots,y_q)\in S\), assign the integer vector \[ F(y)=\left(\sum_{j=1}^{q}a_{1j}y_j,\ldots, \sum_{j=1}^{q}a_{pj}y_j\right). \] Since \(|a_{ij}|\le1\) and \(|y_j|\le p\), each coordinate satisfies \[ \left|\sum_{j=1}^{q}a_{ij}y_j\right| \le\sum_{j=1}^{q}|a_{ij}|\,|y_j| \le pq. \] Thus each coordinate of \(F(y)\) has at most \(2pq+1=q^2+1\) possible integer values. Consequently, \(F(y)\) has at most \((q^2+1)^p\) possible values.

But \[ |S|=(q+1)^{2p} =\bigl(q^2+2q+1\bigr)^p >(q^2+1)^p. \] By the pigeonhole principle, there exist distinct vectors \(u,v\in S\) such that \(F(u)=F(v)\).

Set \(x_j=u_j-v_j\) for every \(j\). These numbers are integers, and at least one is nonzero because \(u\ne v\). Moreover, \[ \sum_{j=1}^{q}a_{ij}x_j =\sum_{j=1}^{q}a_{ij}u_j-\sum_{j=1}^{q}a_{ij}v_j =0 \qquad (i=1,\ldots,p), \] and \[ |x_j|\le |u_j|+|v_j|\le 2p=q \qquad (j=1,\ldots,q). \] Hence \(x\) satisfies all three requirements. \(\square\)

The solution was checked against John Scholes' IMO solution archive (Kalva).