トップ› 大阪大学› 1970年› 理系第4問

大阪大学 1970年理系第4問解説

方針・初手

5つの国から異なる2つを選ぶ組合せの数を求め、必要な「手をつなぐ箇所」の最小数を考える。これにより人数の下限を評価し、その下限人数で実際に条件を満たす並び方が存在するかを具体的に構成して示す。

解法1

5つの国をそれぞれ A、B、C、D、E とし、輪をつくる人数を $n$ 人とする。

異なる2つの国の選び方は、

$$ {}_5\mathrm{C}_{2} = \frac{5 \cdot 4}{2 \cdot 1} = 10 $$

より、$10$ 通りである。

$n$ 人が手をつないで1つの輪をつくるとき、隣り合う2人のペア（手をつなぐ箇所）は全部で $n$ 箇所ある。

題意を満たすためには、上記で求めた $10$ 通りの国籍のペアが、輪の中に少なくとも1回ずつ現れる必要がある。1箇所で手をつなげるのは1組のペアのみであるから、手をつなぐ箇所の総数 $n$ は少なくとも $10$ 以上でなければならない。よって、

$$ n \geqq 10 $$

が必要である。

次に、$n=10$ のときに条件を満たす輪が実際につくれるかどうかを調べる。 $10$ 人が以下の順に手をつないで輪をつくったとする（右端の E は左端の A と手をつなぐものとする）。

$$ \mathrm{A - B - C - A - D - B - E - C - D - E} $$

この輪において、手をつないでいる隣り合う2人の国籍のペアを順に書き出すと、以下のようになる。

A と B
B と C
C と A
A と D
D と B
B と E
E と C
C と D
D と E
E と A （右端と左端）

この $10$ 個のペアの中には、AからEの異なる2つの国の組合せ $10$ 通りがすべて1回ずつ重複なく現れている。したがって、この並び順であれば、$10$ 人で条件を満たす輪をつくることができる。

以上より、求める最小の人数は $10$ 人である。

解説

グラフ理論における「オイラー閉路（一筆書き）」を背景とする問題である。

5つの国を頂点、異なる国の人同士が手をつなぐことを辺とみなすと、5つの頂点のすべてが互いに結ばれた完全グラフ（辺の総数は $10$）を考えることになる。このグラフはすべての頂点の次数が $4$（偶数）であるため、すべての辺をちょうど1回ずつ通って元の頂点に戻る「オイラー閉路」が存在することが保証されている。

解答においては、必要条件から人数の下限が $10$ であることを示し、実際に $10$ 人で題意を満たす例を1つ構成して提示するのが最も簡明かつ確実な方針である。