MathLabs

第5题

考虑关于 q=2pq=2p 个未知数 x1,…,xqx_1,\ldots,x_q 的 pp 个方程，其中每个系数 aija_{ij} 都属于 {−1,0,1}\{-1,0,1\}。证明该方程组存在一个解，使得：(a) 所有 xjx_j 都是整数；(b) 至少有一个 xj≠0x_j\ne0；(c) 对每个 jj 都有 ∣xj∣≤q|x_j|\le q。
第 1/5 步：计数有界非零向量
上一步下一步
通俗地说

盒子 [0,q]q[0,q]^q 中有许多候选向量，而方程能够产生的输出元组数量是有限的。

Nvec=(q+1)q−1>(q2+1)p,q=2pN_{\mathrm{vec}}=(q+1)^q-1>(q^2+1)^p,\quad q=2p
详细分析

令 q=2pq=2p。考虑所有满足 (x1,…,xq)(x_1,\ldots,x_q) 的非零整数向量 0≤xi≤q0\le x_i\le q。这样的向量共有 (q+1)q−1(q+1)^q-1 个。我们将每个向量映射到由各个方程左端组成的 pp 元组。