読者です 読者をやめる 読者になる 読者になる

碁石の問題(東大入試)

『数学のロジックと集合論』(田中一之・鈴木登志雄、培風館)p30、問題0.4に、東大文系の入試問題が採録されている。同書を読むたびにこの問題を解き直してしまって先に進まないので、ここに自分の解答をメモしておく。

【問題】白石\(180\)個と黒石\(181\)個の合わせて\(361\)個の碁石が横に一列に並んでいる。碁石がどのように並んでいても、次の条件をみたす黒の碁石が少なくとも1つあることを示せ。

「その碁石とそれより右にある碁石をすべて除くと、残りは白石と黒石が同数となる。」

ただし、碁石が1つも残らない場合も同数とみなす。

【解答】黒石が白石よりも\(1\)個だけ多い碁石の並びに対して、このような黒石が存在することは、「碁石の並びを(白黒同数)黒(白黒同数)となるように分割できる」ことであると言い換えられる。ただし「白黒同数」とは、白石も黒石も\(0\)個である場合を含む。以下、これを「分割可能である」と表記し、境目にある黒石を「境界石」と呼ぶことにする。\(P(n)\)を「白石\(n\)個、黒石\(n+1\)個の並びに対し分割可能」とおき、数学的帰納法により、すべての(\(0\)を含む)自然数\(n\)に対して\(P(n)\)が成り立つことを証明する。
[1] 白石\(0\)個、黒石\(1\)個の場合、この黒石を境界石として分割可能であるので、\(P(0)\)が成り立つ。
[2]\(k\)を自然数とし、\(n\leq k\)なるすべての自然数\(n\)に対し\(P(n)\)が成り立つと仮定して、\(P(k+1)\)を導く。
白石\(k+1\)個、黒石\(k+2\)個の並びから、まったく任意に白石と黒石を\(1\)個ずつ隠す。すると白石\(k\)個、黒石\(k+1\)個が残り、帰納法の仮定から分割可能である。隠した\(2\)石は各々、境界石の左または右のいずれかにあるはずであるが、両者が境界石の同じ側にある場合は、隠すのをやめても、やはり同じ境界石によって全体が分割可能である。いっぽう\(2\)石が互いに境界石の反対側にある場合は、全体を「隠した白石のある側\(A\)」と「隠した黒石のある側\(B\)」に分け、境界石は\(A\)のほうに含める。2石を隠すのをやめると、\(A\)は白黒同数に、\(B\)は「白\(m\)個、黒\(m+1\)個」(ただし\(m\leq k\))という状態になる。すると再び帰納法の仮定により\(B\)は分割可能であり、この際の新しい境界石によって全体が分割可能となる。■

(追記1)Twitterにて@tokyomarlinさんより別解をいただいた。


(追記2)@MarriageTheoremさんからも別解をいただいた。