パズルの国のアリス

いつまで続く? 巴戦(解答)

 ウォーミングアップの最初の問題は,いろいろな本で取り扱われているし,これを少し改変した問題が近年の東大入試に出たこともあって,ご存じの読者も多いことだろう。場合分けをきちんとして,システマチックに考えていけば高校数学の範囲で正解にたどり着ける。

 最初の対戦の勝者をA,敗者をB,最初の対戦で待機していた人をCとし,それぞれがチャンピオンになる確率をabcとしよう。次の対戦はA対Cとなるが,Aはこの対戦に勝てば(確率1/2) チャンピオンになる。負けても,次にBがCに勝ちそのBに再び勝つことで(確率1/8)またチャンスが訪れる。よってa=1/2+a/8という方程式が成り立つから,a=4/7である。一方Bがチャンピオンになるためには,次の対戦でCがAに勝ちそのCに勝つしかなく(確率1/4),その時点でAの立場(つまり,最初の対戦の勝者と同じ立場)になれるのだから,その確率はba/4=1/7だ。またCがチャンピオンになるためには,次の対戦でAに勝つ必要があるが(確率1/2),その時点でAの立場になるから,その確率はca/2=2/7だ。

 aから順次求める以外の方法もある。例えばAは次の対戦でCに勝つとチャンピオンになるが,負けるとBの立場になる。次の対戦でCが勝つとBはCの立場になり,CはAの立場になることを考えると,

 

a=(1+b)/2,bc/2,ca/2

という連立方程式が立つので,これを解いてもa=4/7,b=1/7,c=2/7が得られる。

 最初に対戦する2人がA,Bのどちらになるかは半々なので,結局,その2人がチャンピオンになる確率はどちらも(4/7+1/7)/2=5/14で,待機していたCがチャンピオンになる確率2/7=4/14よりわずかに高い。

 ウォーミングアップの次の問題,チャンピオンが決まるまでの延べ対戦回数の期待値は,確率よりもずっと易しい。3人の場合は,次の対戦,A対CでAが勝てばチャンピオンが決まるし,Cが勝ってもA,B,Cの立場が入れ替わるだけで状況は変わらないことを考えると,これから先の何戦目くらいでチャンピオンが決まるかという数値をrとすればr=1+r/2が成り立つから,r=2が求まる。結局,これに最初にA,B,Cが決まるまでの1戦を加えて対戦回数の期待値は3だ。

 ところが人数が増えると,途端に状況は複雑怪奇となる。しかし,4人くらいまでなら,方程式アプローチがなんとか現実に取り扱える範囲なのでやってみよう。最初の対戦の勝者をA,敗者をB,待機者をC,Dとする。こののちチャンピオンが決まるまでの対戦回数の期待値をr(1,0,0)としよう。(1,0,0)は対戦権を持つ人が3人いて,それぞれが1人,0人,0人を支配している状況を表している。次の対戦の組み合わせはA対C,A対D,C対Dの3通りがあり,その勝者が誰かでさらに分類すると全部で6通りがあるが,その結果を整理すると次のような方程式が立つことを読者は確認されたい。

r(1,0,0)=1+r(2,0)/3+r(1,0,0)/3+r(1,1)/3

 

ここで(2,0)は,対戦権を持つ人が2人いてそのうちの1人が他の2人を支配している状況を表し,r(2,0)はそれから先の何戦目くらいでチャンピオンが決まるかの期待値だ。r(1,1)も同様である。また,さらに次の方程式が成り立つことも納得していただけるだろう。

r(1,1)=1+r(2,0),r(2,0)=1+r(1,0,0)/2

 

これらをすべて連立させて解くことでr(1,1)=5,r(2,0)=4,r(1,0,0)=6が得られる。

 結局,4人の場合はチャンピオンが決まるまでに平均でr(0,0,0,0)=1+r(1, 0,0)=7回くらいの対戦が必要ということになる。

 ポーンたち8人の場合も,方程式アプローチが不可能というわけではないが,未知数や連立させる方程式の数が多すぎて現実的ではない。そこで別の方法ということになるが,ここは帰納的に予想を立てるのがよさそうだ。2人の場合,明らかに1回でチャンピオンが決まる。1,3,7と来れば,次は15,その次は31になりそうだ。つまりn人の場合,平均2n-1ー1回くらいの対戦でチャンピオンが決まるという予想が立つ。n=8なら27-1=127回くらいだから,アリスの懸念は当たっているともいないとも言えそうだ。

 実は,この予想は正しいのだが,それをどうやって証明すればよいだろうか。そのための巧妙な手法は次のようなものだ。まず対戦権を持つ人が支配している人数をkとすると,その人に支配力として2k-1という数を割り当てる。そして対戦権を持つ人全員の合計を考える。対戦権はあるがだれも支配していない人の支配力は20-1=0なのがミソだ。つまり,最初の段階でのこの支配力合計は0である。

 今,くじ引きによりk人を支配する人Kとl人を支配する人Lとが対戦することになったとしよう。その勝敗結果によって支配力合計は変化する。この2人の支配力合計はこの時点では2k+2l-2だが,Kが勝てば2k+1-1に,Lが勝てば2l+1-1に変化する。どちらが勝つ確率も1/2なのだから,対戦後の2人の支配力合計の期待値は2k+2l-1となり,支配力合計は1増えることが期待される。

 これは,どの2人の対戦であっても同じだから,1回の対戦ごとに支配力合計は1ずつ増えると期待される。一方,チャンピオンが決定したということは,その支配下に他のn-1人全員が入ったということだから,支配力合計は2n-1-1。よって,支配力合計0の状態からその状況に至るには,平均で2n-1-1の対戦が必要になる。

 この支配力合計という指標は極めて強力だ。例えば,8人の場合で,途中Aが4人,Bが2人を支配下に置いたとき,あと何回くらいの対戦でチャンピオンが決まるかというようなことも,27-1-(24-1)-(22-1)=109と簡単に計算できる。

問題はこちらです