東大後期数学 1998-3(2) の必要性の証明

1998年度の東大後期試験数学第3問(2)は、大学入試としては最も難しい問題だと言われています。問題文が冗長であるので、説明の都合もあり、自明な範囲で以下のように問題を書き換えます。

最初、白丸が1個ある。操作は以下の3つのいずれかを行う。（操作を繰り返すたびに、白丸と黒丸が一列に並んでいる状態が生じる。）

ア―隣り合う2つの丸の間に白丸を入れ、その2つの丸の色をそれぞれ別の色に変える。

イ―列の左端に白丸を追加し、元々左端にあった丸の色を別の色に変える。

ウ―列の右端に白丸を追加し、元々右端にあった丸の色を別の色に変える。

この操作を (n-1) 回繰り返して n 個の白丸が並んだ状態を作ることができるために n の満たすべき必要十分条件を求めよ。

答えは「nを3で割った余りが 0 か 1 であること」です。十分性は容易に示せるのですが、必要性の証明が問題となります。

数日前この問題を見て考えた時は必要性がまるで証明できず、しばらく考えた後に諦めました。昨夜はコーヒーを飲んだせいかなかなか寝付けず、この問題が解けていなかったことを思い出して考え込んでしまってさらに寝付けず、解けてしまってテンションが上がってさらに寝付けず、気づけば寝ていて今朝目覚めました。一応他の人の解き方も調べてみると楽しい証明がいくつもありましたが、自分の思い付いた証明は分かりやすさの点では優れていると思うので紹介しておきます。

（証明）

それぞれの黒丸で白丸のグループを区切り、それぞれのグループの個数を表す数列を作る。ただし、黒丸が隣り合っているとき、黒丸が左端か右端にあるときは、0個の白丸のグループがあるとする。例えば「黒白白白黒白黒黒白」なら「0, 3, 1, 0, 1」となる。この数列の「交代和」を考える。例えば、先ほどの例では交代和は 0 - 3 + 1 - 0 + 1 = -1 となる。

また、黒丸が偶数個ある状態を「正の状態」、奇数個ある状態を「負の状態」とする。

各操作によって状態の符号と交代和は以下のように変化する。（元の交代和を n とする。）

操作アでは、状態の符号は変わらず、交代和は n+3 または n-3 となる。
操作イでは、状態の符号は反転し、交代和は 2-n となる。
操作ウでは、状態の符号は反転し、交代和は元の状態が正ならば n-2、負ならば n+2 となる。

最初は正の状態で、交代和は1である。よって操作を繰り返したとき、交代和を3で割った余りは帰納的に、正の状態のとき 0 か 1、負の状態のとき 1 か 2 となる。全ての丸が白いときは正の状態なので、nを3で割った余りは 0 か 1 でなければならない。

（証明終わり）

補足：この議論を用いると、最初に白丸1個から始めて作れる色の並びの集合と、黒丸1個から始めて作れる色の並びの集合は共通部分を持たないということも示せます。黒丸1個から始める場合、最初は負の状態で交代和は0なので、操作を繰り返したとき、交代和を3で割った余りは帰納的に、正の状態のとき 2、負の状態のとき 0 となります。ゆえに2つの集合が共通部分を持たないことはすぐに分かります。