知恵袋で見かけた問題について
Yahoo知恵袋で見かけた記事（現在消去済み）についてのメモ. 問は「$x_1, x_2, \cdots , x_{1001}$ を実数とし, 各 $1 \leqq i \leqq 1001$ について, 残りの元 $x_1, \cdots, x_{i-1}, x_{i+1}, \cdots, x_{1001}$ を500個ずつの総和の等しいグループに分ける方法が存在する時, $x_1 = x_2 = \cdots = x_{1001}$ であることを示せ.」というもの.
- 【補題】
- $n$ 次正方行列 $A=(a_{ij}) \in M_n(\mathbb{Z})$ は対角成分が全て奇数であり, それ以外の成分は全て偶数とする. このとき $A$ は $M_n(\mathbb R)$ の元として正則である（ユニモジュラーとは限らない. 逆行列の成分は整数でない可能性もある）.
- （証明）
- 行列式が0でないことを示せばいい. $\mathfrak S_n$ を $n$ 次の置換全体の集合とする. 行列式の定義は
$ \displaystyle \det(A)=\sum_{ σ \in \mathfrak S_n} \mathrm{sgn}(σ) \prod_{i=1}^n a_{i σ(i)}$ であった. 恒等置換でない $σ$ について考えると, ある $i$ について $a_{i σ(i)}$ は対角成分ではなくなる. すなわち偶数になる. したがって $\displaystyle \prod$ の部分が偶数になる. 一方 $σ$ が恒等置換の場合, それは対角成分を順に掛けていくことになり, 対角成分は全て奇数であったから, それらを全て掛けたものも奇数になる. したがって $\displaystyle \sum_{σ \in \mathfrak S_n}$ で足される数たちは奇数を1つだけ含み, それ以外は全て偶数であるから, その総和である $\det(A)$ は奇数になる. すなわち0になりえないから $A$ は正則であることが示された（証明終）.
この補題を踏まえた上で冒頭の問を証明する.
まず, 実数の組 $x_1, x_2, \cdots , x_{1001}$ が問の条件を満たす（resp. 満たさない）とすると, 任意の定数 $C$ について $x_1+C, x_2+C, \cdots , x_{1001}+C$ も条件を満たす（resp. 満たさない）ことが分かる. つまり定数だけの差は無視してよいことになる. そこで上の式で $C=-(x_1+x_2+ \cdots +x_{1001}) \div 1001$ とおくことにより, 初めから $x_1+x_2+\cdots +x_{1001}=0$ と仮定しても一般性を失わない.
仮定より各 $x_i$ について, それ以外の1000個の数を500個ずつの総和の等しいグループに分けられる. 言い換えれば, うまく500個を選べばその和を
にできるということである. これをベクトルを用いて表現する.
ベクトル $v = (x_1, x_2, \cdots, x_{1001})^T$ とする. すなわち1001個の成分をもつ列ベクトルである. $x_i$ についての上の記述は「成分として1を500個, 0を501個含み, 第 $i$ 成分は0であるような1001次元の行ベクトル $b_i$ があって, $\displaystyle b_i v=-\frac{x_i}{2}$ となる」と表現できる. そこで行列 $B$ を
と定めることにすればこれは1001次の正方行列になり, またその対角成分は全て0である. そして行列の積の等式として,
が得られることになる. 整理すれば $(I+2B)v=0$ である. ここで $I$ は1001次の単位行列.
行列 $B$ の成分は作り方から分かるように1と0のみである. よって $2B$ の成分はすべて偶数である. したがって $I+2B$ は対角成分は全て奇数で, それ以外の成分は全て偶数であるような行列になる. よって補題よりこれは正則である. $(I+2B)v=0$ の両辺に左から $(I+2B)^{-1}$ を掛ければ $v=0$ が得られ, これは $x_1=x_2= \cdots = x_{1001}=0$ を示している. よって示された.
※$x_i$ たちは実数とのことであったが, 多分アーベル群の元としても同じことが成り立つはず.
