なかけんの数学ノート

【標準】ダブらせて数える

ここでは、場合の数を求めるときによく使う「ダブらせて数える」方法を見ていきます。

[広告]

総当たり戦の試合数は何試合か

ここでは、「5つのチームが総当たりのリーグ戦を行うとき、試合数は全部で何試合になるか」という問題を考えてみましょう。「総当たり」とは、「各チームが、他のすべてのチームと試合をする」ということです。

まずは、【基本】書き出して数えるで見たように、すべて書き出してみましょう。

チームを、A,B,C,D,Eと書きましょう。まずは、Aと戦う試合を書き出してみます。すると、対B,対C,対D,対Eの4試合あることがわかります。

次に、Bと戦う試合を書き出してみます。これも同じように考えると、対A,対C,対D,対Eになるような気がしますが、「B対A」という試合は、「A対B」の試合と同じですね。ダブってしまいます。なので、これを除いた「対C,対D,対E」の3試合があることがわかります。

続いてCと戦う試合です。対Aと対Bは、A対C、B対Cがすでに出ているので、ダブってしまいます。なので、「対D,対E」の2試合です。

続いてDです。これは「D対E」の試合しかありません。最後はEですが、Eが登場する試合はすでにすべて出てしまっています。

樹形図をかくと、次のようになります。
standard-overlap-and-count-01
今回は、【基本】まとめて数えるのときと違って、同じ構造が出てきません。なので、掛け算は使えません。総試合数は、それぞれの試合数を足し合わせて\[ 4+3+2+1=10 \]試合と求めることができます。

ダブらせて数えよう

基本的に、数えるときには、ダブらせて数えてはいけません。しかし、自分でコントロールできる場合には、「わざとダブらせて数える」という技が使えることがあります。上で見た「総当たり戦の総試合数」で使うことができます。

Aと戦う試合は、対B,対C,対D,対Eの4試合でした。次にBと戦う試合を考えたときに、「B対A」を除きましたね。ダブるからです。しかし、これをあえて残してみます

Cと戦う試合も「C対A」「C対B」を除きましたが残します。Dと戦う試合も、Eと戦う試合も同様です。Eと戦う試合は、4試合除きましたが、すべて残すことにします。

そうなると、「〇対△」という試合は、〇の部分には5チームが入り、△には〇チーム以外の4チームが入ります。なので、今の段階では、\[ 5\times 4=20 \]試合があることがわかります。

ただ、これだとダブっている試合が含まれているので、そのままでは答えになりません。ダブっている試合を除かないといけません。

「あとから除くのなら、はじめから除いておけばよかったのでは?」と思うかもしれませんが、実は、今のケースでは、とてもいいダブり方をしているんですね。

例えば、「B対E」という試合。これは「Bと戦う試合」でもカウントしたし、「Eと戦う試合」でもカウントしました。1つの試合を2回カウントしています。「A対C」という試合も「Aと戦う試合」「Cと戦う試合」として2回カウントします。「〇対△」という試合は、「〇と戦う試合」「△と戦う試合」の2回カウントされるんですね。

ということは、どの試合も2重にダブっていることがわかります。なので、2で割れば、求めたい試合数になります。つまり、\[ 5\times 4 \div 2=10 \]試合が求める試合数となります。たしかに、樹形図で求めたときと同じ結果になっています。

総当たりの試合では、次のような表を使うことがあります。
standard-overlap-and-count-02
これを見ると、斜線を引いた部分(自分対自分の試合)を除いた試合が $5\times 4=20$ 試合、斜線で折り返したときに重なる部分は同じ試合(B対EとE対Bなど)なので、すべての試合数は $20\div2=10$ 試合であることがわかります。

もちろん樹形図をかいて解くこともできますが、このようにあえてダブらせることによって簡単に解けることもあります。ここでは5チームでしたが、100チームなら樹形図をかいて解くことは事実上不可能です。しかし、ダブらせて数えるやり方だと、\[100\times99\div2=4950\]試合だ、と簡単に求めることができます。

おわりに

ここでは、ダブらせて数える方法を見てきました。ダブらせて数えたあとで、そのダブりを取り除くと、簡単に数えられるケースを見ました。このように、ダブらせて数える方法は今後もよく出てくるので覚えておきましょう。

[広告]
対象者: 数学A
分野: 場合の数と確率
トピック: 場合の数
レベル: 標準
キーワード: 場合の数
更新日:2017/01/11