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

2022年4月1日2026年3月3日

解法１：交代和を不変量関数に利用する証明

　 $g \in \mathfrak{G}$ が図6のように表記されるとき、関数 $f(g)$ を

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

と定義します。

　すると $f(g)$ は操作2に対して不変であって、拡張オセロ列 $EG$ の不変量関数になります。すなわち EG の初期要素を g₀ と置くとき、任意の $g \in EG$ に対し

f(g) = f(g_0)

が成り立ちます。

　交代和というのはちょっと不自然な代物ですが、オセロ列に操作2をほどこすと隣り合う2つの白オセロ群に対して

のいずれかが起きます。

　そこで、白オセロ群のオセロ数を、1つおきに符号を反転させて総和を取れば、それは白オセロが3つ増えるか、3つ減るかのいずれかしか起きないので、 mod 3 で変化はありません。

　こうやって交代群を思いつくことができます。

　交代和で不変量関数を定義したとき、長さ 3m+2 の白オセロ列ができないことを以下のようにして証明することができます。

$f(g) \ne f(g_0)$ なら $g \notin EG$
長さ 3m+2 の白オセロ列 $wg$ の両端にオセロ石 $o_L,o_R$ をどのように付加しても、①が成り立つので $o_L -wg - o_R \notin EG$ である
ゆえに命題2により、 $wg \notin G$ である。すなわち長さ 3m+2 の白オセロ列は生成できない

　①は、 $g \in EG$ なら $f(g) =f(g_0)$ であることの対偶です。

　超難問だというのに意外にすっきりして見えますが、これは結局のところ不変量関数の導出がキモだからです。これをどのように料理するかが、各解法の特徴になっています。

　拡張オセロ列を使用しない場合、 $f(g)$ は不変量関数になりませんが、

\begin{aligned} f(g) = & mod_3(\sum_{k \text{が偶数} } w_k - \sum_{k \text{が奇数} } w_k \\ & \text{　　　}+2mod_2(n)) \\ \end {aligned}

と定義するとき、、 $g \in G$ に対し $f(g)$ は0かまたは1になります。解法1-3はこの性質を使って証明しています。また、解法1-8はこの関数それ自体は使用していませんが、この性質を利用して証明しています。

　一方、解法1-2はオセロ石に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 は単位行列です。

　白オセロ石に W を、黒オセロ石に B を対応させて、オセロ石の並び順の通りに行列積を計算した結果が $g \in G$ であることの必要条件になりますが、長さ 3m+2 の白オセロ列はこれを満たさない、というのが証明の骨子です。

　ところが、 $g \in G$ の行列積が

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 )

で、これは交代和そのものです。また、 $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} }

です。　以上のように行列積は交代和の値に依存して決まるので、これらは本質的に同じであることがわかります。

1 2 3 4 5 6