2016-06-30

東大の碁石の問題

高校数学

タイトルの問題は

東大文系2001 白石180個と黒石181個の合わせて361個の碁石が横に一列に並んでいる。碁石がどのように並んでいても、次の条件を満たす黒の碁石が少なくとも１つあることを示せ。
(＊)その黒の碁石とそれより右にある碁石をすべて除くと、残りは白石と黒石が同数となる。ただし、碁石が１つも残らない場合も同数とみなす。

です。シンプルな問題文の論証問題で、よく話題にもなり、見たことがある人も多いことと思います。ちなみに $361$ は平方数 $19^2$ です。初めて見る方はまず自分で考えてみることをオススメします。

私とこの問題出会いは高校の数学の定期テストにおいてでした。

当時、毎回ではないですが、定期テストの問題に「 $X$ 問題」が出題されていました。 $X$ 問題は通常の問題100点分とは別に、時間が余った人用の問題です(20点)。つまり、 $X$ 問題が出題されたときのテストでは100点を超えることが可能でした。

そして、高一のときのある回のテストで $X$ 問題としてこの問題が出題されました(もちろん、先生のオリジナル問題のときもあったと記憶しています(その方が多い？) )。

幸いにも私はこの問題を見たことがなかったので、早めに通常の問題を片付けてこの問題にワクワクしながら取り組み始めました。

高一ではまだ習っていないものの既に数学的帰納法を知っていた私は、この問題を数学的帰納法で解くことに決めました。つまり、白石の個数が $180$ 個とあるところを $n$ 個に一般化して解こうというのです。

途中までは上手くいきましたが、記憶では答案を書き終えた後に細かい論証のミスに気づいて消しゴムで消し、修復を試みるもタイムアップという感じでした。

無念。

その後、先生に解答を教わり、帰納法を用いずにシンプルに解けるのだなあと感動したものです。

標準的と思われる解法（背理法、中間値の定理の類似）

一列に並んだ碁石の左端の碁石が黒石の場合、その黒石と右側の碁石(つまり全部)を除くことによって題意が成り立つ。従って、以下では左端の碁石が白石である場合を考える。
左から数えて $1$ 番目から $n$ 番目の碁石までの

(白石の数)ー(黒石の数)

を $f(n)$ とする( $1 \leq n \leq 361$ )。今、 $f(1)=1, \ f(361)=-1$ であり、 $f(n+1)-f(n)=\pm 1 \ (1 \leq n \leq 360)$ なので、

$\displaystyle f(k)=0, \ f(k+1)=-1 \ (2 \leq k \leq 360)$

なる $k$ が存在する*1。このとき、 $f$ の定義から、左から数えて $k$ 番目までの碁石は白石と黒石の個数が同数であり、 $k+1$ 番目の碁石は黒石であることがわかる。よって、左から $k+1$ 番目の碁石である黒石が条件（＊）を満たす。 Q.E.D.

例えば、

○ ○ ○ ● ○ ● ● ○ ● ● ● ○ ○ ● $\cdots$

と並んでいるときは、

$\begin{equation}\begin{split}&f(1)=1, \ f(2)=2, \ f(3)=3, \ f(4)=2, \ f(5)=3, \ f(6)=2, \ f(7)=1, \\ &f(8)=2, \ f(9)=1, \ f(10)=0, \ f(11)=-1, \ f(12)=0, \ f(13)=1, \ f(14)=0 \dots \end{split}\end{equation}$

となっており、確かに左から $11$ 番目の黒石とそれより右側の碁石を取り除くと、11番目の黒石より左側には白石と黒石がともに5個ずつ並んでいることが分かります。

何故、碁石の問題のことを今思い出したのか。

私は今、エジプト分数に関するGrahamの定理についての記事を執筆しています。

論文が二つあって、一つ目を読み終わったのですが、当初の予想では「論文２は発展的内容で、欲しい定理の証明は論文１にあるはず」と思っていました。

ところが、この考えはあまく、、、、

実は「定理は論文１で宣言しているものの、論文１では準備となる定理を証明しており、所望の定理はその準備の定理を用いて論文２で証明される」という構造だったのです！！

はあ。。

こうして、記事を書くための準備にもう少し時間がかかりそうな状況なのです。

さて、論文１は読み終えたわけですが、その証明において東大の碁石の問題の解法(上記「標準的と思われる解法」)で用いた論法を何度も繰り返し用いています。

つまり、論文１を読んでいて碁石の問題を連想して高校時代の思い出が読みがえり、まだGrahamの記事が書けないから繋ぎとして碁石の問題の記事を書いちゃおうという魂胆なのでした。。。

これ以上ないシンプルな解法が存在するわけですが、高校時代に挑戦した数学的帰納法についても気になります。当時解けなかった高校生せきゅーんのために帰納法による解答も書いておきましょう。

数学的帰納法による解法１

定理１ $n$ を非負整数とし、白石 $n$ 個と黒石 $n+1$ 個の合わせて $2n+1$ 個の碁石が横に一列に並んでいる。碁石がどのように並んでいても、条件（＊）を満たす黒の碁石が少なくとも１つある。

証明. $n$ に関する数学的帰納法で証明する。 $n=0$ のときは自明。 $n$ で成立すると仮定して $n+1$ のときにも成立することを証明する。白石 $n+1$ 個と黒石 $n+2$ 個の合わせて $2n+3$ 個の碁石が一列に並んでいるとする。このとき、左端の碁石が黒石であればその黒石と右側の碁石(つまり全部)を取り除けばよいため、左端の碁石は白石であると仮定してよい。左端の白石と、左から数えて初めて現れる黒石を取り除いて得られる白石 $n$ 個と黒石 $n+1$ 個の合わせて $2n+1$ 個の碁石の列を考える。この列に関して帰納法の仮定によって、条件（＊）を満たす黒石が存在するが、その黒石は元の $2n+3$ 個の元の碁石の列についても条件（＊）を満たす。 Q.E.D.

白石と黒石を１つずつ取り除くことによって $n+1 \mapsto n$ と関連付けるアイデアです。高校でテストを受けていたときのアイデアはテキトーに*2白石と黒石を１つ取り除いて、その状況に応じて場合分けするというものでした。テストでは混乱して時間がなくなりましたが、ちゃんと論理の穴を埋めることができます。それも一応書いておきますが、テキトーには選ばずに左端の方から選ぶことによって上記証明のようにすっきりすることが分かります(同様に右端から選ぶ証明も書けます)。

高校のときのアイデアによる証明. $n$ に関する数学的帰納法で証明する。 $n=0$ のときは自明。 $n$ 以下で成立すると仮定して $n+1$ のときにも成立することを証明する。白石 $n+1$ 個と黒石 $n+2$ 個の合わせて $2n+3$ 個の碁石が一列に並んでいるとする。このとき、白石と黒石を１つずつテキトーに選んで取り除く。取り除いて得られる白石 $n$ 個と黒石 $n+1$ 個の合わせて $2n+1$ 個の碁石の列に帰納法の仮定を用いることによって条件（＊）を満たすような黒石が存在し、それを $F$ と名付ける。元の碁石の列において、最初に取り除いた白石と黒石（それぞれW, Bとする）とFとの位置関係によって以下のように場合分けする。