USAMO2008第6問と有限体上の線形代数 - フィボナッチ・フリーク

USAMO（アメリカ数学オリンピック）の2008年大会では，第6問として次のような問題が出題されました．

ある数学の会議において，どの2人の数学者も友達かそうでないかのどちらかであるとする．参加した数学者全員は二つの大きな部屋のいずれかで夕食を食べる．数学者たちはみな，自分の友達のうち偶数人が含まれる部屋で食事をしたいとする．全員の希望を満たすように数学者を分ける方法の総数は2の冪（つまりある正整数 $k$ に対し $2^k$ ）であることを示せ．

これは純粋に組み合わせ論の問題ですが，実は線形代数の知識を使うと見通しよく解くことができます．

解答．数学者に $1,2,\dots,n$ と番号をつける．以下，行列やベクトルは全て $\mathbb{F}_2=\mathbb{Z}/2\mathbb{Z}$ 上で考える． $i$ と $j$ が友達であるとき $a_{ij}=1$ ，そうでないとき $a_{ij}=0$ と定め， $a_{ii}$ は $i$ の友達の総数を2で割った余りとする．これにより $n\times n$ 行列 $(a_{ij})$ が定まる．また， $i$ を部屋Aに割り当てるとき $v_i=0$ ，部屋Bに割り当てるとき $v_i=1$ とすると $n$ 次元ベクトル $(v_i)$ が定まる．このとき，割り当て方 $v$ が数学者全員の希望を満たすことは

\[\begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n}\\ a_{21} & a_{22} & \dots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\a_{n1} & a_{n2} & \dots & a_{nn}\end{pmatrix}\begin{pmatrix}v_1\\ v_2\\\vdots\\v_n\end{pmatrix}=\begin{pmatrix}a_{11}\\ a_{22}\\ \vdots\\a_{nn}\end{pmatrix}\]

と同値である．実際左辺の第 $i$ 成分は， $i$ が部屋Aにいるときは

（部屋Bにいる $i$ の友達の総数） $\mathrm{mod}~2$

であり， $i$ が部屋Bにいるときは

（ $i$ の友達の総数） $+$ （部屋Bにいる $i$ の友達の総数） $\mathrm{mod}~2$

なので，これが $a_{ii}$ になることは $i$ の希望が満たされることと同値である．よって全員の希望を満たす割り当て方は存在すれば2冪であることがわかった．解の存在を示すには，拡大係数行列

\[\left(\begin{array}{cccc|c}a_{11} & a_{12} & \dots & a_{1n} & a_{11}\\a_{12} & a_{22} & \dots & a_{2n} & a_{22} \\ \vdots & \vdots & \ddots & \vdots & \vdots\\ a_{n1} & a_{n2} & \dots & a_{nn} & a_{nn}\end{array}\right)\]

のランクがもとの行列のランクに等しいことを示せば良い．行変形により第 $i_0$ 行の第 $1$ 列から $n$ 列までを $0$ にできたとすると，実は同じ行の $n+1$ 列も $0$ になる．実際，行変形としては第 $i_1,i_2,\dots,i_k$ 行を第 $i_0$ 行に足すという操作だけ考えればよい．このとき