勝ち点パターンは何通りなのか考えた

「4チームの総当たり戦をやったときに、最終結果における勝ち点配分は何パターンあるんだろう？」というのが気になったので調べてみました。9-6-3-0 とか、5-5-4-1とか、そういうやつです。

試合数は 4C2=6試合、それぞれに（数え方にもよりますが）勝ち、引き分け、負けの3ケースとすると、順序を考慮すると（試合結果）全部で 3^6 = 729パターンになります。順序を考慮しないと、これはいくつに減るのでしょうか。

ちなみに、勝つと3点、引き分け1点、負けると0点という設定です。

プログラミングの要素は薄めの記事になります。

数学だと思って考える

場合の数の問題と思って考え始めました。よくある方針は「一つ選んだ変数によって全体を分割し、その変数を固定して数える」という感じでしょう。

自分が思い当たった変数は、

• 引き分けの試合数（全部引き分けの場合、5試合引き分けの場合、...）
• グループ内での1位チームの勝ち点（全勝9の場合、2勝1分で7...）
• 勝ち点の被りパターン（4チームが全て並ぶ場合、3チーム並ぶ...）
• 上位チームの負け数（1位2位が全勝の場合、1位が全勝2位1敗...)

などです。

1位の勝ち点で分割 (失敗談)

まずは1位の勝ち点で分割する方法を使いましたが、これといって効率的に数えられたわけでもなくただ頑張っただけで、だけど正解に1割ほど足りず...時間もそれなりに使ったので惨敗となりました。

上位チームの負け数

一度答えを知ってからこの方法にトライし、幾度となくミスを繰り返し（仮に試験の問題だったら絶対間違えてる）ましたが、網羅的に数えやすい方法でした。

1位2位のチームの負け数に加えて、負けの相手および引き分けの数を動かしながら分類します

- 1位2位ともに下位に負けなし
    - 引き分けが0試合 (9-6-3-0)
    - 引き分けが1試合 (引き分け0の6試合を一つずつ引き分けにする(6通り))
    - 引き分けが2試合 (引き分け1の全パターンについて、引き分けではない5試合を一つずつ引き分けにして、重複が出れば除く)
    - 引き分けが3試合 (引き分け2の全パターンについて、引き分けではない4試合を一つずつ引き分けにして、重複が出れば除く)
    - 引き分けが4試合 (引き分け5の5試合のうち、一つ勝ちにできる試合を探す)
    - 引き分けが5試合 (引き分け6の6試合のうち、一つ勝ちにできる試合を探す (当然1位チーム))
    - 引き分けが6試合 (3-3-3-3)
- 1位は負けなし、2位は下位に負けあり
    - 2位が3位に負けるとき
    - 2位が4位に負けるとき
- 1位は下位に負けあり
    - 1位が2位に負けるとき
        - 2位が下位に負けていないとき
        - 2位も下位に負けるとき
    - 1位が3位に負けるとき

「1位2位ともに下位に負けなし && 引き分けが3試合」のパターンが一番細かくて間違えやすいです。また、1位や2位に負けがある場合についてはパズル的に勝ち点が埋まってしまうので、漏れなく数えられているかが不安になります。

計算機で解く

まずは普通に

順序考慮ありのパターンを列挙し、単にsort して uniq を取る Ruby ¹ プログラムを書きました。

matches_patterns = []

# 各試合のパターン 3通り
score_patterns = [ [3, 0], [1, 1], [0, 3] ]

# 6試合分の全ケースを配列に入れる
score_patterns.each { |ab|
score_patterns.each { |ac|
score_patterns.each { |ad|
score_patterns.each { |bc|
score_patterns.each { |bd|
score_patterns.each { |cd|
  matches_patterns << [   ab, ac, ad,
                              bc, bd,
                                  cd]
}}}}}}

# puts matches_patterns.size
# => 729

points_patterns \
  = matches_patterns.map { |matches|
     ab, ac, ad,
         bc, bd,
             cd = *matches

     # 勝ち点を計算
     [
               ab[0] + ac[0] + ad[0],
       ab[1]         + bc[0] + bd[0],
       ac[1] + bc[1]         + cd[0],
       ad[1] + bd[1] + cd[1],
     ].sort
   }
