トーナメントで対戦する確率

質問

2^nのチームがトーナメント形式で対戦をします。
・各チームには力の差がない（じゃんけん大会としてもよいかも？）
・トーナメントの形状は、綺麗な対称形（どのチームもｎ回連続で勝てば優勝できる、といえば形状が特定できると思います）
このとき、特定の２チームAとBが対戦する確率を求めよ。

という問題で、私の回答は、
・Aの位置を一番左としても一般性を失わない
・ともにk回(k=0,1,...,n-1)勝てば対戦できるような位置にBが入る入り方は2^k通り（A以外の2^n-1個所の場所の選び方は同様に確からしいと考えて）
という考えのもと、

Σ(k=0～n-1) 2^k/(2^n-1) * (1/4)^k = 1/(2^n-1) * {1-(1/2)^n}/{1-(1/2)} = 1/2^(n-1)

となると考えましたが、この考えであってますか？

この問題、某かの本に載っていた問題なのですが、解答がどうも違うことを書いていたらしいのです。。。（他人から教えて貰った問題なので、どの本なのかはわかりませんし、記述されていた解答もちゃんと覚えてないので、質問として完全ではないのですが・・・）

確率の話は、「何が同様に確からしいか」を明確にしないと、自分の考えた解答が間違っている可能性があって、ちといやらしいです。（半径１の円に任意に弦を引いたときにその長さが１以上になる確率を求める問題とか^^;ちなみに私はルベーグ積分とか、測度とかは知りません。）

回答No.4

noname#5277

久々に思いついたので投稿しようと思いました。

まず、トーナメント戦なので全試合数は
　　2^n - 1
試合あります。これはすべて異なるチームの組み合わせです。

ここで、可能な２チームの組み合わせは、
　　(2^n)C(2) = 2^(n-1) * (2^n -1 )
となります。

したがって、任意の２チームが対戦する確率は、
可能なチームの組み合わせの総数のうちの
実際に対戦が実現する組み合わせの数になりますので、
　　　{2^n - 1}/{2^(n-1) * (2^n -1 )}
= 1/2^(n-1)
となります。

いかがでしょうか？

回答No.3

noname#5277

NO1のもので、No2の方とにた回答ですが、
2~(n+1)のとき、
準決勝までに当たる確率はP(n)×(2^n-1)/(2^(n+1)-1)であり、
決勝で当たるのは(1/2)^n×(1/2)^n×2^n/(2^(n+1)-1)となりますので、
あとは漸化式を解けば出ると思います。

通学中の車の中で考えたので、
計算していませんが・・・

回答No.2

noname#5179

帰納法的な考え方もあるかと思います。

2^Kチームの場合の確率がPとすると、

2^（k＋1）チームの時、
その2^kの時のトーナメント表の一番下のチームを2つに分割、（先ほどの一番下のチームの所が2回戦となるようにします。）
すると、先ほどより一度勝ち抜かないとだめなのでP/4の確率となります。

さらに、この2つに分割したところに、AとBの両方のチームが入ることも考えられます。つまり1回戦で対戦する場合が、4/Pの中に含まれていません。
この確率を計算して4/Pと足したのか確率。

後は帰納法的に求める、という方法はいかがでしょうか。

具体的に計算していないので、本当にただしいかどうかは不明ですが。

補足

たぶんですが、P/4には「１回戦で対戦しない（ような割り振りとなる）確率」(1 - 1/{2^(n+1)-1})を乗じないといけないと思うのですが・・・
ちなみに、Pと書いているのも、P(k)と書くべきですか？

P(n+1) = (1 - 1/{2^(n+1)-1}) * 1/4 * P(n) + 1/{2^(n+1)-1}, P(1)=1

これを解くと、P(n)=1/2^(n-1) となりそうです。（答えを類推しての帰納法ですが^^;）

回答No.1

noname#5277

合っていると思いますよ。
あえて付け足せば、勝つ確率は誰も１／２であるという前提が必要ですが。

お礼

ありがとうございます。とりあえず、ホッとしてます。(笑)
勝つ確率が誰も1/2というのは、「力の差はない」で大丈夫かと思います。

to ここをごらんになられた皆様
質問の趣旨が、自分の解答の確認のほかに「他の解釈方法がありえるのか」というところにあったりしますので、「こんな解釈のもとに、こんなとき方ができる（結果、質問に書いたのと違う答えとなる）」というのがあれば、どしどしお寄せください。