8人の選手を強い順に並べる方法は？

日本語翻訳版のカバーイメージが見つからなかったので原書のカバーです。カバーは人物イラストを使った翻訳版のほうが楽しげで、雰囲気的に内容とマッチしています。原書で読んだわけではありません。
きょう紹介する本は、デニス・シャシャ著『ドクター・エッコ――奇妙なパズルの依頼人たち』（久慈要・湯浅太一訳、日経サイエンス社、1990年）。コンピュータ科学者による歯ごたえ満点の数理系パズル本です。

よろず難問請負人を標榜する天才数学者エッコが、さまざまな依頼者――政治家、ビジネスマン、弁護士、エンジニア、軍人、大富豪等々――が持ち込むさまざまな難問を解き、それを友人が記録するという体裁で書かれています。いわばパズル版シャーロック･ホームズ物語。全38問はどれもよくできていて、パズルやクイズが好きな人にはこたえられない1冊です。

それでは1問お楽しみください。

依頼人はオリンピック･テニスチームの監督。依頼内容は、出場予定の選手たちが飛行機事故で負傷し、急遽、補欠8人を起用することになったので、今日中に8人をランクづけする方法を考えてほしい、というものでした。条件は以下です。

・選手は8人
・使用できるコートは1面
・1試合にかかる時間は1時間
・選手Xが選手Yに勝ち、選手Yが選手Zに勝つなら、選手Xは選手Zに勝つと考えてよい
・選手は十分に体力があり、試合が連続しても大丈夫

■問題
①エッコは、各試合の結果に関係なく、17時間で8人をランク付けできる方法を見つけました。その方法とは？

②コートが4面使えることになりました。エッコは、それなら6時間で決められると言いました。その方法とは？

③さらに1時間短縮して、5時間でランキングすることはできるでしょうか？

■解答（考え方）
①めざすゴールが「17時間」とはっきりしているので自分で解いてみてください。ちなみに、私は解けませんでした。解答を読んで、なんとか理解できました。
ヒント追加：まず4人ずつ2組にわけて、その4人のなかで1位から4位までを決めます。

②考え方だけ紹介します。コートをA、B、C、Dとし、8人を4組に分けて試合をさせます（1時間目）。その試合の勝敗によって、2時間目にどのコートに入るか（誰と対戦するか）を決めていきます。勝敗のパターンによっては、休みをはさむ選手も出てきます（3時間目と5時間目はコート2面、6時間目はコート3面を使用します）。とても説明できません……。私は解答を読んで（解答図を見て）、なんとか理解できました。

③未解決の問題である。ということだそうです。

■ちなみに……
問題①を解くのに使われるアルゴリズムはマージ・ソートというもので、考案者は不明ですが、計算機の生みの親ジョン・フォン・ノイマンはこの方法を知っていたそうです。問題②を解くのに使われるアルゴリズムはK.E.バッチャーが考案したバッチャ－・ソートというそうです。

●ご用とお急ぎでない方は下のアイコンに応援のワンクリックをお願いします。