トーナメントは運か実力か(解析解編)

先日の第7回日曜数学会で福原和朗さんが「トーナメントは運か実力か」という大変面白いLTをしておられました。今回は福原さんのLTを受けて、私が見つけた数式について発表させていただきます。

福原さんのLTに関しては下記のリンクのブログにまとめられております。

発表
第７回日曜数学会で発表してきました。 - kazurof weblog

福原さんは後述するある確率の数値解(←コンピュータ等を用いた計算による数値で与えられる解)を発表されたのですが、LTの後に、「必ず確率を文字式で解を表せるよね(つまり解析解(←問題を特徴付ける変数で表された代数的な解)が得られるよね)」と2人で会話させていただきました。先日のMathPowerで行われた素数大富豪のトーナメント表を見てそのことを思い出し、無事に解析解を見つけることができましたので、ここに発表したく思った次第です。

本記事の数学面の説明は、高校レベルの確率(特にコンビネーション $\mathrm C$ の使い方、赤い玉と白い玉が入っている袋から玉を取り出す系の確率の問題の解き方、何人かを一列に並べて特殊な並べ方の場合の数を求める方法)を習得している人を想定して記載しております。ただ高校確率の知識がない方でも問題の設定は理解していただけると思いますので、こういった現実的な問題を数学を使って解くことができるということ、つまり数学の力を感じていただけたら幸いです。

始まり、始まり
f:id:mattyuu:20161016085420j:plain
↑
「トーナメントは運か実力か(解析解編)」というタイトルで発表させていただきます。

夏の高校野球やリオオリンピックの柔道は負けたら終わりのトーナメント方式ですね(オリンピックの柔道に関しては敗者復活戦があるため完全に負けたら終わりというわけではありませんが)。トーナメントでは第1回戦で実力が1位と2位の人が戦ったら、2位の人は初戦敗退となってしまいます。また、実力がない人でもたまたま対戦相手が自分よりも下の実力であれば、第二回戦、第三回戦と勝ち進むことができます。理不尽だな、と思った経験はないでしょうか。

(余談ですが、駒大苫小牧高校は2004年、2005年と夏の甲子園を連覇しております。そしてなんと2006年の夏も甲子園の決勝まで行っているんです。この2006年の決勝こそ歴史に残る引き分け再試合となった、「ハンカチ王子こと斎藤佑樹」VS「マー君こと田中将大」なんです。夏2連覇して、その翌年の夏も決勝まで進むとは、駒大苫小牧の実力やばいですね。)

数学の確率を使えば理不尽なことがどれほど起こり得るのか、ということを定量的に表すことができます。では問題設定を行います。

f:id:mattyuu:20161016085425j:plain
↑
$n$ を正の整数として、 $2^n$ 人が参加するトーナメントを考えます。ただしトーナメントは上図のような綺麗な形のトーナメントを考え、シードがあったり、参加者によって優勝するまでに必要な勝利数が異なったりしないものとします。

参加者を $2^n$ 人(つまり2人、4人、8人、16人、、、)という人数に縛るのは綺麗な形のトーナメントにするために必要な条件となります。 $2^n$ という制約を課すことで第1回戦、第2回戦、第3回戦、、、という風に第 $k$ 回戦終わるごとに勝ち残っている参加者の数が半分になり続け、第 $n$ 回戦で1人になる(つまり優勝者が決まる)綺麗な形のトーナメント表を作成することができます。綺麗な形のトーナメントという数学的ではない表現が出てしまっておりますが、その意味するところはわかっていただけると思います(ちなみに数学的には完全2分木という言葉で表します)。

f:id:mattyuu:20161016085429j:plain
↑
参加者には「強さ」を示す数値があらかじめ与えられており、各試合では「強さ」が大きい参加者が必ず勝つものとします。
「強さ」は1から $2^n$ までの整数値をとり、参加者の「強さ」はそれぞれ異なるものとします。つまり、1から $2^n$ までの各整数値が $2^n$ 人の参加者一人一人に対して重複なく割り振られているものとします。

「強さ」 $2^n$ を持つ参加者はランキング1位、「強さ」 $(2^n-1)$ を持つ参加者はランキング2位、「強さ」1を持つ参加者はランキング $2^n$ 位(つまりビリ)となります。毎回『「強さ」 $x$ を持つ参加者』と書くのは大変ですので、今後は『「強さ」 $x$ を持つ参加者』のことを $x$ さんと呼ぶことにしましょう。

