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 3 of 5: Count output tuples

In plain words

The number of possible right-hand-side tuples grows like a $p$ -dimensional box, while the candidate-vector count is larger.

\#\{(L_1,\ldots,L_p)\}\le(q^2+1)^p

Detailed analysis

There are $p=q/2$ rows, so the image tuple $(L_1,\ldots,L_p)$ assumes at most $(q^2+1)^p=(q^2+1)^{q/2}$ distinct values.