2016年京大理学部特色入試第3問(コインの問題)を線形代数で機械的に解く

以前,京大特色入試のある問題が「難問だ」と話題になりました.かなり競プロっぽい問題でもあります.

この記事では,この問題を大学の線形代数の知識を使って機械的な計算で解いてみます.「連立方程式で鶴亀算が解ける」なんかもまさにそうですが,高級な道具で難問が機械的に解けるというのは嬉しいですね!

設問 $(1)$,$(2)$ ではガウスの消去法を,$(3)$ ではちょっとハイレベルな巡回行列の固有値を使います.

問題

以下に問題を引用します.
「2016年度 京都大学理学部 特色入試 数学 第3問」です.

準備: $\F_2$ 上の線形代数による定式化

有限体 $\F_2$

整数しかない世界を考え,さらに全ての偶数を $0$ と,全ての奇数を $1$ と同一視します.こうすると,この世界には $\{0, 1\}$ の $2$ つの数しかなくなります.この世界を $\F_2$ と書きます.$\F_2$ では例えば $1+1=0$ となります.

$\F_2$ のように,数が有限個しかなく加減乗除が定義されている世界を有限体と言います.以下では断りのない限り $\F_2$ の世界で考えます.

線形代数による定式化

便宜上,問題文中の図の一番上にあるコインを $1$ 枚目とし,そこから時計回りに $2$ 枚目,$3$ 枚目,... とします.また,$1$ 枚目 〜 $k$ 枚目をひっくり返す操作を「操作 $1$」,$2$ 枚目 〜 $k+1$ 枚目をひっくり返す操作を「操作 $2$」,... と名付けます.

コインの表を $0$ で,裏を $1$ で表すことにすると,$n$ 枚のコインの状態は,$n$ 次元ベクトル $b \in \F_2^n$ で表せます.例えば,設問 (1) の初期状態は $b=[0,1,1,0,1,0,1]^\top$ といった具合です.

コインをひっくり返さないことを $0$ で,ひっくり返すことを $1$ で表すことにすると,操作 $1$ 〜 $n$ もそれぞれ $n$ 次元ベクトルで表せます.これを $a_1,\dots,a_n \in \F_2^n$ とします.例えば,$n=7$,$k=3$ のとき,$a_4 = [0,0,0,1,1,1,0]^\top$ です.

このように定めると,状態ベクトル $b$ に操作ベクトル $a_i$ を($\F_2$ 上で)足すと,操作後の状態ベクトルになることに気づきます! これが一番のポイントです.

例えば,問題 (1) の初期状態から操作 $1$,$2$ を適用した後の状態は $b+a_1+a_2$ $=[1,1,1,1,1,0,1]^\top$ となります.この足し算から,操作の順番は関係無いこと,同じ操作を 2 回以上しても意味が無いことも分かります.

初期状態ベクトルを $b \in \F_2^n$ とし,操作 $i$ をするとき $x_i=1$,しないとき $x_i=0$ と定めると,操作後の状態ベクトルは,$b + \sum_{i=1}^n a_i x_i$ と書けます.この式は,$A = [a_1,\dots,a_n] \in \F_2^{n\times n}$,$x = [x_1,\dots,x_n]^\top \in \F_2^n$ とおくと,行列・ベクトル積を用いて $\red{b + Ax}$ とより簡潔に書けます.

ゲームを終了させるということは,$b + Ax$ をゼロベクトルにすることです.つまり,ゲームを終了させるために必要な操作は,線形方程式 $\red{Ax = b}$ の解 $x$ です.

$(1)$ の解答

方程式 $Ax=b$ の解を求めればよいです.これは以下のようにガウスの消去法で機械的に計算できます.$1+1=0$ であることに注意して下さい.

まず $A$ と $b$ を並べると\[ \left[ \begin{array}{ccccccc|c} 1 & & & & & 1 & 1 & \\ 1 & 1 & & & & & 1 & 1\\ 1 & 1 & 1 & & & & & 1\\ & 1 & 1 & 1 & & & & \\ & & 1 & 1 & 1 & & & 1\\ & & & 1 & 1 & 1 & & \\ & & & & 1 & 1 & 1 & 1\end{array} \right] \] です(空白の要素は $0$ です).$1$ 列目から順に下三角部分を消去(前進消去)していくと,\[\left[\begin{array}{ccccccc|c}1 & & & & & 1 & 1 & \\& 1 & & & & 1 & & 1\\& & 1 & & & & 1 & \\& & & 1 & & 1 & 1 & 1\\& & & & 1 & 1 & & \\& & & & & 1 & 1 & 1\\& & & & & & 1 & 1\end{array}\right]\] となります.後退代入すると,解は $x=[1,1,1,0,0,0,1]^\top$ しか無いことが分かります.

よって,操作 $1$,$2$,$3$,$7$ の $4$ 手が最短です.

$(2)$ の解答

