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 4 of 5: Compare the counts

Previous step Next step

In plain words

This strict inequality is the only numerical estimate needed for the pigeonhole principle.

(q+1)^q-1=(q^2+1+2q)^{q/2}-1>(q^2+1)^{q/2}

Detailed analysis

Because $q=2p$ , expand $(q^2+1+2q)^{q/2}$ . Its first term is $(q^2+1)^{q/2}$ , and all remaining binomial terms together exceed $1$ ; hence $(q+1)^q-1>(q^2+1)^{q/2}$ .