解法１：キング オブ 難問 – 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
- 長さ 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 であることの対偶です。
超難問だというのに意外にすっきりして見えますが、これは結局のところ不変量関数の導出がキモだからです。これをどのように料理するかが、各解法の特徴になっています。