東京大学 2001年度 前期日程 第2次学力試験文系数学 第4問

左から $j$ 個の碁石を見たとき、黒石の個数から白石の個数を引いた値を $d_j$ とおく。ただし、まだ何も見ていない状態を $d_0=0$ とする。碁石を1個右へ進むたびに、黒石なら値は1増え、白石なら値は1減る。

全体では黒石が181個、白石が180個であるから $d_{361}=181-180=1$ である。

ここで、$d_j=0$ となる $j$ のうち最大のものを $l$ とする。少なくとも $d_0=0$ なので、このような $l$ は存在する。また $d_{361}=1$ だから $l\mathrm{\ne }361$ であり、$l+1$ 番目の碁石が存在する。

もし $l+1$ 番目の碁石が白石であれば、$d_{l+1}=d_l-1=-1$ となる。しかし最後には $d_{361}=1$ であり、値は1個の碁石ごとに1ずつしか変わらない。したがって $-1$ から $1$ へ移る途中で必ず0を通る。これは $l$ が $d_j=0$ となる最後の位置であることに反する。

よって $l+1$ 番目の碁石は黒石である。この黒石とそれより右にある碁石をすべて除くと、左に残るのは最初の $l$ 個の碁石である。ところが $d_l=0$ なので、そこには黒石と白石が同数ある。したがって条件を満たす黒石が少なくとも一つ存在する。

左端からの「黒石数−白石数」を考え、
初めて値が1になる位置を選ぶ。
その一歩前は必ず0なので、選んだ黒石より左に白黒が同数残る。

左から $j$ 個までに含まれる黒石数から白石数を引いた値を
$d_j$ とし、$d_0=0$ とする。石を1個読むたびに
$d_j$ は黒石なら1増え、白石なら1減る。

全体では黒石が1個多いので$$d_{361}=1.$$そこで、左から見て初めて $d_j=1$ となる位置を $j$ とする。
1回の変化は $\pm 1$ だから$$d_{j-1}=0$$であり、$j$ 番目の石は黒石である。

この黒石とそれより右側の石をすべて除くと、
残るのは最初の $j-1$ 個である。
$d_{j-1}=0$ より、その中では黒石と白石が同数である。
$j=1$ の場合は何も残らず、これも問題文の約束により同数とみなされる。
したがって条件を満たす黒石が必ず存在する。