YONのドバトブログ

YONの土鳩ブログ

ゲーム好きの鳩"YON"がツイッターでは言い切れないことについて書き連ねるブログ

【数学】n人のリーグ戦で上位m位以内に入るには何勝が必要か?

急いでいる人がいるかもしれないので先に解答を書く。

 n人のリーグ戦で「確実に」上位m位以内に入るには、

 f:id:YON_4:20170117114752p:plain 勝が必要。

 n人のリーグ戦で上位m位以内に入るには、「少なくとも

 f:id:YON_4:20170117114701p:plain 勝が必要。

 ただし、f:id:YON_4:20170117114955p:plainはX以上の最小の整数を表す(端数切り上げを意味する)。

 

リーグ戦、総当り戦は初心者のプレイヤーも上級者のプレイヤーと同じ回数だけ試合を行える便利な試合形式であり、スマブラ大会の予選でもよく採用されている。この記事では最もメジャーである、総当りの回数が1回のリーグ戦のみを扱う。 *1

ところで、n人のリーグ戦で「確実に」上位m位以内に入るには何勝が必要なのだろうか?これは具体的な数値を入れると非常に簡単な問題に見えるが、案外直感と反する解答が出る。

記事の前半でウメブラSGC予選を例にとって具体的な場合を扱い、後半では一般的な場合を扱う。

 

具体例:「12人リーグ、上位6名通過」の場合

以前私は、ツイッターでこのようなアンケートツイートを流した。

これは、上記の問題にてn=12, m=6とした場合であり、12人のリーグ戦で「確実に」上位6位以内に入るためには何勝が必要だろうか?という問題である。多くの人は11戦中7勝すれば十分予選を突破できると考えており、確かに実際のケースを考えると7勝で予選通過できる場合がほとんどなのだが、実は「確実に」予選を突破するには9勝が必要である。つまり3敗した時点で予選落ちの可能性がある。こちらの表を見てみよう。

f:id:YON_4:20170116041351p:plain

黄色で強調した7位のプレイヤーは、8勝3敗という成績であるが予選落ちする。これは考えうる中で最悪のケースであり、予選を確実に突破するには9勝が必要である。

 

数学的に求めてみよう。今回求めるべきなのは7位のプレイヤーの勝数の最大値である。7位のプレイヤーはギリギリ予選落ちするプレイヤーなので、このプレイヤーよりも多く勝てば確実に予選を通過できる。7位のプレイヤーが最も勝数を稼ぐのは、1位から7位のプレイヤーが同数の勝利を収めたときである。

プレイヤーが12人いるので、全試合数は12C2 = 66(試合)となる。すなわち、リーグ戦全体で66の「勝ち」が生まれることになる。8位から12位の下位5人のプレイヤー同士の試合は5C2 = 10(試合)あるので、下位同士で10勝がやりとりされる。よって、1位から7位の7人のプレイヤーが持てる合計勝数の最大値は 66-10 = 56(勝)であり、上位1人あたり 56/7 = 8(勝)である。したがって、7位の勝数の最大値は8勝であるので、9勝すれば確実に予選を通過できる。

 

次に、このような問題を考えてみよう。この12人のリーグ戦で上位6位以内に入るためには「少なくとも」何勝が必要だろうか?個人的には、多くの人は5勝くらいと予想すると思うのだが、本当の解答はそれよりもずっと少ない。実は3勝すれば予選突破の可能性がある。表を見てみよう。

f:id:YON_4:20170116043955p:plain

黄色で強調した6位のプレイヤーは、3勝8敗という成績であるが予選を通過する。これは考えうる中で最も幸運なケースであり、予選を突破するには少なくとも3勝が必要である。

では、また数学的に求めてみよう。今回求めるべきなのは6位のプレイヤーの勝数の最小値である。6位のプレイヤーの勝数が最小となるのは、1位から5位までのプレイヤーが可能な限り多くの勝数を獲得し、6位から12位の7人のプレイヤーが均等に勝利する場合である。

