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

2022年4月1日2024年3月11日

解法１：キングオブ難問 – 1998年東大数学後期第3問(2021)

　まずは手前みそながら、筆者が考えた解法を紹介します。

　本解法では拡張オセロ列 $EG$ を使用します。拡張オセロ列の初期要素を

●－〇－●

とします。

　また、 $g \in \mathfrak{G}$ が図6のように表記されるとき、不変量関数を

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

と定義します。

　 $f(g)$ の導出方法と、これが操作2に対して不変であって、 $g \in EG$ なら $f(g) =2$ であることの証明は、元記事を参照していただくとして、本解法では以下の段取りで証明します。

$f(g) \ne 2$ なら $g \notin EG$
$g$ に含まれる黒オセロの数が奇数個なら $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) =2$ であることの対偶です。また②は、操作2によって黒オセロ数の偶奇が変わらない（黒オセロは2つ増えるか、2つ減るか、増減しないかのいずれか）ことと、EGの初期オセロ列 ●-〇-● の黒オセロ数が2すなわち偶数であることを利用しています。

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