伝説の入試問題と現代数学周遊

1998 年の東京大学後期入試で出題された数学の問題は、「伝説の入試問題」「最難関」「史上最悪」などと呼ばれています。「受験生は誰一人解けなかった」「予備校も解答を作れず、数学者に依頼した」など、様々な伝説があります。

そんな入試問題ですが、最近パズルゲーム化され再び話題になっています。

https://unityroom.com/games/1998tokyo

話題になる中で新たな解答が発表されるなど、数学的にも注目されています。

この記事では伝説の入試問題の解答を紹介しながら、現代数学とのつながりを見ていこうと思います。

問題概要

#

問題は (1) と (2) の 2 つがありますが、難しいのは (2) なのでこちらのみ扱います。

白または黒の丸を一列に並べることを考えます。まずはじめに白い丸が 1 つだけあります。その後、次の 2 種類の操作のいずれかを行います。

• 操作 1: 左端または右端に白い丸を追加し、その隣の丸の色を反転させる。
• 操作 2: 隣り合う 2 つの丸の間に白い丸を追加し、その両隣の丸の色を反転させる。

$n$ 個の丸が並んだとき、それらがすべて白であるようにすることはできるか、という問題です。

実験してみましょう。

○　→　●○　→　○○○

○　→　●○　→　○○●　→　○○○○

このように、$n=1,3,4$ では可能であることがわかります。一方 $n=2$ は不可能です。

$n=4$ の作り方を応用すれば、$n=k$ で可能ならば $n=k+3$ で可能であることもわかります。これより、$n$ を 3 で割った余りが 0 または 1 のときは可能であることがわかります。

あとは $n$ を 3 で割った余りが 2 のときに不可能であることを示せば解答が完成します。しかしこの部分が非常に難しく、伝説となった所以です。

解答

#

様々な解法が知られていますが、どれも受験生が時間内で思いつけるとは思えない天才的なものです。

多くの解法では操作によって変わらない「不変量」を考えることで、ある図形が作れないことを証明しています。

解答 1: 交代和を 3 で割った余り

#

多くのサイトで公開されている解法はこれです。例を挙げると

