数学オリンピック 2018 日本予選 10

今回の記事はこちらの問題、予選の第10問です。

23=8人の選手が勝ち抜きトーナメントのチェス大会に参加した。この大会では、次のようにして優勝者が決定される:

  • 最初に、選手全員を横一列に並べる。
  • 次に、以下の操作を3回繰り返す:「列の中の選手を、端から順に2人ずつ組にし、各組の選手どうしで試合を行う。勝った選手は列に残り、負けた選手は列から脱落する。ただし、引き分けは発生しないものとする。」
  • 最後に列に残った選手を優勝者とする。

大会の前に総当たりの練習試合が行われ、その際引き分けが発生しなかった。すなわち、任意の2人組について、その2人の選手による練習試合が行われ、勝敗が決した。
いま、大会中の勝敗が練習試合と一致すると仮定したとき、はじめの選手の並べ方によっては優勝する可能性のある選手はちょうど2人であった。練習試合の勝敗の組み合わせとしてありうるものは何通りあるか。

かなり根気のいりそうな問題ですが、比較的やりやすいと思います。


まずは優勝する可能性のある選手においてありうる勝敗を考えましょう。
この2人も練習試合で勝敗が決していますから、勝った側をA、負けた側をBとおきます。
まずはAの勝敗数を考えましょう。
Aは他の6人全員にも勝っている場合、はじめにどのように並べられてもAは3試合を勝ちますからA以外に優勝する可能性がある選手はいなくなります。
また、Aが2人以上に負けている場合、列の先頭にA、2番目にB、3番目と4番目にAに勝った相手、と並べられてしまいますとまずAとBの対戦でBが負けます。その次はどちらが相手でもAが負けてしまい、新たに優勝の可能性がある選手が出てしまいます。
すなわち、Aは6勝1敗であり、Bに勝っている、ということが決定されます。

そこで新たにAに勝った選手としてCとおきましょう。
すると最初にAとCが対戦する場合Aがここで負けますからBが優勝しなければならなくなります。
ということは、こうなった場合はBは残った誰が相手でも勝ち上がる、ということになります。
(2回戦でCと戦う場合もありえますのでCにも勝ったことがわかります)

さらにCの勝敗を考えると、A以外に勝った相手がいたとすると1回戦でAとBが対戦しCとCが勝った相手が対戦するとCが勝ち、次にAとCの直接対決でCが勝ってしまいます。するとAB以外に優勝者が出てしまい、設定がおかしくなります。

ということで、ここまでで以下のことが分かりました。
・優勝する可能性のある2人で直接対決で勝った側をA、負けた側をBとすると、AとBは6勝1敗
・Aに勝った選手をCとおくと、Cは1勝6敗

これで大丈夫かどうかを検証しましょう。
・1回戦でAとCが直接対決:1回戦でAは負けてしまいますが残りの選手にBは負けませんのでBが優勝
・1回戦でAとCは直接対決しない:1回戦でCが負けてしまいますのでAが優勝

となり、これですべての条件がそろったことがわかりました。
あとはその場合の数を計算するだけです。
「Aはだれか」「Bはだれか」「Cはだれか」「残り5人の総当たり(10試合)の結果」の場合を乗算すると求められます。
ということで8・7・6・210 = 344064通りとなります。

スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする

スポンサーリンク