f:id:mattyuu:20161016085449j:plain
↑
上述した設定の元、本記事の問題はこのようになります。

トーナメント表をランダムに組むという意味は、 $2^n$ 人の参加者をランダムに一列に並べ、トーナメント表の一番下に据えるということになります。

各試合では「強さ」が大きい参加者が必ず勝つため、 $2^n$ さん(つまり「強さ」 $2^n$ を持つ参加者)が必ず優勝しますし、1さん(つまり「強さ」1を持つビリの参加者)は必ず初戦敗退します。2さんは初戦が1さんでなければ第2回戦に進みますが、第2回戦では必ず負けるでしょう。 $P_{a,b}$ で $a$ さんがちょうど $b$ 回勝つ確率を表しますから、上で話した簡単な考察ですぐに下記のことがわかります。問題が解けた暁には、下記が成り立っているかを確認することでその妥当性を判定できそうです。

$2^n$ さんは絶対優勝する。必ずちょうど $n$ 回勝つ。逆にちょうど $k$ 回( $0\leq k \leq n-1$ )勝つことはない。
$P_{2^n,n}=1$
$P_{2^n,k}=0$

1さんは必ず初戦敗退。逆にちょうど $k$ 回( $1 \leq k\leq n$ )勝つことはない。
$P_{1,0}=1$
$P_{1,k}=0$

2さんは初戦が1さんでなければ第1回戦勝てるが、第2回戦は必ず負ける。初戦の相手が1さんでなければ初戦敗退する。
(トーナメント表はランダムのため、例えば初戦の相手が1さんになる確率は、参加者から2さんを除いた $(2^n-1)$ 人のうち1さんだけということで、 $1/(2^n-1)$ となります。)
$P_{2,0}=(2^n-2)/(2^n-1)$
$P_{2,1}=1/(2^n-1)$

f:id:mattyuu:20161016085452j:plain
↑
具体的な例を見つつ、何が問われているかを確認しましょう。上図は $n=3$ の例になります。

このトーナメントではランキング2位の7さんが初戦敗退している上、ランキング5位の4さんが決勝戦に進んでいるなど、かなり理不尽なことが発生しております。このような理不尽なことがどれほど発生するのかということを、確率という道具を使って評価しよう、ということになります。

以上で問題設定を終わります。イメージは掴めましたでしょうか。

f:id:mattyuu:20161016085456j:plain
↑
「 $a$ さんがちょうど $b$ 回勝つ確率 $P_{a,b}$ を求めよ」と言われてもどこから手をつけてよいかわかりません。 $2^n$ 人が参加するトーナメント表は単純に考えると $2^n!(=2^n \cdot (2^n-1)\cdots3\cdot2\cdot1)$ 通りのパターンがあり、考えようとするだけでも頭がこんがらがりそうです。
今、 $a$ さんがちょうど $b$ 回勝つ確率を考えたいので、まずは $a$ さんだけに注目することで考察を始めるための入り口を模索していきたいと思います。

トーナメント表をランダムに組むと $a$ さんの最初の位置は様々です。しかし上図のように $a$ さんを隣の $z$ さんと入れ替えた2つのトーナメント表は本質的に同じものであるといえます。同様に $a$ さんと $z$ さんの2人分の組で構成されたトーナメントのブロックを隣のブロックと入れ替えてもトーナメント表は同じものであると言えるでしょう。トーナメント表は参加者が勝ち進んでいくと、どこを勝ち進んだ勝者と戦うことになるのかを示すものであり、ブロックの左右の入れ替えには影響を受けないため、このような操作をしてもトーナメント表の本質は変わりません。 $a$ さんができるだけ左に行くように各階層でブロックを入れ替えていくと、元のトーナメント表と本質的に同じトーナメント表で $a$ さんが一番左下に配置されているものを得ることが可能になります。つまり $a$ さんは始めからトーナメント表の一番左下に固定してよいということがわかります(数学的にはこのことを「 $a$ さんを左下に固定しても一般性を失わない」と表現します。)。

$a$ さんを一番左下に置くトーナメント表を考えることで何かいいことがあるでしょうか。まず最初に感じられるメリットは問題のサイズを落とすことができたということになります。元々 $2^n!$ 通りのトーナメント表の可能性がありましたが、 $a$ さんを左下に固定することで残りの $(2^n-1)$ 人の並べ替えである、 $(2^n-1)!$ 通りに問題のサイズを落とすことができました。つまり問題のサイズが $1/2^n$ になっています。例えば $n=5$ の場合を考えると $1/32$ の時間で結果を出すことができるわけで、これは数値シミュレーションを行う場合には大変都合の良いメリットになります。

