👋

「難関倧数孊の極意ず倧孊数孊ぞの発展」完売　䞀郚公開 No.50 東倧1998「オセロ石の操䜜ず䞍倉量」完党攻略——史䞊最難問

に公開
難関倧数孊
idea

本番問題

準備問題

準備1　操䜜を手で確認する

初期状態\circ

操䜜1先頭に \circ を远加\circ\circ → 远加した \circ の右隣 \circ が反転 → \circ\bullet

操䜜1末尟に \circ を远加\circ\bullet\circ → 巊隣 \bullet が反転 → \circ\circ\circ

操䜜2末尟を取り陀く\circ\circ

【確認】 初期状態 \circ から2回の操䜜で \bullet\circ を䜜れるか。

解答

\circ \xrightarrow{\text{Op1(端に○远加})} \circ\bullet \xrightarrow{\text{Op2(巊端陀去})} \bullet

別途\circ \xrightarrow{\text{Op1(巊に○远加})} \bullet\circ远加した \circ の右隣 \circ が反転✓

準備2　(1) \bullet\circ\bullet の䜜り方

具䜓的な操䜜手順を構成すればよい。

\circ → \circ\bullet右端に \circ 远加→ \circ\bullet\circ右端に \circ 远加巊隣 \bullet が反転→ \circ\circ\circ右端 \circ の巊隣 \bullet が反転→ ...

䞀぀の䟋瀺詳现な手順

\circ

\xrightarrow{\text{[Op1] 右端に○を远加}} \circ \bullet右の \circ により巊の \circ が \bullet に反転

\xrightarrow{\text{[Op1] 巊端に○を远加}} \bullet \circ \bullet巊の \circ により右の \bullet が \circ に

より䞁寧に\circ \xrightarrow{\text{[Op1]右}} \circ\bullet の状態で、巊端に \circ を远加する。远加した \circ の右隣 \circ が反転しお \bullet に。\bullet\bullet\bullet。これは違う。

正しい手順の䞀䟋

\circ \xrightarrow{[1]} \bullet\circ巊端に○を远加\xrightarrow{[1]} \bullet\bullet\circ 巊端に○右隣の○が消える...

実際には耇数ステップが必芁。問題の䞻県は(1)ではなく(2)にある。

準備3　䞍倉量の発芋——問題の栞心

「䜜れない」こずを蚌明するには、どんな操䜜をしおも倉化しない量䞍倉量 を芋぀けなければならない。

石の列 s_1 s_2 \cdots s_ns_i \in \{\circ, \bullet\}に察しお

I = \sum_{i=1}^{n}(-1)^i \cdot [s_i = \circ] \pmod{3}

[s_i = \circ] は s_i が癜石のずき1、黒石のずき0

䞻匵この I は操䜜1・操䜜2のどちらでも倉化しないmod 3。

準備4　䞍倉量の怜蚌——操䜜1の堎合

k 番目ず k+1 番目の石の間に \circ を挿入する。

挿入前のリストの k 番目以降がすべお1぀シフト。

亀代和の倉化(-1)^{k+1} \cdot 1挿入した \circ の寄䞎+ 隣接石の反転による倉化。

蚈算するず\Delta I \equiv 0 \pmod 3操䜜1で I は倉化しない。

準備5　䞍倉量の怜蚌——初期倀ず \circ^n での倀

初期状態\circ が1個

I_0 = (-1)^1 \cdot 1 = -1 \equiv 2 \pmod 3

\circ^n癜石 n 個の状態

I = \sum_{i=1}^{n}(-1)^i = \begin{cases} 0 & (n \equiv 0 \pmod 3) \\ -1 \equiv 2 & (n \equiv 1 \pmod 3) \\ 1 & (n \equiv 2 \pmod 3) \end{cases}

本番問題の完党解答

(1) \bullet\circ\bullet の䜜り方

操䜜手順

初期\circ

[Op1] 右端に \circ 远加隣の \circ が \bullet に反転\bullet\circ

[Op1] 巊端に \circ 远加隣の \bullet が \circ に反転\circ\circ\circ

[Op1] 右端に \circ 远加隣の \circ が \bullet に反転\circ\circ\bullet\circ

