フィボナッチ・フリーク

数学の小ネタ集。

Fibonacci Freak

USAMO2008第6問と有限体上の線形代数

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

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

 

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

 

解答.数学者に1,2,\dots,nと番号をつける.以下,行列やベクトルは全て\mathbb{F}_2=\mathbb{Z}/2\mathbb{Z}上で考える.ijが友達であるとき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行に足すという操作だけ考えればよい.このとき

\displaystyle \sum_{p=0}^ka_{i_pi_q}\equiv 0~(\mathrm{mod}~ 2)

より

\displaystyle \sum_{p,q}a_{i_pi_q}\equiv \sum_{p=0}^k a_{i_pi_p}\equiv 0~(\mathrm{mod}~ 2)

なので第n+1列も0になっている.ゆえに拡大係数行列のランクはもとの行列と等しく,解の存在が示された.\square