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

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

【広告】

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引けば求められる」と考えて出すことができます。

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

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

チームを、A,B,C,D,Eと書いて、このトーナメント戦を考えてみましょう。5チームなので、試合形式はいろいろ考えられますよね。例えば、「A対B」「C対D」「2試合目の勝者対E」「決勝戦」という組み合わせ方があります。4試合ですね。他にも、「A対B」「その勝者対C」「その勝者対D」「その勝者対E」という組み合わせもあるでしょう。これも4試合です。ひょっとしたら、どんな組み合わせでも4試合になるのでしょうか。

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

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

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

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

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

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

おわりに

ここでは、何かに対応させて数える方法を見てきました。ただ、この技はいつ使うかわからない上、何に対応させるかは場面によって異なります。初見でこのテクニックを使うのは難しいことが多いので、見かけたときはどんどん吸収して使えるようにしましょう。