リーグ戦全体で66の「勝ち」が生まれるのは前述の通り。先程と同じ導出により、上位5人に分配できる勝数の最大値は 66 - 7C2(勝)であり、このとき下位7人に分配できる勝数は 66 - (66 - 7C2) = 7C2 = 21(勝)である。下位1人あたりの勝数は 21/7 = 3(勝)。これが6位から12位の平均勝数となるので、ちょうど3勝すれば6位になって予選を突破する可能性がある。

 

一般的な場合:n人リーグ、上位m人通過の場合

上位m位に確実に入るために必要な勝数を求める。n-(m+1) >= 2のとき(下位同士で試合をするか否かで場合分けが必要)、上位m+1(人)に分配できる勝数の最大値は

f:id:YON_4:20170117180447p:plain.

ここで、

f:id:YON_4:20170117175143p:plain

であるから、

f:id:YON_4:20170117180401p:plain

となる。これが上位m+1(人)に分配できる勝数の最大値なので、これを超える勝数を収めれば確実に上位m人に入ることができる。この数が整数のときは1を加えた数だけ勝てばよく、そうでない場合は端数を切り上げた数だけ勝てばよい。これをガウス記号(端数切捨)を用いて表すと、

f:id:YON_4:20170117182809p:plain

となる。

以上の結果はn-(m+1) >= 2のときのものだったので、別の場合を考える。n-(m+1) = 1, すなわち m = n-2 のとき、求める勝数は

f:id:YON_4:20170117182633p:plain

一方、(1)式より

f:id:YON_4:20170117183007p:plain

であるので、一致する。

次に、n-(m+1) = 0 すなわち m = n-1 のときを考える。このとき予選落ちするのは1人だけなので、全員が均等に勝つ場合の1人あたりの勝数よりも多くの勝ちを収めれば確実に予選を通過できる。1人の試合数はn-1(試合)なので、全員均等に勝つならば1人あたり(n-1)/2勝するはずである。よって求める勝数は

f:id:YON_4:20170117183545p:plain

となる。一方、(1)式より、

f:id:YON_4:20170117183636p:plain

であるので、一致する。

以上より、いずれの場合も(1)式が求める勝数となる。(1)式を天井関数(端数切上)を用いて表すと、

f:id:YON_4:20170117181742p:plain

となる。

 

では、上位m人に入るために最低限必要な勝数を求める。下位n-(m-1)(人)の1人あたりの勝数の最小値は

f:id:YON_4:20170117184426p:plain

である。これが整数ならばこれと等しい勝数を収めれば予選突破の可能性があり、そうでない場合は端数を切り上げた数だけ勝てば予選突破の可能性がある。よって求める勝数は

f:id:YON_4:20170117184713p:plain

 

以上をまとめると、以下のような解答になる。

 n人のリーグ戦で「確実に」上位m位以内に入るには、

 f:id:YON_4:20170117114752p:plain 勝が必要。

 n人のリーグ戦で上位m位以内に入るには、「少なくとも

 f:id:YON_4:20170117114701p:plain 勝が必要。

 ただし、f:id:YON_4:20170117114955p:plainはX以上の最小の整数を表す(端数切り上げを意味する)。

 

おまけ

この結果だが、個人が予選通過のための目標を定める以外に、大会運営の効率化に利用することができる。つまり、予選突破確定者と予選敗退確定者がリーグ戦進行中でもはっきり分かるため、両者の間の試合は行わなくてよく、省略することができる。勿論、途中までの試合結果を使えばもっと厳密に不要な試合を求めることができるが、進行表を紙で管理する大半の場合では、こちらの手法の方が手間が少なく、適している。

しかし、そもそも予選でリーグ戦が採用されているのは、弱いプレイヤーでも多くの試合を経験できるからという理由もあるので、無闇に試合を省略するのはあまり望ましくない。進行具合に応じて適宜利用するのが良いだろう。

 

ちなみに、トーナメント形式(シングリエリミネーションやダブルエリミネーション)については別記事で考察している。

 

 

*1:英語圏ではリーグ戦はRound-robin tournamentと呼ばれることが多いが、これは厳密には総当りの回数が2回以下のリーグ戦を指す