東京大学 2001年 文系 第4問 解説

方針・初手

左から順に並んだ碁石について、黒石を $1$、白石を $-1$ として、左端からの総和を考える。 ある黒石に注目したとき、「その黒石とそれより右にある碁石を除くと、残りは白黒同数（または $0$ 個）」という条件は、注目した黒石の直前までの総和が $0$ であることと言い換えられる。 全体の総和が $1$ であることと、石が $1$ つ増えるごとの総和の変化が必ず $\pm 1$ であることに着目し、総和が最後に $0$ となる箇所を調べる。

解法1

左から $k$ 番目の碁石について、黒石であれば $x_k = 1$、白石であれば $x_k = -1$ とする（$k = 1, 2, \dots, 361$）。 左から $k$ 番目までの $x_i$ の和を $S_k$ とする。

$$ S_k = \sum_{i=1}^k x_i \quad (k = 1, 2, \dots, 361) $$

また、便宜上 $S_0 = 0$ と定める。 このとき、$S_k$ は左から $k$ 番目までの「(黒石の数) $-$ (白石の数)」を表す。

問題の条件「ある黒の碁石とそれより右にある碁石をすべて除くと、残りは白石と黒石が同数となる」を満たす黒石が左から $k$ 番目にあるとき、以下の2つの条件が成り立つ。

• $k$ 番目の碁石は黒であるから、$x_k = 1$
• $k-1$ 番目までの白石と黒石が同数（一つも残らない場合を含む）であるから、$S_{k-1} = 0$

したがって、「$x_k = 1$ かつ $S_{k-1} = 0$ を満たす整数 $k$ ($1 \le k \le 361$) が少なくとも一つ存在する」ことを示せばよい。

全体の碁石は黒石が $181$ 個、白石が $180$ 個であるから、

$$ S_{361} = 181 - 180 = 1 $$

である。

ここで、$S_0, S_1, \dots, S_{361}$ という数列において、値が $0$ となる項のインデックス（番号）の集合を考える。 $S_0 = 0$ であるため、この数列の中には値が $0$ になる項が少なくとも一つ（$S_0$）存在する。 そのような項の中で、インデックスが最大となるものを $M$ とする（$0 \le M \le 360$）。 $S_{361} = 1 \neq 0$ であるため、$M \le 360$ であることは保証されている。

$M$ は $S_M = 0$ となる最大のインデックスであるから、$M < i \le 361$ を満たす任意の整数 $i$ において、

$$ S_i \neq 0 $$

である。

また、$S_i$ は $1$ ステップごとに $+1$ または $-1$ される数列であり、値が正と負の間を移動する際には必ず $0$ を経由する。 $M < i \le 361$ において常に $S_i \neq 0$ であり、かつ終端が $S_{361} = 1 > 0$ であることから、$M < i \le 361$ の範囲では常に

$$ S_i > 0 $$

でなければならない。

これより、$i = M+1$ のとき

$$ S_{M+1} > 0 $$

が成り立つ。 一方で、$S_{M+1}$ の定義から、

$$ S_{M+1} = S_M + x_{M+1} = 0 + x_{M+1} = x_{M+1} $$

である。 $x_{M+1}$ は $1$ または $-1$ のいずれかの値しかとらないため、$x_{M+1} > 0$ より

$$ x_{M+1} = 1 $$

が確定する。

この結果は、$k = M+1$ としたとき、$x_{M+1} = 1$（$M+1$ 番目の碁石は黒石）かつ $S_{(M+1)-1} = S_M = 0$ が成り立つことを示している。 これは題意を満たす黒の碁石が少なくとも一つ存在することを意味しており、証明が完了する。

解説

黒石を $+1$、白石を $-1$ と数値化して累積和をとるアプローチは、白黒の並びに関する条件を数学的に処理するための典型的な手法である。 横軸に碁石の番号、縦軸に累積和をとった折れ線グラフ（ランダムウォーク）を想像すると視覚的に理解しやすい。 原点 $(0,0)$ からスタートして、終点が $(361, 1)$ になる折れ線を引くとき、「最後に $y=0$ となる点から次のステップ」は、終点が $y=1$ である以上必ず右上（$y=0$ から $y=1$ へ）向かう必要がある。この「右上へ向かうステップ」が条件を満たす黒石に対応している。 「最後に $0$ になる瞬間」という極端な場所に着目することで、背理法を用いずに鮮やかに存在を示すことができる。

答え

条件を満たす黒の碁石は少なくとも一つ存在する。

略（解法1の証明を参照）