次: 有理数値関数［02京大後期理系改題］ 上: 数学的帰納法か直接証明か 前: 数列の公約数［86東工大］

円周の分割［02東大文科］

問題     

円周上に $m$ 個の赤い点と $n$ 個の青い点を任意の順序に並べる．これらの点に より, 円周は $m+n$ 個の弧に分けられる．このとき，これらの弧のうち両端の点の色が 異なるもの個数は偶数であることを証明せよ. ただし，$m\ge 1$, $n\ge 1$であるとする．

方針

1.

個数についての数学的帰納法

2.

円周の2色分割への還元

解1

青色の個数$n\ (\ge 1)$を固定し，すべての$n$に対して赤い点$m$個で 題意が成立することを$m$に関する数学的帰納法で示す．

$m=1$のとき．赤点の両隣りの弧が両端の色が異なり，その他にはないので， 両端の点の色が異なる弧は2個で偶数．成立する．

$m=k$ のとき成立しているとして $m=k+1$ のときの成立を示す．

1つの赤い点を除くと 赤い点は$k$個になり数学的帰納法の仮定から命題は成立する．

その上で除いた赤い点1点を戻す．

戻した点の両隣が赤色なら両端の点の色が異なる弧の個数は増えない． 戻した点の両隣が青色なら両端の点の色が異なる弧のは2個増える． 戻した点の両隣が異なる色なら両端の点の色が異なる弧は増えない．

赤い点1点を戻すことによる変化の個数が常に偶数なので， $k+1$ のときも両端の点の色が異なる弧の個数は偶数である． 数学的帰納法により題意が示された．□

解2

隣りあう弧でそれぞれの両端が同色のものがあれば (したがってそれらの端はみな同色)はつないで一つの弧としていく． こうすると円周上に赤ばかりの弧と青ばかりの弧がいくつかでき，交互に並ぶ． 円周上に並ぶのでそれぞれ同数個ある．

赤ばかりの弧の境界点と隣りあう青ばかりの弧の境界の点で両端の点の色が 異なる弧が一つできる． 赤ばかりの弧一つに対して境界の端点は2個あるので，両端の点の色が 異なる弧は2の倍数個ある．□