トップ› 京都大学› 1975年› 理系第1問

京都大学 1975年理系第1問解説

方針・初手

参加チーム数を $n$ としたとき、各チームの試合数は $n-1$ である。引き分けがないため、各チームの勝ち数は $0$ から $n-1$ のいずれかの整数値をとる。「同順位のチームがなかった」という条件から、全 $n$ チームの勝ち数がすべて異なることを導き、各順位のチームの勝ち数を確定させるのが第一歩だ。その後、上位のチームから順に対戦結果を決定していくか、あるいは最上位のチームを除外してより少ないチーム数の問題に帰着させることで証明する。

解法1

大会に参加するチーム数を $n$ とする。各チームは自分以外の $n-1$ チームと1回ずつ試合を行うため、とりうる勝ち数は $0, 1, 2, \dots, n-1$ のいずれかである。

問題の条件より同順位のチームが存在しない、すなわち全チームの勝ち数が互いに異なるため、$n$ 個のチームの勝ち数はちょうど $0, 1, 2, \dots, n-1$ が1つずつ割り当てられる。順位は勝ち数の多い順に決まるため、$k$ 位（$1 \le k \le n$）のチームの勝ち数は $n-k$ である。

ここで、第 $k$ 位のチームに注目し、自分より上位の $k-1$ チームすべてに負けていると仮定する。このとき、第 $k$ 位のチームの敗北数は上位チームに対する少なくとも $k-1$ 敗があるため、残りの試合ですべて勝ったとしても、その最大勝ち数は

$$ (n-1) - (k-1) = n-k $$

となる。一方、第 $k$ 位のチームの実際の勝ち数は $n-k$ である。最大勝ち数と実際の勝ち数が一致しているため、第 $k$ 位のチームは残りの試合、すなわち自分より下位の $n-k$ チームとの試合にはすべて勝たなければならない。したがって、仮定が成り立てば、第 $k$ 位のチームは自分より下位のチームに必ず勝っていることになる。

この推論がすべての順位 $k$ について成り立つことを順を追って示す。 1位（$k=1$）のチームは勝ち数が $n-1$ であり、自分以外の全チームに勝っている。これは上位チームが存在しないため上記の仮定を空虚に満たし、実際に下位の全チームに勝っている。 2位（$k=2$）のチームは、1位のチームが全勝であることから1位に負けている。よって上位1チームに負けているという仮定を満たし、上記の論理から下位の全チームに勝っている。以下帰納的に、上位 $k-1$ チームがそれぞれ自分より下位の全チームに勝っているならば、第 $k$ 位のチームは上位 $k-1$ チームすべてに負けていることになり、下位の全チームに勝つことがいえる。

以上により、どの順位のチームも、それより下位のチームには必ず勝っていることが示された。

解法2

「1位のチームを取り除く」という操作を繰り返すことで帰納的に証明する。

参加チーム数を $n$ とし、題意を満たす大会について考える。解法1と同様に、各チームの勝ち数は $n-1, n-2, \dots, 0$ となり、1位のチームの勝ち数は $n-1$ である。勝ち数が $n-1$ であるということは、1位のチームは自分以外の残り $n-1$ チーム（すなわちすべての下位チーム）に勝っていることを意味する。

ここで、この大会から1位のチームと、そのチームが行った試合結果をすべて取り除く。残った $n-1$ チーム（元の2位から $n$ 位のチーム）について、取り除かれた1位のチームに対する対戦結果はすべて「負け」であった。したがって、1位のチームを取り除いたあとの $n-1$ チーム間で行われたリーグ戦のみを考えると、各チームの勝ち数は元の大会での勝ち数から変動せず、それぞれ $n-2, n-3, \dots, 0$ となる。これは、残った $n-1$ チーム間におけるリーグ戦においても「引き分けがなく、同順位のチームがない」という元の問題と同じ条件が保たれていることを示している。

この残った $n-1$ チームの中で最も勝ち数が多い（勝ち数 $n-2$）チームは、元の大会における2位のチームである。このチームは、残った集団のなかで全勝しているため、自分より下位の $n-2$ チームすべてに勝っている。以下同様に、その集団において一番勝ち数の多いチームを順次取り除いていく操作を繰り返すことにより、任意の時点での最上位のチーム（元の順位における各チーム）は、残っているすべての下位チームに勝っていることがわかる。

よって、どのチームもそれより下位のチームには必ず勝っていることが証明された。

解説

この問題は、リーグ戦における「勝ち数」と「順位」の関係を離散数学的に捉える問題だ。最大のポイントは、「引き分けなし」「同順位なし」という条件から、各チームの勝ち数が $0$ から $n-1$ までの連続する整数値になることを見抜く点にある。これが分かれば、勝ち数最大のチームが全勝であり、勝ち数最小のチームが全敗であることが直ちに導かれる。証明の記述においては、解法1のように上位陣との対戦結果から勝ち数の帳尻を合わせる方法や、解法2のように全勝チームを帰納的に除外して問題を縮小していく方法が有効だ。論理に飛躍や循環が生じないよう、言葉で丁寧に説明することが求められる。