$n$ を正整数とする。白石 $n$ 個と黒石 $n+1$ 個の合計 $2n+1$ 個の碁石が横一列に並んでいる。どのように並んでいても、ある黒石が存在し、その黒石とそれより右にある碁石をすべて除くと、残りは白石と黒石の数が同数になることを示せ。ただし、碁石が一つも残らない場合も同数とみなす。

1. 問題の内容

$n$ を正整数とする。白石 $n$ 個と黒石 $n+1$ 個の合計 $2n+1$ 個の碁石が横一列に並んでいる。どのように並んでいても、ある黒石が存在し、その黒石とそれより右にある碁石をすべて除くと、残りは白石と黒石の数が同数になることを示せ。ただし、碁石が一つも残らない場合も同数とみなす。

2. 解き方の手順

左から $i$ 番目の碁石について、左から $i$ 番目までの黒石の数から白石の数を引いた値を $d_i$ とする。

$d_0 = 0$ と定義する。

$d_i$ は黒石なら1増え、白石なら1減るので、必ず整数である。

$d_{2n+1} = (n+1) - n = 1$ である。

もし $d_i = 0$ となる $i$ が存在すれば、左から $i$ 番目までの石を除くと、残りの黒石と白石の数は等しくなり、題意は満たされる。

$d_i$ がすべて $0$ でない場合を考える。

$d_{2n+1} = 1$ なので、少なくとも１つの $d_i$ は正である。

$d_0 = 0$ なので、負の値をとる $d_i$ も存在すると仮定する。

このとき、 $d_0=0$ であり、$d_{2n+1} = 1$ であるから、$d_i$ が初めて正の値をとる場所が存在する。

その場所を $k$ とすると、$d_{k-1} \le 0$ であり、$d_k > 0$ である。

$d_k - d_{k-1} = 1$ であるから、$d_{k-1} = 0$ または $d_{k-1} = -1$ である。

$d_i$ がすべて正である場合は、 $d_i$ は $1$ から $n+1$ までの整数であり、$k=1$ とする。

$k$ 番目の黒石より右の石を取り除くと、それより左の黒石の数から白石の数を引いた値は $d_k > 0$ である。

したがって、 $k$ 番目の黒石の左側には $d_k$ だけ黒石が多いことになる。

残りの $2n+1-k$ 個の石を取り除いた後、残っている石の数は $k-1$ 個である。

$k-1$ 個の石の中には、$b$ 個の黒石と $w$ 個の白石がある。

$b - w = d_k$ である。

$b+w = k-1$ である。

$2b = d_k + k - 1$ となる。

$d_k + k - 1$ が偶数であれば、$2b$ は偶数となり、$b$ は整数となる。

一方、$2w = k-1 - d_k$ となる。

$k-1 - d_k$ が偶数であれば、$2w$ は偶数となり、$w$ は整数となる。

$n+1$ 個の黒石があるので、$d_i = 0$ となる $i$ がない場合は、黒石が隣り合っている箇所が存在する。

このとき、その左側の黒石を取り除くと、白石と黒石の数は等しくなる。

3. 最終的な答え

白石 $n$ 個と黒石 $n+1$ 個の合計 $2n+1$ 個の碁石が横一列に並んでいるとき、ある黒石が存在し、その黒石とそれより右にある碁石をすべて除くと、残りは白石と黒石の数が同数になる。