• 1998年 東京大学　大学入試史上No.1の超難問～20年目の真実～ (https://examist.jp/legendexam/1998-tokyo/)
• JSユウカのイラスト

があります。

JSユウカ#ブルアカ 100日チャレンジ Day 86 pic.twitter.com/6Y7RHo1Qx3

— Azel@1日目南q-16b (@lam) November 21, 2023

まず、両端に黒丸を 2 個追加することで、操作 1 は操作 2 の一種と捉えることができます。これにより操作 2 のみ考えればよくなります。

黒丸で区切ったとき、いくつかの白丸が連続した領域に分かれます。ここで、奇数番目の領域にある白丸の個数から偶数番目の領域にある白丸の個数を引いて得られる量を考えます。例えば

●○○●○●●○○○

なら、左から $0,2,1,0,3$ 個の白丸の領域に分かれるので、$(0+1+3)-(2+0)=2$ が求める量になります。$0-2+1-0+3$ と書くことで、この量は交代和であると考えることもできます。

さて、この量を 3 で割った余りは操作 2 で不変であることが示せます。最初の状態ではこの不変量が 2 なので、可能な配置では常に 2 です。一方、$3k+2$ 個の白丸が並んだ図形（に両端に 2 個加えたもの）ではこの量が 2 にならないので、不可能であることが示せます。

どうでしょうか。突然偶数番目と奇数番目に分けるところが人工的で、思いつけそうにないですね。なお、以下の J. K. さんのツイートは本質的にはこの解法と同じですが、より自然に見えるようになっています。

初等的に解いてみました。 pic.twitter.com/JsS8r7N5Nr

— J. K. (@J_Koizumi_233) January 21, 2023

解答 2: 行列式を 2 で割った余り

#

この解法は以下で見られます。

• リアルな代数幾何―メビウスの帯からトロピカル曲線まで― (https://www.mathsoc.jp/assets/pdf/publications/tushin/backnumber/2202/2202kobayashi.pdf)
• 佐久間さんのツイート

最近これを題材としたゲームができたり、小学生ユウカがこれを初等的に解いているイラストが再度万バズしてネットニュースになったりして話題になっているグラフ理論の「史上最も難しい大学入試数学の問題」(1998東大理系後期第3問)を行列式の余因子展開を使って解きました。 pic.twitter.com/gDcLxOKtTQ

— 佐久間 (@keisankionwykip) May 17, 2025

白を 1、黒を 0 と置き換えると、直線状に並んだ $n$ 個の丸を長さ $n$ の 01 列 $(a_1,\ldots,a_n)$ で表すことができます。

ここで、以下のように行列式を 2 で割った余りを考えます。

$$f(a_1,\ldots,a_n)=\det\begin{pmatrix} a_1 & 1 & 0 & \cdots & 0 \\ 1 & a_2 & 1 & \cdots & 0 \\ 0 & 1 & a_3 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & a_n \end{pmatrix} \bmod{2}$$

行列は対角線に $a_1,\ldots,a_n$ が並んでおり、その上下の対角線の成分は 1 で、その他の成分は 0 であるような三重対角行列です。

これは操作で不変であることが示せるので、同様の手法で $n$ を 3 で割った余りが 2 のときは不可能であることが示せます。

先ほどの不変量は天才的でしたが、こちらも同じくらい天才に見えますね。なお余因子展開をすることで

$$f(a_1,\ldots,a_n)\equiv a_nf(a_1,\ldots,a_{n-1})+f(a_1,\ldots,a_{n-2}) \pmod{2}$$

がわかります。高校生は行列式を知らないので、この式で定義することになるでしょうか。

解答 3: 二面体群

#

この解法は以下のサイトにあります。

• 史上最大の難問　東大後期1998-問3 (https://ameblo.jp/miraclemaster/entry-10876823332.html)
• えびまさんの動画

解答 1 と同様に、両端に白丸を加えて操作 2 のみ考えます。白丸を a、黒丸を b とおくと、操作は

• aa → bab
• ab → baa
• ba → abb
• bb → aaa

となります。不変量を作るために、$a,b$ をある群の元とみなし、上の操作において左右を等号で結びます：

• $aa=bab$
• $ab=baa$
• $ba=abb$
• $bb=aaa$

$G=\langle a,b\mid a^3=b^2=\mathrm{id}, bab=a^{-1} \rangle$ という群を考えると、上の等式が成り立ちます。この群 $G$ は位数 6 の二面体群です。

これより、可能な丸の配置において $a,b$ を群 $G$ の元とみなして積を計算すると、単位元になります。これが不変量です。

群論を知らない人に解説するには、$a,b$ を具体的な対称性とすればよいです。例えば $a$ を 120° 回転、$b$ をある軸に沿った反転とします。

群論を知っていれば他と比べて思いつきやすい解法かもしれませんが、受験生が思いつくのは難しそうです。

解答 4: 二分木

#

この解法は以下で見られます。

• nishimura さんのツイート
• simasima さんの動画

出所https://t.co/m8wMLjQDmq
私の解法：画像 pic.twitter.com/IaJ707oQuP

— nishimura (@icqk3) January 21, 2023

要約すると、操作を行うことと二分木に頂点を追加することを対応させ、すべて白丸になることは二分木の葉の深さの偶奇がすべて等しくなることと同値であることを証明します。

現代数学周遊

#

ここからは、伝説の入試問題と現代数学を結び付けていこうと思います。

新たな別解を求めて

#

これだけたくさんの別解を見ると、自分も新しい別解を探したくなります。探究の旅に出ました。

まず操作列は順列と対応します。そこで順列と一対一対応の関係にあるオブジェクトを使って考察できないか考えました。例えば permutation tableau や alternative tableau などがあります。しかしこの方法は上手くいきませんでした。

先ほど操作列が二分木と対応すると述べましたが、異なる操作列が同じ結果と対応することがあります。これは二分木に頂点を追加する順番（言い換えると頂点のラベルのつけ方）によらず、二分木の形のみに依存するということです。二分木の個数はカタラン数です。そこで順列ではなく、カタラン数と関連のあるオブジェクトを調べればよいと考えました（念のため注意ですが二分木の形が異なっていても結果が同じになることもあります）。

こうして、三角形分割を用いるという発想に至りました。次の問題を考えればよいことになります。

• 正 $n$ 角形の三角形分割において、各頂点に集まる三角形の個数を $(a_1,\ldots,a_n)$ とする。$a_i$ がすべて奇数、または隣り合う 2 数のみが偶数でその他が奇数となるようにできるか。

これをツイートしたところ、この数列 $(a_1,\ldots,a_n)$ には quiddity という名前がついていると教わりました。『フリーズの数学　スケッチ帖』という数学書にこの話が載っていると教わったので、読むことにしました。すると、上で紹介した解法がフリーズに関する様々な概念と繋がっていきました。

その面白さを紹介していこうと思います。

フリーズ

#

『フリーズの数学　スケッチ帖』の主題であるフリーズは、平面上にある規則をみたすように数を並べたものです。その規則とは

 b
a d
 c

のように並んでいるとき、$ad-bc=1$ をみたす、というものです。例を挙げると

0 0 0 0 0 0 0 0 0 0 0
 1 1 1 1 1 1 1 1 1 1
  1 2 3 1 2 3 1 2 3
   1 5 2 1 5 2 1 5
    2 3 1 2 3 1 2
     1 1 1 1 1 1
      0 0 0 0 0

があります。

quiddity は三角形分割において各頂点に集まる三角形の個数からなる列でした。この本では quiddity は奇蹄列（きてれつ）と呼ばれています。いま、1 行目は 0、2 行目は 1 のみとし、3 行目は奇蹄列を繰り返し並べたものとします。するとここからフリーズが得られます。上は六角形の三角形分割に対する奇蹄列 $(1,2,3,1,2,3)$ から得られるフリーズです。

逆に、周期的で 2 行目から $n-1$ 行目が正であるようなフリーズを考えると、3 行目はある三角形分割の奇蹄列であることが知られています。これは Conway-Coxeter の定理と呼ばれています (本の定理 2.18)。

フリーズは 3 行目を決めることで一意的に決まりますが、左端を決めることでも一意的に決まります。左端（本では第一対角線と呼ばれています）に書かれた数を $f_{-1},f_0,f_1,\ldots$ とすると、$f_{-1}=0, f_0=1$ で、$f_1$ は奇蹄列 $(a_1,\ldots,a_n)$ の最初の数 $a_1$ に等しいです。

$f$ と $a$ には $f_i=a_if_{i-1}-f_{i-2}$ という関係があります (本の補題 2.13)。

連分因子

#

本の第 4 章では連分因子 (continuant) というものが扱われています。それは次のようなものです。

$$K_n(a_1,\ldots,a_n)=\det\begin{pmatrix} a_1 & 1 & 0 & \cdots & 0 \\ 1 & a_2 & 1 & \cdots & 0 \\ 0 & 1 & a_3 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & a_n \end{pmatrix}$$

なんと、解法 2 の行列には名前がついていたのです！

連分因子はオイラーが連分数の研究をする中で導入されたもののようです。もちろん、オイラーの時代には行列式はなかったのですが。連分数については本の第 6 章で扱われています。

余因子展開により

$$K_n(a_1,\ldots,a_n)=a_nK_{n-1}(a_1,\ldots,a_{n-1})-K_{n-2}(a_1,\ldots,a_{n-2})$$

が成り立ちます。勘のいい読者はお気づきかもしれませんが、$K_i(a_1,\ldots,a_i)$ は $f_i$ と同じ関係式を満たしているので、$f_i=K_i(a_1,\ldots,a_i)$ が成り立ちます。

さて、解法 2 を思い出すと、$f_n\bmod{2}$ は不変量です。$f_n$ はフリーズのどこでしょう。それは……。

0 0 0 0 0 0 0 0 0 0 0
 1 1 1 1 1 1 1 1 1 1
  1 2 3 1 2 3 1 2 3
   1 5 2 1 5 2 1 5
    2 3 1 2 3 1 2
     1 1 1 1 1 1
      0 0 0 0 0
       -1

一番下に書いた $-1$ です。

2 次正方行列

#

本の定理 4.7 によると、$(a_1,\ldots,a_n)$ が奇蹄列のとき

$$\begin{pmatrix} a_1 & 1 \\ -1 & 0 \end{pmatrix} \begin{pmatrix} a_2 & 1 \\ -1 & 0 \end{pmatrix} \cdots \begin{pmatrix} a_n & 1 \\ -1 & 0 \end{pmatrix} =-\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$$

が成り立ちます。この等式を入試問題に応用できないでしょうか？

偶奇にのみ興味があるので、2 元体 $\mathbb{F}_2$ 上で考えます。ここで登場する行列はすべて行列式が 1 であることから、特殊線形群 $\mathrm{SL}_2(\mathbb{F}_2)$ を考えます。この群はどのような群でしょうか。

実は、$\mathrm{SL}_2(\mathbb{F}_2)$ は位数 6 の二面体群と同型です！

解法 3 の背後にはこのような性質があったのですね。

研究課題

#

ここまでフリーズを使って伝説の入試問題を考察してきましたが、まだまだわからないことや知りたいことがたくさんあります。ここに研究課題を並べておくので、ぜひ一緒に考えましょう。

解法 1 の解釈

#

解法 1 では交代和が登場しましたが、これにいい感じの「解釈」を与えることはできないでしょうか？

交代和と聞いて思い浮かぶのは包除原理やオイラー標数です。謎の不変量にこのような解釈を与えることができれば、背後に潜む構造が見えてくるかもしれません。

一筆書き

#

三角形分割においてグラフとして見たときの各頂点の次数を $(d_1,\ldots,d_n)$ とすると、これは奇蹄列に 1 を加えたものです。次数が奇数の頂点が 0 個または 2 個で、2 個の場合は隣り合っているようなものを考えることになります。これは一筆書きを連想させます。一筆書きを用いて証明できないでしょうか？

団代数との関連

#

三角形分割やフリーズは今流行りの団代数とも関連します。団代数を用いた解釈ができないでしょうか？

団代数は 21 世紀に生まれた数学なので、1998 年には存在していません。もしつながりがあるとすれば面白そうですね。

おわりに

#

これまでに知られている解法を調査しましたが、漏れがあるかもしれません。新たな別解を見つけたり、研究課題についてわかったことがあったりした場合はお知らせください。