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。
第 3/5 步：计数输出元组
上一步下一步
通俗地说

可能的输出元组数量像一个 pp 维盒子，而候选向量的数量更多。

#{(L1,…,Lp)}≤(q2+1)p\#\{(L_1,\ldots,L_p)\}\le(q^2+1)^p
详细分析

共有 p=q/2p=q/2 行，因此像元组 (L1,…,Lp)(L_1,\ldots,L_p) 至多有 (q2+1)p=(q2+1)q/2(q^2+1)^p=(q^2+1)^{q/2} 种不同取值。