一般性を失わないようにもっと場合の数を減らすことは可能でしょう(例えば第一回戦の対戦では左側に強さが小さい人が来るように配置する等)。ただこれ以上の一般化は数値シミュレーションをする上でメリットになっても、今回のように解析的に解を求めたい場合は必ずしもメリットになりません。場合分けが多く発生し、論理的に考える思考の妨げになるからです。実は今回の一般化は問題のサイズを落とす以上のメリットがあります。 $a$ さんを左下に持っていくことで、 $a$ さんが $b$ 回勝つための必要条件を簡単に考察することができるのです。

f:id:mattyuu:20161016085500j:plain
↑
本格的な考察に入る前に、今後の考察、記載を容易にするため、上図のようにトーナメント参加者にラベルをつけておきます。

f:id:mattyuu:20161016085508j:plain
↑
では $a$ さんが $b$ 回勝つための必要条件を求めましょう。 $a$ さんをトーナメントの左下に固定した威力が発揮されるときがきました。

必要条件というのは $a$ さんが $b$ 回勝つために最低限満たさなければいけない条件となります。つまり必要条件を満たしても $a$ さんがちょうど $b$ 回勝つとは限りません。 $(b+1)$ 回以上勝つ可能性もあるわけです。「 $a$ さんが $b$ 回勝つための必要条件」というのは「 $a$ さんが最低 $b$ 回勝つための必要十分条件」ということになります。なおしばらくの間、「 $a$ は1ではない」、かつ「 $b$ は0でない」として話を進めます。 $a=1$ または $b=0$ は、 $a$ さんが初戦敗退するという少し趣が異なる事象になるため、考察がしにくくなります。

まずは $a$ さんが1回勝つ必要条件(つまり初戦突破する条件)を求めましょう。数学では文字式を使った一般的な議論の前に具体的な数値でイメージをつかんで一般化するという手法が有効です。 $a$ さんが1回勝つためには初戦の相手である $X_1$ が $a$ さんよりも弱い(=「強さ」の小さい)1さんから $(a-1)$ さんであることが明らかに必要条件になります。つまり $a$ さんが1回勝つための必要条件は「 $X_1$ が1さんから $(a-1)$ さんのいずれかである。」ということになります。

次に $a$ さんが2回勝つ必要条件を求めましょう。 $X_1$ が $a$ さんよりも弱い参加者であることは明らかに必要ですが、 $a$ さんは第二回戦ですぐ隣のブロックの $X_2$ と $X_3$ の勝者と戦うわけですから、 $X_2$ 、 $X_3$ のいずれも $a$ さんよりも弱い1さんから $(a-1)$ さんのいずれかであることが必要条件になります。つまり $a$ さんが2回勝つための必要条件は「 $X_1$ 、 $X_2$ 、 $X_3$ が1さんから $(a-1)$ さんのいずれかである」ということになります。

同様に考察を行うと $a$ さんが $b$ 回勝つための必要条件は「 $X_1$ 〜 $X_{2^b-1}$ が1さんから $(a-1)$ さんのいずれかである」ということが分かるかと思います。

めでたしめでたしとしたいところですが、ここでもう一つ考えないといけない条件があります。例えば5さんは4回勝つことができるでしょうか。5さんが4回勝つためには $X_1$ 〜 $X_{2^5-1}(=X_{31})$ が1さんから4さんである必要があります。 $X_1$ から $X_{31}$ に重複なく1さんから4さんを割り振ることは不可能です。つまり $a$ さんが $b$ 回勝つためには $a>2^b-1$ も必要になるわけです。

例えば5さんがb回勝つためには
$5>2^b-1$
が満たされる必要がありますから、
$2^b<6$
となり、これを満たす $b$ は1、2のみとなります。つまり5さんはどれだけ頑張っても3回以上勝つことができないのです。

以上まとめるとaさんがb回勝つための必要条件は、
「 $a>2^b-1$ 」かつ「 $X_1$ 〜 $X_{2^b-1}$ が1さんから $(a-1)$ さんのいずれかである」
となります。

