『数学のロジックと集合論』(田中一之・鈴木登志雄、培風館)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さんより別解をいただいた。
そのような黒石が存在しないとすると、左から数えて行って(ゼロを含めて)白黒同数になるばあいは、その右隣の石は白である。さらに数えて行くと、360個目についてもこのことが成り立つから、白石が黒石よりひとつ多いことになって、白石180黒石181と矛盾する。
— マーリン (@tokyomarlin) March 21, 2016
@tokyomarlin そのような黒石が存在しないと仮定すると、左端は白石である。このあと左から順に石を数えてゆくと、黒石の数が白石に追いついた途端、右隣が白石となって再び白石が上回るから、黒石が白石の数を上回る事態は一度も起こらずにすべて数え終わるはずである、と。
— ぼんてんぴょん(Bontenpøn) (@y_bonten) March 21, 2016
(追記2)@MarriageTheoremさんからも別解をいただいた。
某所で見かけた碁石の問題、
— MarriageTheorem (@MarriageTheorem) 2016年3月22日
・・・*!
・・*・・
・*・・・
*・・・・
↑と→だけで左下から「!」まで辿ると必ず「*」を右向きに超える瞬間がある(でないと右側の領域に移れない)ので、その直前までを残せばよい、んですよね(元ネタ知らないので元ネタの解答と同じな可能性もあるけど)