インテジャーズ

インテジャーズ

数、特に整数に関する記事。

東大の碁石の問題

タイトルの問題は

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

です。シンプルな問題文の論証問題で、よく話題にもなり、見たことがある人も多いことと思います。ちなみに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の定理についての記事を執筆しています。

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

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

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

はあ。。

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

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

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

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

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

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

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

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

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

W, BがともにFより右側にある場合
このときは、Fが元の列についても条件(*)を満たす。

W, BがともにFより左側にある場合
このときも、白石と黒石が1つずつ増えるものの、Fが元の列についても条件(*)を満たす。

BがFより左側にあり、WがFの右側にある場合
元の碁石の列において、左端からFの左隣までの碁石の列をSとする。このとき、S

(黒石の個数)=(白石の個数)+1

を満たす。よって、Sに対して帰納法の仮定により条件(*)を満たす黒石が存在し、それは元の碁石の列に対しても条件(*)を満たす。

WがFより左側にあり、BがFの右側にある場合
元の碁石の列において、左端からFまでの碁石の列をS_1、Fの右隣から右端までの碁石の列をS_2とする。このとき、

S_1は (黒石の個数)= (白石の個数)

S_2は (黒石の個数)= (白石の個数)+1

が成り立つので、S_2に対して帰納法の仮定により条件(*)を満たす黒石が存在し、それは元の碁石の列に対しても条件(*)を満たす。 Q.E.D.

4つの場合分けのうち、比較的複雑な後半部分が現れないようにしたものが1つ前に紹介した証明というわけです。

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

一方、主張を少し言い換えて、白丸の個数ではなく碁石全体の個数に関する数学的帰納法を用いれば、右端の碁石一つだけに着目してもう少しシンプルに証明できます。

定理2 nを自然数とし、白石と黒石を合わせてn個の碁石が横に一列に並んでいる。碁石がどのように並んでいても、(黒石の個数) > (白石の個数)であれば、条件(*)を満たす黒の碁石が少なくとも1つある。

証明. nに関する帰納法で証明する。n=1のときは明らか。nのときに成立すると仮定してn+1のときに証明する。白石と黒石を合わせてn+1個の碁石からなる列であって、(黒石の個数) > (白石の個数)なるものを考える。

右端の碁石が白石の場合
それを取り除いてできるn個の碁石からなる列は(黒石の個数) > (白石の個数)を満たすので、帰納法の仮定より条件(*)を満たす黒石が存在する。その黒石は元の碁石の列に対しても条件(*)を満たす。

右端の碁石が黒石の場合
それを取り除いてできるn個の碁石からなる列が(黒石の個数) > (白石の個数)を満たせば、同様に示される。(黒石の個数)=(白石の個数)の場合は右端の黒石が条件(*)を満たす。

Q.E.D.

「石」がゲシュタルト崩壊しました。

*1:この部分は厳密には背理法を用いよ。

*2:数学用語の適当と日常用語の適当は意味が異なりますが、後者をテキトーと表して区別しています。