f:id:mattyuu:20161016085514j:plain
↑
最終的に求めたいものは $a$ さんがちょうど $b$ 回勝つ確率の $P_{a,b}$ ですが、その一歩手前として、 $a$ さんが最低 $b$ 回勝つ確率 $\tau_{a,b}$ を求めましょう。( $\tau$ という文字に特別の意味はなく、最初に私がノートで計算した際にたまたま用いた文字で、ここでもそのまま使わさせていただきます。)

前章で $a$ さんが $b$ 回勝つための必要条件、つまり $a$ さんが最低 $b$ 回勝つための必要十分条件が得られております。これを丁寧に確率の計算に当てはめてあげれば良いです。上図に記載した通り、確率の定義を思い出しておきましょう。

まず、求めたい確率の分母である全体の場合の数を求めます。今左下に $a$ さんを固定しているため、トーナメント表の組み合わせとして起こりうる全体の場合の数は、 $a$ さんを除く $(2^n-1)$ 人を一列に並べる並べ方の総数である $(2^n-1)!$ に等しくなります。一列に並べて左の人から順に $X_1$ 、 $X_2$ 、 $X_3$ 、、、 $X_{2^n-1}$ と割り振っていけばよいのです。

f:id:mattyuu:20161016085519j:plain
↑
次に確率の分子になる $a$ さんが最低 $b$ 回勝つトーナメントの総数を求めましょう。

まず、 $X_1$ から $X_{2^b-1}$ に $a$ さんより弱い1さんから $(a-1)$ さんまでを割り振る場合の数を求めます。これは $(a-1)$ 人の中から $(2^b-1)$ 人を選出し、選出された $(2^b-1)$ 人を一列に並べる場合の数の総数になります。 $(a-1)$ 人から $(2^b-1)$ 人を選出する組み合わせは ${}_{a-1}{\mathrm C}_{2^b-1}$ 通り、その各々に対して選出された $(2^b-1)$ 人を一列に並べる総数は $(2^b-1)!$ ですから、この場合の数は ${}_{a-1}{\mathrm C}_{2^b-1}\cdot(2^b-1)!$ となります。
そして、その各々に対し参加者の割り振られていない $X_{2^b}$ から $X_{2^n-1}$ へ $(2^b-1)$ 人に選出されなかった残りの $\{(2^n-1)-(2^b-1)\}$ 人、つまり $(2^n-2^b)$ 人を割り振ります。この並べ方は $a$ さんが最低 $b$ 回勝つという事柄に影響しませんので、単純に一列の並べ方の総数を出せばよく $(2^n-2^b)!$ となります。以上まとめると、 $a$ さんが最低 $b$ 回勝つトーナメントの総数は ${}_{a-1}{\mathrm C}_{2^b-1}\cdot (2^b-1)!\cdot(2^n-2^b)!$ となります。

f:id:mattyuu:20161016085524j:plain
↑
確率の分母、分子が求まりましたので、 $a$ さんが最低 $b$ 回勝つ確率 $\tau_{a,b}$ は上図の通りとなります。 ${}_n{\mathrm C}_r=n!/(n-r)!r!$ を使うことで、なんともシンプルで綺麗な表記になりました。

なお、最後の $\prod$ は $\pi$ の大文字であり、高校で習ったシグマ( $\sum$ )の掛け算版の記号として使われます。
つまり、
$\displaystyle \prod_{k=1}^na_k=a_1a_2\cdots a_n$
です。

$a<=2^b-1$ のときは、 $a$ さんは絶対に $b$ 回勝てないので、 $\tau_{a,b}=0$ となります。

今、 $a\neq 1$ で考察していました。 $a=1$ つまり、1さんは最弱のため1回も勝つことができません。つまり $b>0$ となる $b$ に対して、明らかに $\tau_{1,b}=0$ です。
そして $b>0$ なる $b$ に対して、 $a=1<=2^b-1$ ですから、今回求めた $\tau_{a,b}$ は $a=1$ に対しても成り立つことがわかります。

f:id:mattyuu:20161016085528j:plain
↑
さて、本題であった $a$ さんがちょうど $b$ 回勝つ確率 $P_{a,b}$ を求めましょう。ただし、ここでも $b\neq 0$ とします。 $b=0$ に対しては次章で求めたいと思います。

以前にも注意した通り、 $\tau_{a,b}$ は $a$ さんが最低 $b$ 回勝つ確率であり、ちょうど $b$ 回勝つ確率ではありません。しかし下記の考え方から、 $\tau_{a,b}$ から、簡単に $P_{a,b}$ を求めることができます。