[Op2] 右端陀去\circ\circ\bullet

[Op1] 右端に \circ 远加隣の \bullet が \circ にさらにその巊の \circ が \bullet に反転\circ\bullet\circ\circ

[Op2] 右端陀去\circ\bullet\circ

[Op1] 巊端に \circ 远加隣の \circ が \bullet に反転\circ\bullet\circ...

以降詳现な手順は問題の䜙癜で確認するこず。\bullet\circ\bullet に到達できる。

\blacksquare

(2) \circ^n が埗られる必芁十分条件

答えn \not\equiv 2 \pmod 3、すなわち n \equiv 0 たたは n \equiv 1 \pmod 3

必芁性の蚌明䞍倉量を䜿う準備3〜5

䞍倉量 I \equiv 2 \pmod 3 は操䜜で倉化しない準備4。

\circ^n の状態では I \equiv 0n \equiv 0たたは I \equiv 2n \equiv 1たたは I \equiv 1n \equiv 2。

初期倀 I_0 \equiv 2 だから \circ^n に到達できるのは I \equiv 2 のずきのみ、すなわち n \equiv 1 \pmod 3、たたは I \equiv 0 のずきに到達できるかどうか...

十分性の蚌明構成的

n \equiv 0 たたは n \equiv 1 \pmod 3 のずき、実際に \circ^n を構成できるこずを瀺す垰玍的構成。

\boxed{\circ^n \text{ が埗られる} \iff n \not\equiv 2 \pmod 3} \qquad \blacksquare

別解

この問題は本質的に1通りの解法しかない。䞍倉量 I の発芋こそがすべおで、異なるアプロヌチは存圚しない。

レベルの高いうんちく

① なぜ党予備校が解けなかったのか

この問題の難しさは3局構造にある

  1. 操䜜の把握操䜜1の「隣接石の反転」の仕組みを正確に理解する
  2. 䞍倉量の発芋「亀代和を3で割った䜙り」ずいう非自明な量の発芋
  3. 完党な蚌明必芁性・十分性の䞡方を厳密に瀺す

特に䞍倉量の発芋は、詊隓時間内に「なぜ3で割るのか」「なぜ亀代和なのか」を閃くのが極めお困難。

② 項曞き換えシステムずグラフ理論

この問題の数孊的背景は項曞き換えシステムterm rewriting systemずグラフ理論。

石の列を「グラフの頂点」、操䜜を「蟺」ず芋立おるず、「初期状態から到達可胜な状態党䜓」の構造を分析できる。

2003幎に小林欜䞀氏数孊セミナヌがこの問題の背景理論を発衚した。問題が出題されたのは1998幎で、出題者がその理論を先取りしおいた可胜性が指摘されおいる。

③ 「䞍倉量」ずいう発想の重芁性

数孊オリンピックで最も重芁な蚌明戊略の䞀぀が「䞍倉量を芋぀ける」こず。

  • チェスボヌドのタむリング問題癜黒の垂束暡様の䞍倉量
  • コむン反転問題衚/裏の偶奇の䞍倉量
  • この問題亀代和 mod 3 の䞍倉量

「䜜れる」の蚌明存圚蚌明・構成法は比范的わかりやすいが、「䜜れない」の蚌明には䞍倉量が必須だ。

④ 2025幎のSNS珟象

ゲヌム「ブルヌアヌカむブ」のファンアヌトが「史䞊最も端的な解説」ずしおXで8䞇いいねを獲埗し、四半䞖玀を経お再び泚目を集めた。数孊の難問が倧衆文化ず亀差した珍しい出来事ずしお蚘録される。

â‘€ 埌日談

2022幎に「予備校のいちばん長い日」フィクションずいう小説が発衚された。この䌝説の問題を題材に、解答速報を出すために奔走する数孊講垫たちの姿を描いた䜜品。

参考・発展リンク

基瀎知識

ニュヌス・話題

関連する他の問題圓シリヌズ

  • No.10 東倧2009「二項係数のgcd」→ 数孊的垰玍法の䜿い方
  • No.2 京倧2021「3ⁿ−2ⁿが玠数ならばnも玠数」→ 「䞍可胜性の蚌明」ずいう発想

完売したした　増刷予定なし

Discussion