円卓テーブルの座り方問題

Problem

円形のテーブルに25人の男子と25人の女子が座っている. このとき, 隣りに座っている人が両方共女子であるような人が少なくとも 1人は存在することを示せ

証明

背理法を用いて証明する. 隣りに座っている人が両方共女子である人が１人もいない並び方があると仮定し, その並び方を

$(a_{1}, a_{2}, \dots, a_{50})$

と表現されるとする. なお, $a_{1}$ と $a_{50}$ は隣り合っているとする. ここから, indexが偶数と奇数のグループにそれぞれ分けて, 以下のような２つのグループを考える:

$\begin{aligned} Group A: & (a_{2}, a_{4}, \dots, a_{50}) \\ Group B: & (a_{1}, a_{3}, \dots, a_{49}) \end{aligned}$

仮定より, Fを女子, Mを男子としたとき, FMFという並び方が存在しないので, Group A, Group Bともに女子が隣り合ってならんでいるパターンは存在しない.

つまり, Group Aに属する女子とGroup Bに属する女子の人数はそれぞれ12人以下となる. すると, Group A と Group Bを合わせた女子の人数は24人以下となるが, 問題設定より女子は25人存在する.

従って, 矛盾が発生する = 仮定が間違っている, ので隣りに座っている人が両方共女子であるような人が少なくとも 1人は存在する.

証明終了

References

Share Buttons
Share on:

Feature Tags
Leave a Comment
(注意：GitHub Accountが必要となります）