MathLabs

第5問

pp 本の方程式からなる、q=2pq=2p 個の未知数 x1,…,xqx_1,\ldots,x_q の連立方程式を考える。すべての係数 aija_{ij} は {−1,0,1}\{-1,0,1\} に属する。この系が (a) すべての xjx_j が整数、(b) 少なくとも1つの 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} 個である。