方程式 $Ax=b$ に解が無いことを示せばいいです.これも (1) と同様に機械的に計算できます.\[\left[
\begin{array}{cccccc|c}1 & & & & 1 & 1 & \\1 & 1 & & & & 1 & 1\\1 & 1 & 1 & & & & 1\\& 1 & 1 & 1 & & & \\& & 1 & 1 & 1 & & \\& & & 1 & 1 & 1 & 1\end{array}\right]\]を前進消去すると,\[\left[\begin{array}{cccccc|c}1 & & & & 1 & 1 & \\& 1 & & & 1 & & 1\\& & 1 & & & 1 & \\& & & 1 & 1 & 1 & 1\\& & & & & & 1\\& & & & & &\end{array}\right]\]となります.$5$ 行目を見ると,$0=1$ となっているので,この方程式には解が無いことが分かります.

$n$ と $k$ がもうちょっと大きかったら総当たりで解くのは大変そうですが,線形代数を使えば簡単ですね!

$(3)$ の解答

任意の $b \in \F_2^n$ に対し方程式 $Ax = b$ の解が存在するための必要十分条件を調べればよいです.これは $\det A \neq 0$ と同値です.

この $\det A$ ももちろん $\F_2$ 上の話ですが,(楽な計算方法が思いつかなかったので,)ここではまず複素数体 $\C$ 上で計算します.$\C$ 上で $\det A$ を計算してその偶奇を見れば,$\F_2$ 上での $\det A$ の値がわかります.

巡回行列についての知識を使うと,$\R$ 上での $\det A$ の値は「$n$ と $k$ が互いに素ならば $k$,そうでないならば $0$」と計算できます(→ 補足).よって $\F_2$ 上では,$n$ と $k$ が互いに素かつ $k$ が奇数ならば $\det A = 1$,そうでないなら $\det A=0$ となります.

補足: 複素数体上での $\det A$ の計算

この補足では,$\F_2$ 上ではなく $\C$ 上で計算します.

$2$ 列目は $1$ 列目を下に $1$ つスライドしたもの,$3$ 列目は $2$ 列目を下に $1$ つスライドしたもの,... となっている行列を巡回行列と言います.つまり,以下のような行列です: \[\left[\begin{array}{cccccc}c_0 & c_{n-1} & c_{n-2} & \cdots & c_2 & c_1\\c_1 & c_0 & c_{n-1} & \ddots & \ddots & c_2\\c_2 & c_1 & c_0 & \ddots & \ddots & \vdots\\\vdots & \ddots & \ddots & \ddots & c_{n-1} & c_{n-2}\\c_{n-2} & \ddots & \ddots & c_1 & c_0 & c_{n-1}\\c_{n-1} & c_{n-2} & \cdots & c_2 & c_1 & c_0\end{array}\right].\]この問題の行列 $A$ はまさに巡回行列になっています.

巡回行列の固有値は明示的に書けることが知られています(証明は割と簡単です):

巡回行列 $C \in \R^{n\times n}$ の $1$ 列目を $[c_0,c_1,\dots,c_{n-1}]^\top$ とすると,$C$ の固有値は\[\sum_{l=0}^{n-1} c_l \xi^{jl}\qquad(j=0,1,\dots,n-1)\]である.ただし,$\xi := \exp\big(\frac{2\pi\sqrt{-1}}{n}\big)$.

この問題の行列 $A$ では $c_0=c_1=\dots=c_{k-1}=1$,$c_k=\dots=c_{n-1}=0$ です.上の事実と等比数列の和の公式より,\begin{equation}\label{detA}\det A= \prod_{j=0}^{n-1} \sum_{l=0}^{k-1} \xi^{jl}= k \under{\frac{\prod_{j=1}^{n-1} (1-\xi^{kj})}{\prod_{j=1}^{n-1} (1-\xi^{j})}}\end{equation}となります.

高校数学でもよく登場する,整数に関する有名な事実1:

$n$ と $k$ が互いに素ならば,$k,$ $2k,\dots,$ $(n-1)k$ を $n$ で割った余りには $1,2,\dots,n-1$ がちょうど一回ずつ現れる.

を使うと,$n$ と $k$ が互いに素のとき,式 \eqref{detA} 下線部の分母と分子は一致することが分かり,$\det A = k$ です.互いに素でないときは $n=pn'$,$k=pk'$ と書け,分子の $\prod$ の中身は $j=n'$ で $0$ となるため,$\det A = 0$ です.

以上で $\det A$ が計算できました.

  1. これを背理法で証明します. $ak$ と $bk$ $(0 \lt a \lt b \lt n)$ を $n$ で割った余りが一致すると仮定すると,$(b-a)k$ は $n$ の倍数です. しかし,$n$ と $k$ が互いに素で,$0 \lt b-a \lt n$ なので,これは矛盾です.
タイトルとURLをコピーしました