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。
第 5/5 步：应用抽屉原理
上一步下一步
通俗地说

将两个有界非负候选向量相减，是得到带符号的非平凡整数核向量，同时不超过同一界的标准方法。

x=y−y≠0,∣xj∣≤qx=y-y\ne0,\quad |x_j|\le q
详细分析

非零向量的数量多于输出元组的数量，因此存在两个不同的向量 u,vu,v 具有相同的像。它们的差 x=u−vx=u-v 是一个非零整数向量；由于输出相消，x 满足每个方程。又因为 0≤uj,vj≤q0\le u_j,v_j\le q，所以 ∣xj∣≤q|x_j|\le q。这就证明了所要求的三个性质。