空論上の砂、楼閣上の机。

The Castle of Indolence

2001年 東大文系数学 第4問

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

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

一般的には, 左から数えて $1$ 番目から $n$ 番目の碁石までの白石の数から黒石の数を引いたものを $n$ の関数と考えて, 離散的な中間値の定理を考えることで証明することが多いのですが, 次のように証明することも可能です.

補題. $f\colon \{0,\dots,n\}\to\{0,\dots,n\}$ は広義単調増加なら不動点をもつ.
略証. 不動点をもたないならば $f({} ^ {\forall} l)>l$ が帰納的に従うが $f(n)\leqq n$ より矛盾.
証明. 黒石を左から順に $B_0,$ $\dots,$ $B_{180}$ とする. $B_n$ より左にある白石の個数を $F(n)$ とすると $F\colon\{0,\dots,180\}\to\{0,\dots,180\}$ は広義単調増加写像となり補題から不動点 $k$ をもち, $B_k$ が題意を満たす黒石でる.