Problem 5

Consider the system of

p

equations in

q=2p

unknowns

x_1,\ldots,x_q

, with every coefficient

a_{ij}

\{-1,0,1\}

. Prove that the system has a solution such that (a) all

x_j

are integers; (b) at least one

x_j\ne0

; (c)

|x_j|\le q

for every

j

Step 1 of 5: Count bounded nonzero vectors

Previous step Next step

In plain words

The box $[0,q]^q$ supplies many candidate vectors; the equations can produce only a limited number of output tuples.

N_{\mathrm{vec}}=(q+1)^q-1>(q^2+1)^p,\quad q=2p

Detailed analysis

Set $q=2p$ . Consider all nonzero integer vectors $(x_1,\ldots,x_q)$ with $0\le x_i\le q$ . There are $(q+1)^q-1$ such vectors. We will map each vector to the $p$ -tuple of left-hand sides of the equations.