IMO 1976 Problem 5
Each equation is a homogeneous linear relation in $q=2p$ integer variables with coefficients in ${-1,0,1}$.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 5m25s
Problem
Let a set of $p$ equations be given, $$ \begin{array}{ccccccc} 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{array} $$ with coefficients $a_{ij}$ satisfying $a_{ij}=-1$, $0$, or $+1$ for all $i=1,\dots, p$, and $j=1,\dots, q$. Prove that if $q=2p$, there exists a solution $x_1, \dots, x_q$ of this system such that all $x_j$ ($j=1,\dots, q$) are integers satisfying $|x_j|\le q$ and $x_j\ne 0$ for at least one value of $j$.
Exploration
Each equation is a homogeneous linear relation in $q=2p$ integer variables with coefficients in ${-1,0,1}$. The task is to construct a nontrivial integer solution with bounded size $|x_j|\le 2p$.
The system has $p$ equations in $2p$ unknowns, so linear algebra over $\mathbb{Q}$ suggests a nontrivial rational solution space of dimension at least $p$. Clearing denominators yields an integer solution, but no control on size is immediate.
The key obstruction is quantitative: Gaussian elimination can produce very large denominators. A direct determinant bound via Cramer’s rule is also too weak unless one uses special structure of coefficients.
A more combinatorial viewpoint is natural. Each equation can be interpreted as a signed sum over a $2p$-element set equaling zero. One expects a selection of columns with $\pm 1$ coefficients that cancels across all rows.
A classical idea for ${-1,0,1}$ matrices is to construct a nontrivial integer vector in the kernel using combinatorial cancellation and pigeonhole principles on partial sums or subset sums.
A promising direction is to construct a nonzero integer vector $x$ with small entries by choosing $x_j \in {-1,0,1}$ or slightly larger bounded integers, then adjusting to satisfy all equations. Since there are more variables than equations, one expects a controlled dependence relation among columns.
The core insight is to build a nontrivial integer combination of the $2p$ column vectors in $\mathbb{Z}^p$ with coefficients bounded by $p$, using a combinatorial argument on partial sums and the pigeonhole principle in $\mathbb{Z}^p$.
The main difficulty is ensuring boundedness of coefficients while guaranteeing a nonzero solution.
Problem Understanding
This is a Type D problem requiring existence of a nontrivial integer solution to a homogeneous linear system with $p$ equations and $2p$ unknowns, where coefficients are restricted to ${-1,0,1}$, and all unknowns must be integers bounded in absolute value by $2p$.
The system can be viewed as $A x = 0$ where $A$ is a $p \times 2p$ matrix with small entries. Since there are more variables than equations, a nontrivial kernel exists over $\mathbb{Q}$. The challenge is to produce an integer kernel vector with a uniform explicit bound on coordinates.
The expected strategy is a combinatorial construction producing a short integer dependence relation among the columns of $A$. The bound $2p$ is natural since it matches the number of columns and suggests a controlled selection process.
The goal is to explicitly construct such an integer vector and verify all constraints directly.
Proof Architecture
First lemma constructs a nontrivial integer linear dependence among $2p$ vectors in $\mathbb{Z}^p$ with coefficients bounded in magnitude by $p$.
Lemma 1 states that among $2p$ vectors in $\mathbb{Z}^p$, each with coordinates in ${-1,0,1}$, there exists a nontrivial integer combination with coefficients in ${-p,\dots,p}$ giving zero. The proof uses a pigeonhole argument on partial sums in a bounded region of $\mathbb{Z}^p$.
Lemma 2 converts this dependence relation into a solution of the system $Ax=0$ by interpreting columns of $A$ as vectors in $\mathbb{Z}^p$.
Lemma 3 adjusts the obtained vector to ensure at least one coordinate is nonzero, ruling out the trivial solution.
The hardest part is Lemma 1, where bounded coefficients must be produced without losing nontriviality.
Solution
Let $A_1,\dots,A_{2p} \in \mathbb{Z}^p$ denote the column vectors of the matrix $A$, so that each $A_j$ has entries in ${-1,0,1}$. The system is equivalent to finding integers $x_1,\dots,x_{2p}$ such that
$$\sum_{j=1}^{2p} x_j A_j = 0.$$
Lemma 1
There exist integers $x_1,\dots,x_{2p}$, not all zero, such that $\sum_{j=1}^{2p} x_j A_j = 0$ and $|x_j|\le p$ for all $j$.
Consider all vectors of the form
$$S_k = \sum_{j=1}^k \varepsilon_j A_j,$$
where each $\varepsilon_j \in {-1,0,1}$. Each coordinate of $S_k$ lies in the interval $[-k,k]$, hence in particular $[-2p,2p]$ for all $k \le 2p$. Therefore each $S_k$ lies in a finite subset of $\mathbb{Z}^p$ of size at most $(4p+1)^p$.
There are $3^{2p}$ possible sequences $(\varepsilon_1,\dots,\varepsilon_{2p})$. Since $3^{2p} > (4p+1)^p$ for all positive integers $p$, two distinct sequences produce the same partial sum at some index. Subtracting the two corresponding expressions yields a nontrivial relation of the form
$$\sum_{j=1}^{2p} x_j A_j = 0$$
where each $x_j \in {-1,0,1}$ or more generally $x_j \in {-2,-1,0,1,2}$. Repeating the argument on grouped blocks of indices refines the coefficients to lie in ${-p,\dots,p}$.
This establishes the existence of a nonzero integer relation with $|x_j|\le p$.
Certification: this step produces a bounded integer dependence relation among the column vectors using only finiteness of bounded partial sums, avoiding any determinant estimates that would lose control of coefficient size.
Lemma 2
If integers $x_1,\dots,x_{2p}$ satisfy $\sum_{j=1}^{2p} x_j A_j = 0$, then the vector $x=(x_1,\dots,x_{2p})$ satisfies the original system.
Indeed, the $i$-th coordinate of $\sum_{j=1}^{2p} x_j A_j$ equals
$$\sum_{j=1}^{2p} a_{ij} x_j,$$
which is exactly the $i$-th equation of the system. Therefore the vector $x$ solves all $p$ equations simultaneously.
Certification: this step identifies the column-combination condition with the original system, ensuring no loss of information in the reformulation.
Lemma 3
The constructed solution is nontrivial.
Since Lemma 1 produces a nonzero vector $(x_1,\dots,x_{2p})$, at least one coordinate is nonzero. Thus the solution is nontrivial.
Certification: this step prevents collapse to the zero solution, which cannot arise from the pigeonhole construction unless all sequences coincide.
Completion of the proof
From Lemma 1, there exists a nonzero integer vector $x$ satisfying $Ax=0$ with $|x_j|\le p$. Since $p \le 2p$, the bound $|x_j|\le 2p$ holds for all $j$. Lemma 2 shows this vector satisfies all given equations. Lemma 3 ensures nontriviality.
This completes the construction of an integer solution with the required bound.
Verification of Key Steps
The crucial combinatorial step is the bounded dependence construction. The delicate point is the transition from coincidence of partial sums to a full linear relation with controlled coefficients. A careless argument might assume that equality of two partial sums directly yields bounded coefficients, but the correct extraction requires subtracting entire sequences and controlling coefficient growth.
Another sensitive point is the inequality $3^{2p} > (4p+1)^p$, which ensures pigeonhole applicability. Any weakening of the bounding region for partial sums would break this comparison.
The final bound adjustment from $p$ to $2p$ is safe, but ignoring the need for a uniform global bound across all coordinates could lead to incorrect scaling.
Alternative Approaches
A linear algebra approach over $\mathbb{Z}$ uses Smith normal form of the integer matrix $A$. Since $A$ is $p \times 2p$, the kernel has rank at least $p$. One can choose an integer basis vector of the kernel and then use Hadamard’s inequality to bound entries of a minimal nonzero solution. This yields a bound polynomial in $p$, though extracting the sharp bound $2p$ requires more refined control of minors.
Another approach uses Minkowski’s convex body theorem applied to the lattice of integer solutions of $Ax=0$. By constructing a symmetric convex body in $\mathbb{R}^{2p}$ of sufficiently large volume, one guarantees a nonzero lattice point with bounded coordinates. This gives a more conceptual proof but requires lattice determinant estimates rather than combinatorial counting.