パズルの国のアリス

いつまで続く? 巴戦(問題)

坂井 公(筑波大学) 題字・イラスト:斉藤重之

 春は物言う花たちも満開で,鏡の国の花園はさぞかし美しいだろうと思ってアリスが散歩にやって来た。確かにスミレやポピーがそこかしこで咲き乱れているのだが,花たちの会話や独り言でかしましいことこの上ない。アリスはたちまちうんざりしたが,わざわざ来た手前,挨拶しただけですぐに立ち去るのも角が立ちそうと悩んでいると,少し遠くで赤のポーンたちが手招きしている。

 これ幸いとポーンたちのほうへ行くと,こちらはカルタ取り勝負の最中らしい。1人が言う。「あんなおしゃべりの花たちと付き合っていたら日が暮れちゃうよ。それより俺たちの勝負の立会人になって,どちらが早いかとかお手付きがないかとか,判定してくれないか? 今,競技カルタ風の1対1勝負でチャンピオンを決めようとしてるんだ」。

 「8人いるから,トーナメント方式でやれば公平というわけですね」とアリス。「いや,それだと,チャンピオンになったとしても,対戦してない相手がいるだろ。それぞれに苦手の相手がいるかもしれないし,全員に勝つまではチャンピオンになれないようにしようと思うんだ。そこで,次のようなルールを考えた」。

(1)最初は全員に対戦権がある。
(2)各回で対戦する2人は対戦権を 持つ人の中からくじ引きで決める。
(3)各対戦の敗者は,勝者の支配下に入り対戦権がなくなる。
(4)支配者が負けると,その支配下全員の対戦権が復活する。
(5)対戦を繰り返し,1人が他の全員を支配下に入れたとき,その支配者がチャンピオンになる。

 「なるほど,自分の支配下に入れるには,直接対決して勝たないといけないから,チャンピオンになった場合は,他の全員に勝っているはずというわけね」とアリス。「日本の相撲の優勝者決定方式に巴戦というのがあるだろ。あれを応用したというわけさ」。

 「え,何,日本のスモモ?」とアリスは思ったが,ここは知ったかぶりをして「あらそう,うまく考えたわね。でも,それで公平なのかしら。それに,各勝敗は時の運といえるのかもしれないけど,『三すくみ』が生じていれば,いつまでもチャンピオンが決まらないということになるわ」。

 「まさか。多少の苦手はあっても,完全な三すくみというのはないさ。ま,チャンピオンが決まるまで,多少,時間がかかるかもしれないけど」という言葉に,アリスは「花たちのおしゃべりに付き合っていた方がまだましだったかも」と心配になる。

 さて,読者にはこのアリスの懸念について考えてもらいたい。まず,ウォーミングアップとして,3人での巴戦の場合を考えてもらおう。対戦する2人はくじ引きで選ばれるから,実際上の問題はないのだが,3人巴戦の場合は,最初に対戦する2人と残った1人では微妙に公平性に差があることが知られている。3人の実力が伯仲していてどの対戦でも勝率が半々だとしたら,それぞれがチャンピオンになる確率はどうなるだろうか? また,この場合,チャンピオンが決まるまでに,延べ何回の対戦が必要だろうか,その期待値を求めてほしい。

 最後に,これが本題だが,8人のポーンでこの勝負をやった場合,チャンピオンが決まるまでに何回くらいの対戦が必要だろうか? もちろん,完全な三すくみがあればチャンピオンは永久に決まらないし,極端に強い人がいれば最短7回で決まってしまうこともあるわけだが,これも各対戦の勝率は半々という仮定で考えていただきたい。

答えは6月17日に

解答はこちらです