puts points_patterns.uniq.size

答えは40だそうです。

モンテカルロ法風に解く

ただ正解を求めただけではあまり面白くなかったので、

何回もやれば全パターン出てくるやろ！

という解き方をしてみました²。

points_patterns = {}

10000.times do |n|
  matches_patterns = (0...6).to_a.map{ [[3,0],[1,1],[0,3]].sample } #あとでいじる★
  ab, ac, ad,
      bc, bd,
          cd = *matches_patterns

  points = [
            ab[0] + ac[0] + ad[0],
    ab[1]         + bc[0] + bd[0],
    ac[1] + bc[1]         + cd[0],
    ad[1] + bd[1] + cd[1],
  ].sort
  if ! points_patterns[points]
    points_patterns[points] = []
    if points_patterns.keys.size > 34 # 35種類目以上では、何回の試行で発生したかを出力しておく
      puts "#{points_patterns.keys.size} #{ points.join(" ") } #{ n }"
    end
  end
end

10回ほど試しましたが平均して694回の試行で答えに到達しました。一番かかったときで 1210回。10000も要らなかった。

派生して別の課題設定へ

上記のモンテカルロ法風のやり方は、「全試合の勝ち・引き分け・負けが等しく発生する」という条件です。この確率をいじってみたくなりました。

とりあえず前述の★の行を

  matches_patterns = (0...6).to_a.map{
    [
      [3,0],[3,0],[3,0],[3,0],[1,1],[1,1],[0,3]
    ].sample
  }

こうしてみます。これは今回の場合、

強い順に並んでいるとして、強い方のチームが勝つ確率が4/7、引き分けが2/7、負けが1/7

という配分の設定になります。

同じく10回試したところ平均して1280回で答え到達となりました。

なお、なかなか登場しなかったパターンは、

-	-	-	-	勝ち点

• | 1 | 3 | 3 | 7
  1 | - | 3 | 3 | 7
  0 | 0 | - | 1 | 1
  0 | 0 | 1 | - | 1

-	-	-	-	勝ち点

• | 3 | 3 | 3 | 9
  0 | - | 1 | 1 | 2
  0 | 1 | - | 1 | 2
  0 | 1 | 1 | - | 2

-	-	-	-	勝ち点

• | 3 | 0 | 1 | 4
  0 | - | 3 | 1 | 4
  3 | 0 | - | 1 | 4
  1 | 1 | 1 | - | 3

-	-	-	-	勝ち点

• | 1 | 3 | 0 | 4
  1 | - | 0 | 3 | 4
  0 | 3 | - | 1 | 4
  3 | 0 | 1 | - | 4

-	-	-	-	勝ち点

• | 1 | 1 | 1 | 3
  1 | - | 1 | 1 | 3
  1 | 1 | - | 1 | 3
  1 | 1 | 1 | - | 3

などです。全部引き分けの3333は、どちらの確率設定でも一番のレアケースでした。3333 は729パターンのうちの1パターンでしか現れません。引き分け確率が 2/7 に減ったことでさらにレアケースになったと思われます。引き分けのバリエーションが少ないことを考慮すると、引き分け確率をあげて試せば少ない試行回数で答えが得られる...と思ったのですがパッと見そうでもなさそうでした。

10回はちょっと少ないので、試行回数を増やせば他にも何か見えてくるかもです。

残っている疑問

数学的にエレガントな解法

前述の通り、机上の問題としては割とマッチョな方法でゴリゴリ数えることしかできませんでした、何かエレガントな解き方はあるのでしょうか。

合計数729への道

「順序を考慮しない場合」に何通りかという話では、それぞれが「順序を考慮した場合」何通り発生するかを足し合わせれば、順序を考慮した場合の総数になるはずです。

たとえば、9-6-3-0 は 4! 通り、4-4-4-3 は4通り、といった具合です。

が、今回の問題では単に勝ち点を見て足しても、729には到達しません。見つけた例としては、7-4-4-1 のパターンは36回発生するとのことです。これももうちょっと細かく調べないと分からなさそうです（めんどい・・・

1. 個人的に慣れているという理由だけで Ruby を採用。 ↩

2. 自分の理解だとモンテカルロ法そのものではないので、あくまでモンテカルロ法「風」。 ↩