Competition problem — Algebra — Maths Olympiad Prep

Library / /246 of 520

Algebra Difficulty 6.4 National olympiad Prove it

5. (NET 3) ${ }^{\mathrm{IMO} 5}$ Let a set of $p$ equations be given,
$\begin{gathered} a_{11} x_{1}+\cdots+a_{1 q} x_{q}=0 \\ a_{21} x_{1}+\cdots+a_{2 q} x_{q}=0 \\ \vdots \\ a_{p 1} x_{1}+\cdots+a_{p q} x_{q}=0, \end{gathered}$
with coefficients $a_{i j}$ satisfying $a_{i j}=-1,0$ , or +1 for all $i=1, \ldots, p$ and $j=1, \ldots, q$ . Prove that if $q=2 p$ , there exists a solution $x_{1}, \ldots, x_{q}$ of this system such that all $x_{j}(j=1, \ldots, q)$ are integers satisfying $\left|x_{j}\right| \leq q$ and $x_{j} \neq 0$ for at least one value of $j$ .

Solution

5. If one substitutes an integer $q$ -tuple $\left(x_{1}, \ldots, x_{q}\right)$ satisfying $\left|x_{i}\right| \leq p$ for all $i$ in an equation of the given system, the absolute value of the right-hand member never exceeds $p q$ . So for the right-hand member of the system there are $(2 p q+1)^{p}$ possibilities. There are $(2 p+1)^{q}$ possible $q$ -tuples $\left(x_{1}, \ldots, x_{q}\right)$ . Since $(2 p+1)^{q} \geq(2 p q+1)^{p}$ , there are at least two $q$ -tuples $\left(y_{1}, \ldots, y_{q}\right)$ and $\left(z_{1}, \ldots, z_{q}\right)$ giving the same right-hand members in the given system. The difference $\left(x_{1}, \ldots, x_{q}\right)=\left(y_{1}-z_{1}, \ldots, y_{q}-z_{q}\right)$ thus satisfies all the requirements of the problem.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.