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 を満たす解を持つことを証明せよ。
ステップ 4/5: 個数を比較する
前のステップ次のステップ
ざっくり言うと

この厳密な不等式が、鳩ノ巣原理を適用するために必要な唯一の数値評価である。

(q+1)q−1=(q2+1+2q)q/2−1>(q2+1)q/2(q+1)^q-1=(q^2+1+2q)^{q/2}-1>(q^2+1)^{q/2}
詳しい解説

q=2pq=2p であるから、(q2+1+2q)q/2(q^2+1+2q)^{q/2} を展開する。その第1項は (q2+1)q/2(q^2+1)^{q/2} であり、残りの二項係数の項の和は 11 より大きい。したがって (q+1)q−1>(q2+1)q/2(q+1)^q-1>(q^2+1)^{q/2} が成り立つ。