試合数を数える

 部活動に青春を燃やしている高校生諸君も多いと思います.目指すはインターハイ!
 さて,部活動はやはり試合に出て勝つことがやはり目標ですよね.(勝つことだけが目的ではないですが...) そんな試合の代表的な方式が,総当たり戦(リーグ戦)と勝ち抜き戦(トーナメント戦)ですね.予選はリーグ戦で決勝はトーナメント戦というのも多いようですが.
 そんな試合の数を求める方法を考えてみましょう.

@総当たり戦(リーグ戦)

 次の図のように4チームでリーグ戦を行うと6試合,6チームだと15試合必要になります.一般にnチームが参加したときの試合数はどうなるでしょう.

 試合というのは2チームで戦いますね.そんな対戦する2チームを全nチームから選べばよいので試合数は
     n2 試合
で求まることになります.

A勝ち抜き戦(トーナメント戦)

 次の図のように8チームでトーナメント戦を行うと15試合,13チームだと12試合必要になります.一般にnチームが参加したときの試合数はどうなるでしょう.

 なんとなく予想が付きそうですね.そうです
      n−1 試合
必要になります.では何故そんな簡単な式で求めることができるのでしょう.
 1試合あると一方が勝ってもう片方が負けることになります.試合が1つあるごとにそのチームはその次の試合に出れません.つまり負けたチームの数だけ試合があることになります.
 n−1の“1”は負けなかったチーム,すなわち優勝したチームのことを言っていたわけです.