伝説の超難問の解法まとめ – 1998年東大 数学 後期 第3問

頂上は１つでもアプローチはいろいろ(SimonによるPixabayからの画像)

2024年3月11日

解法２：史上最大の難問　東大後期1998-問3(2011)

　本解法は他の解法と異なり、2次元正方行列を用いているところが、非常にユニークです。

　行列の定義は、以下の通りです。

　 \theta = \frac{2 \pi}3 とおき、2種類の行列W,Bをそれぞれ、

W = 
\begin{pmatrix}
\cos \theta & - \sin \theta \\
\sin \theta & \cos \theta \\
\end{pmatrix} ,
B =
\begin{pmatrix}
1 & 0 \\
0 & -1 \\
\end{pmatrix}

と定義します。W の幾何学的意味は回転角 θ の回転、B のほうは x 軸に対する対称移動です。当然、

W^3 = I,B^2=I

が成り立ちます。ここに I は単位行列です。

　以上の準備の下に、以下の段取りで証明します。

  1. 操作1と操作2は可換である。したがって、オセロ列 g \in G を生成するための操作順を操作1,1,・・・1,操作2,2,・・・2としても一般性を失わない
  2. 操作1のみを施工し終わった後のオセロ列は必ず
    〇-●-●-・・・●-〇-●-●-・・・-●-〇
    〇-●-●-・・・-●
    ●-●-・・・-●-〇
    のいずれかである。ただし、●の並びの数が0個である場合もある
  3. 白オセロに W を、黒オセロに B をそれぞれ対応させて、オセロ列 g を W と B の積で表わすとき、その計算結果は操作2によって変わらない
  4. もし長さ 3m+2 の白オセロ列が生成できるなら、その行列表現は W^{3m+2} = W^2 になるが、操作1終了時点で行列積が W^2 になることはない。したがって長さ 3m+2 の白オセロ列は生成できない

　言い回しは本稿の内容に合わせて、多少アレンジしてあります。オリジナルの言い回しについては元記事をご覧ください。また、それぞれの項目の証明についても、元記事をご覧ください。

　本解法の最大の特徴は実は行列の導入ではなく、解法段取りの①です。その破壊力は圧倒的で、これのおかげで操作1を考慮しなくてもよくなります。拡張オセロ列と同じ効果があります。

　本解法では行列積が不変量関数の役割を担っています（項番③参照）が、実はこれは、解法1の不変量関数と本質的に同じものであることが示せます。

　 g \in G の黒オセロの数を n と置きます。 g の構造を図6のように表記するとき、行列積は以下のように表せます。

W^{w_0}BW^{w_1}B \cdots BW^{w_{n-1}}BW^{w_{n}}

　ところが、

\begin{aligned}
 & W^{w_k}BW^{w_{k+1}}B\\
=&

\begin{pmatrix}
\cos w_k \theta & - \sin w_k\theta \\
\sin w_k \theta & \cos w_k \theta \\
\end{pmatrix} 
\begin{pmatrix}
1 & 0 \\
0 & -1 \\
\end{pmatrix}  \\
& \cdot

\begin{pmatrix}
\cos w_{k+1} \theta & - \sin w_{k+1}\theta \\
\sin w_{k+1} \theta & \cos w_{k+1} \theta \\
\end{pmatrix} 
\begin{pmatrix}
1 & 0 \\
0 & -1 \\
\end{pmatrix} \\

= &
\begin{pmatrix}
\cos w_k \theta & \sin w_k\theta \\
\sin w_k \theta & -\cos w_k \theta \\
\end{pmatrix}  \\
& \cdot
\begin{pmatrix}
\cos w_{k+1} \theta &  \sin w_{k+1}\theta \\
\sin w_{k+1} \theta & -\cos w_{k+1} \theta \\
\end{pmatrix}  \\

= &
\begin{pmatrix}
\cos (w_k - w_{k+1} )\theta    & - \sin (w_k - w_{k+1})\theta \\
\sin (w_k - w_{k+1}) \theta &  \cos (w_k - w_{k+1}) \theta \\
\end{pmatrix} 


\end{aligned}

なので、 n が偶数の時、

