東大2001年前期文系問題1

白石180個と黒石181個の合わせて361個の碁石が横に一列に並んでいる．
碁石がどのように並んでいても，次の条件を満たす黒の碁石が少なくとも1つあることを示せ．

その黒の碁石とそれより右にある碁石をすべて除くと，残りは白石と黒石が同数となる．
ただし，碁石が1つも残らない場合も同数とみなす．

左から $n$ 個までの碁石のうち黒石であるものの数から白石であるものの数を引いた値を $a_n$ とおく．
$a_0=0-0=0$ なので「 $a_{k-1}\leq0$ ならば $a_k\leq0$ 」が常に成立すれば $a_{361}\leq0$ だが $a_{361}=181-180=1$ より矛盾．
よって $a_{k-1}\leq0$ かつ $a_k>0$ なる $k$ が存在するが， $a_n$ は1ずつ増減するので $a_{k-1}=0,\ a_k=1$ ．
このとき， $k$ 番目の石は条件を満たす黒石である．

shaitan's blog

長文書きたいときに使う．

東大2001年前期文系問題1