京都大学 2006年 文系 第5問 解説

方針・初手

輪に並んだ玉に対して、連続する $n$ 個の組に含まれる「白玉の個数」を関数として設定します。開始位置を1つずらしたときの白玉の個数の変化が $+1, 0, -1$ のいずれかであること（変化が連続的であること）を利用し、中間値の定理の離散版の考え方を用いて証明します。

解法1

玉の総数は $2k + (2n-2k) = 2n$ 個である。輪に並んだ $2n$ 個の玉に対し、時計回りに $1, 2, \dots, 2n$ と番号をつける（玉 $i+2n$ は玉 $i$ と同じものとする）。

位置 $i$ の玉から時計回りに連続する $n$ 個の玉の組を $S_i$ とし、組 $S_i$ に含まれる白玉の個数を $f(i)$ とおく。

輪をある2箇所で切って $n$ 個ずつの2組に分けることは、ある $i$（$1 \leqq i \leqq 2n$）を選んで、組 $S_i$ と組 $S_{i+n}$ に分けることと同値である。

白玉は全体で $2k$ 個あるから、

$$ f(i) + f(i+n) = 2k \quad \cdots \text{①} $$

が常に成り立つ。

次に、位置 $i$ から開始位置を1つずらして $S_{i+1}$ を考える。$S_{i+1}$ は $S_i$ から「玉 $i$」を除き、新たに「玉 $i+n$」を加えた組であるから、

$$ f(i+1) - f(i) \in \{-1, 0, 1\} $$

すなわち、$f(i)$ の値は隣り合う $i$ で高々 $1$ しか変化しない。

$f(1)$ の値で場合分けを行う。

(i)

$f(1) = k$ のとき

①より $f(1+n) = 2k - k = k$ となる。したがって $i=1$ を選べば、2組 $S_1, S_{1+n}$ ともに白玉が $k$ 個、黒玉が $n-k$ 個となり題意を満たす。

(ii)

$f(1) < k$ のとき

（$f(1) > k$ の場合は白玉と黒玉を入れ替えれば同様に示せる）

①より $f(1+n) = 2k - f(1) > k$ となるため、

$$ f(1) < k < f(1+n) $$

が成り立つ。$f(i)$ は $i=1$ から $i=1+n$ にかけて高々1ずつしか変化しない整数値の関数であり、始点が $k$ より小さく終点が $k$ より大きいことから、その途中には必ず $f(j) = k$ を満たす整数 $j$（$1 < j < 1+n$）が存在する。

このとき①より $f(j+n) = 2k - k = k$ となる。したがって、組 $S_j$ と組 $S_{j+n}$ のどちらも白玉が $k$ 個、黒玉が $n-k$ 個となり題意を満たす。

以上より、適当な2箇所でひもを切ることで、どちらの組も白玉 $k$ 個、黒玉 $n-k$ 個となるようにできることが示された。

解説

「離散版の中間値の定理」と呼ばれる、有名かつ強力な論法を用いた証明問題です。「半分に分ける」「ある特徴の個数を関数で表す」「全体との和が一定」「1つずらしたときの変化が $\pm1$ か $0$」というパーツが揃えば、この論法に持ち込むことができます。

一見するとどのように切る場所を見つけるか見当もつかないような問題ですが、関数の変化の連続性に帰着させる発想を知っていれば、とても論理的でスッキリとした解答を作ることができます。

答え

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