USAMO2008第6問と有限体上の線形代数
USAMO(アメリカ数学オリンピック)の2008年大会では,第6問として次のような問題が出題されました.
ある数学の会議において,どの2人の数学者も友達かそうでないかのどちらかであるとする.参加した数学者全員は二つの大きな部屋のいずれかで夕食を食べる.数学者たちはみな,自分の友達のうち偶数人が含まれる部屋で食事をしたいとする.全員の希望を満たすように数学者を分ける方法の総数は2の冪(つまりある正整数に対し)であることを示せ.
これは純粋に組み合わせ論の問題ですが,実は線形代数の知識を使うと見通しよく解くことができます.
解答.数学者にと番号をつける.以下,行列やベクトルは全て上で考える.とが友達であるとき,そうでないときと定め,はの友達の総数を2で割った余りとする.これにより行列が定まる.また,を部屋Aに割り当てるとき,部屋Bに割り当てるときとすると次元ベクトルが定まる.このとき,割り当て方が数学者全員の希望を満たすことは
\[\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}\]
と同値である.実際左辺の第成分は,が部屋Aにいるときは
(部屋Bにいるの友達の総数)
であり,が部屋Bにいるときは
(の友達の総数)(部屋Bにいるの友達の総数)
なので,これがになることはの希望が満たされることと同値である.よって全員の希望を満たす割り当て方は存在すれば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)\]
のランクがもとの行列のランクに等しいことを示せば良い.行変形により第行の第列から列までをにできたとすると,実は同じ行の列もになる.実際,行変形としては第行を第行に足すという操作だけ考えればよい.このとき
より
なので第列もになっている.ゆえに拡大係数行列のランクはもとの行列と等しく,解の存在が示された.