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 を満たす解を持つことを証明せよ。
ステップ 5/5: 鳩ノ巣原理を適用する
前のステップ次のステップ
ざっくり言うと

有界な非負の候補を2つ引き算することで、同じ上限を保ったまま、符号を持つ非自明な整数核ベクトルが得られる。

x=y−y≠0,∣xj∣≤qx=y-y\ne0,\quad |x_j|\le q
詳しい解説

非零ベクトルの数は像の組の数より多いので、異なる2つのベクトル u,vu,v が同じ像を持つ。その差 x=u−vx=u-v は非零整数ベクトルであり、像が打ち消し合うため各方程式を満たす。また、∣xj∣≤q|x_j|\le q であるから 0≤uj,vj≤q0\le u_j,v_j\le q である。よって、要求された3つの性質がすべて示された。