【標準】対応させて数える（トーナメント戦の試合数を簡単に求める）

🕒 2017/01/11 🔄 2023/05/01

ここでは、数え方のテクニックとして、「対応させて数える」方法を見ていきます。

📘 目次

10階までのぼるのにどれだけかかる？

まずは、あまり場合の数とは関係しませんが、次のような問題を考えてみましょう。

「階段を使って1階から5階までのぼるのに1分かかる人が、同じペースで1階から10階までのぼるのにかかる時間は？」

瞬殺で「2分」と答えてしまいそうですが、そうではありません。

フロアを〇で表してみます。左が1階だとしましょう。
「〇〇〇〇〇」
左端の〇から出発して、右端まで移動するのに1分です。ここで、動き方に注目してみましょう。1階分上がると2階に移動します。もう一度上がると3階に移動します。つまり、「n 階分上がると、 $n+1$ 階に移動する」ということがわかります。

このことから、1階から5階まで移動するには、4階分上がればいいことがわかります。また、1階から10階までは9階分のぼればいいことがわかります。4階分のぼるのに60秒かかるので、10階までにかかる時間は\[ 60\div 4 \times 9 =135\]秒となります。

移動を考えるには、〇の数（階数）ではなく、〇の間の数（間にある階段の数）を考えないといけません。そして、その数は、
「〇の数が n 個　⇔　〇の間の数が $n-1$ 個」
という対応から数えることができます。

問題文の「5階と10階」が「50階と100階」だったとしても、小さい数字で実験して、「階の間の数は、最上階から1引けば求められる」と考えて出すことができます。

トーナメント戦の試合数は何試合か

【標準】ダブらせて数えるでは、総当たり戦の試合数を考えましたが、ここではトーナメント戦の試合数を考えてみましょう。うまく何かと対応させると、簡単に試合数を出すことができます。

チームを、Ａ，Ｂ，Ｃ，Ｄ，Ｅと書いて、このトーナメント戦を考えてみましょう。5チームなので、試合形式はいろいろ考えられますよね。

例えば、
　Ａ対Ｂ
　Ｃ対Ｄ
　2試合目の勝者対Ｅ
　決勝戦
という組み合わせ方があります。4試合ですね。他にも、
　Ａ対Ｂ
　その勝者対Ｃ
　その勝者対Ｄ
　その勝者対Ｅ
という組み合わせもあるでしょう。これも4試合です。ひょっとしたら、どんな組み合わせでも4試合になるのでしょうか。

5チームではなく、4チームで考えてみましょう。よくあるのは「Ａ対Ｂ」「Ｃ対Ｄ」「決勝戦」という組み合わせです。3試合です。5チームのときは4試合、4チームのときは3試合。ひょっとしたら、 n チームでトーナメント戦をすると、試合数は $n-1$ 試合になるのでしょうか。

実は、答えはYesです。でも、なぜそうなるのでしょうか。どう数えればいいでしょうか。

これは、試合ではなく、チームの方を数えるとうまくいきます。試合をするごとに、必ず1チームが負けます。負けたチームはそれ以降出てくることはなく、負けたチームが負ける回数は必ず1回です。なので、「試合」と「その試合で負けるチーム」が1対1に対応します。そのため、「試合数」と「負けたチームの数」は同じになります。

トーナメント戦では、優勝するチーム以外は、すべてのチームがどこかで負けます。なので、「負けたチームの数」は全体のチーム数から1引いたものになります。よって、 n チームでトーナメント戦をすると、試合数は $n-1$ 試合になる、ということがわかります（再試合などはないとしています）。100チームなら99試合だし、4000チームなら3999試合です（ちなみに、高校野球の参加校数は、だいたい4000程度です：部員数統計（硬式）｜資料｜公益財団法人日本高等学校野球連盟）。

特に、トーナメントの構成が関係しない、というのがおもしろいですね。

ここでは、「試合」と「負けチーム」が対応し、負けチームを数えるのは簡単だったので、試合数も楽に数えることができました。このように、「直接数えるのは難しい・めんどくさいが、別のものに対応させて数えると簡単に数えられる」という場面が、たまに出てきます。この「対応させる」テクニックを使って解く問題は難しいことが多いので、注意が必要です。