トーナメントが一つ与えられたとき、 $a$ さんが初戦敗退するか、ちょうど1回勝つか、ちょうど2回勝つか、ちょうど3回勝つか、、、ちょうど $n$ 回勝つか(つまり、優勝するか)はどの2つの事象も同時に起こることはありません。「ちょうど3回勝つ」と「ちょうど4回勝つ」という事象は同時に起こらないのです。このことを確率の言葉で排反事象といいます。

「 $a$ さんが最低 $b$ 回勝つトーナメントの総数」は、「 $a$ さんがちょうど $b$ 回勝つトーナメントの総数」と「 $a$ さんがちょうど $(b+1)$ 回勝つトーナメントの総数」と「 $a$ さんがちょうど $(b+2)$ 回勝つトーナメントの総数」、、、「 $a$ さんがちょうど $n$ 回勝つトーナメントの総数」の和になります。

このことから(両辺をトーナメントの総数で割ることで)、「 $a$ さんが最低 $b$ 回勝つ確率」=「 $a$ さんがちょうど $b$ 回勝つ確率」+「 $a$ さんがちょうど $(b+1)$ 回勝つ確率」+「 $a$ さんがちょうど $(b+2)$ 回勝つトーナメントの確率」+・・・+「 $a$ さんがちょうど $n$ 回勝つ確率」となるのです。

今求めたいものは「 $a$ さんがちょうど $b$ 回勝つ確率」 $P_{a,b}$ ですが、今具体的に求まっている $\tau_{a,b}$ には、上図の通り邪魔な確率「 $a$ さんが $(b+1)$ 回以上勝つ確率」が含まれてしまっております。しかし、「 $a$ さんが $(b+1)$ 回以上勝つ確率」= $\tau_{a,b+1}$ ですので、 $\tau_{a,b}$ から邪魔な確率 $\tau_{a,b+1}$ を引いたものが、 $P_{a,b}$ になるのです。

f:id:mattyuu:20161016122736j:plain
↑
これまでは $b\neq 0$ を考えておりました。最後に $b=0$ つまり、 $a$ さんが初戦敗退する確率を求めましょう。これまでの議論に比べればとても簡単なものになります。

上図では少し丁寧に確率を求めましたが、 $a$ さんが初戦敗退する必要十分条件は、「初戦の対戦相手の $X_1$ が $a$ さんより強い」になります。 $a$ さんの初戦の相手となり得る参加者の総数は、 $2^n$ 人の参加者から $a$ さんを除いた $2^n-1$ です。そのうち $a$ さんより強い人は $(2^n-a)$ 人おりますし、初戦の相手が誰になるかは $a$ さんを除く参加者全てに対して同様に確からしいため、 $a$ さんが初戦敗退する確率は、
$\displaystyle P_{a,0}=\frac{2^n-a}{2^n-1}$
になります。

f:id:mattyuu:20161016085537j:plain
↑
以上の議論をまとめると、最終的な解析解は上図の通りになります。誰かが注文したわけではないのに、このような綺麗な形になるところに数学の美しさを感じてしまします。

$a$ 、 $b$ に具体的な値を入れて計算すると、とてもよくできた数式だと感心します。例えば、1さんが必ず初戦敗退することや、 $2^n$ さんが必ず優勝するということを上記の式から計算して確認してみてください。一体この数式は誰が考え、生み出したのでしょうか。とても神秘的な気持ちになります。

今回の所感として、問題が解けたことに驚きを感じています。この世の中には未だ解けない難問が数多く存在します。一見簡単そうな問題でも、解けていないものが多くあります。今回の問題もたまたま解くことができましたが、解けるという保証はありませんでした。簡単に解ける問題、解けない問題の違いは何か、なぜ今回解けたのか、考えるのも怖いくらい難しい問題な気がします。

今回得られた解析解からどんな面白いことがわかるかという考察はしておりません。それはまた機会があれば考察したいと思います。例えば「一回戦敗けの人の言い訳はどれだけ信用してもよいか？」や「 $n\rightarrow \infty$ にして、 $x=b/n$ を $[0,1]$ 区間の連続変数と考えた時の $P_a(x)$ の分布はどうなるか?」等々。後者の分布を出せば、福原さんが日曜数学会で発表されていた、「2位の人は運ゲーである」ということについても目に見える形でわかるのではないかと思います。

f:id:mattyuu:20161016132135j:plain

mattyuuの数学ネタ集

世界は数式で溢れている

トーナメントは運か実力か(解析解編)