\small {
\begin{aligned}
& \text{行列積} \\
=& (W^{w_0}BW^{w_1}B )(W^{w_2}BW^{w_3}B)\cdots \\
& \cdots (W^{w_{n-2}}BW^{w_{n-1}} B )W^{w_{n}}\\
= &
 \begin{pmatrix}
\cos (w_0 - w_{1} )\theta    & - \sin (w_0 - w_{1})\theta \\
\sin (w_0 - w_{1}) \theta &  \cos (w_0 - w_{1}) \theta \\
\end{pmatrix}  \\
& \cdot
\begin{pmatrix}
\cos (w_2 - w_{3} )\theta    & - \sin (w_2 - w_{3})\theta \\
\sin (w_2 - w_{3}) \theta &  \cos (w_2 - w_{3}) \theta \\
\end{pmatrix}  \\
& \cdots \\
& \cdot
\begin{pmatrix}
\cos (w_{n-2} - w_{n-1} )\theta    & - \sin (w_{n-2} - w_{n-1})\theta \\
\sin (w_{n-2} - w_{n-1}) \theta &  \cos (w_{n-2} - w_{n-1}) \theta \\
\end{pmatrix}  \\
& \cdot
\begin{pmatrix}
\cos w_{n} \theta    & - \sin  w_{n}\theta \\
\sin w_{n} \theta &  \cos  w_{n} \theta \\
\end{pmatrix}  \\
=&
\begin{pmatrix}
\cos f(g) \theta    & - \sin  f(g)\theta \\
\sin f(g) \theta &  \cos  f(g) \theta \\
\end{pmatrix}  \\
\end{aligned}
}

ここに、

  f(g) =mod_3 (\sum_{k \text{が偶数} } w_k - \sum_{k \text{が奇数} } w_k   )

で、これは解法1の不変量関数そのものです。また、 n が奇数の時、

\small {
\begin{aligned}
& \text{行列積} \\
=& (W^{w_0}BW^{w_1}B )(W^{w_2}BW^{w_3}B)\cdots \\
& \cdots (W^{w_{n-3}}BW^{w_{n-2}} B) (W^{w_{n-1}} B W^{w_{n}})\\

=& (W^{w_0}BW^{w_1}B )(W^{w_2}BW^{w_3}B)\cdots \\
& \cdots (W^{w_{n-3}}BW^{w_{n-2}} B) (W^{w_{n-1}} B W^{w_{n}}B) B\\

= &
 \begin{pmatrix}
\cos (w_0 - w_{1} )\theta    & - \sin (w_0 - w_{1})\theta \\
\sin (w_0 - w_{1}) \theta &  \cos (w_0 - w_{1}) \theta \\
\end{pmatrix}  \\
& \cdot
\begin{pmatrix}
\cos (w_2 - w_{3} )\theta    & - \sin (w_2 - w_{3})\theta \\
\sin (w_2 - w_{3}) \theta &  \cos (w_2 - w_{3}) \theta \\
\end{pmatrix}  \\
& \cdots \\
& \cdot
\begin{pmatrix}
\cos (w_{n-1} - w_{n} )\theta    & - \sin (w_{n-1} - w_{n})\theta \\
\sin (w_{n-1} - w_{n}) \theta &  \cos (w_{n-1} - w_{n}) \theta \\
\end{pmatrix}  \\
& \cdot

\begin{pmatrix}
1    & 0 \\
0 &  -1 \\
\end{pmatrix}  \\


=&
\begin{pmatrix}
\cos f(g) \theta    & - \sin  f(g)\theta \\
\sin f(g) \theta &  \cos  f(g) \theta \\
\end{pmatrix}  
\begin{pmatrix}
1    & 0 \\
0 &  -1 \\
\end{pmatrix}  \\
=&
\begin{pmatrix}
\cos f(g) \theta    &  \sin  f(g)\theta \\
\sin f(g) \theta &  -\cos  f(g) \theta \\
\end{pmatrix}  


\end{aligned}
}

です。

　操作2によって黒オセロ数の偶奇は変わらないので、行列積は上記の2パターンのいずれかで、常に記述できます。

　以上のように、解法2の行列積は解法1の不変量関数 f(g) の値に依存して決まるので、これらは本質的に同じであることがわかります。

次ページ→解法3の紹介です

東大1998年

Posted by mine_kikaku