問題
25頭の馬がいる。
これからレースを行い、足が速い馬トップ3頭を見つけたい。
ただし1回のレースで走れる馬は5頭まで。
また、レースのタイムは計測できないため、「Aの馬はBより速い」といった相対的な速さしか分からない。
さて、最速の3頭を見つけるために必要な最小のレース回数は？
さあ、解いてみよう！
ヒントはなし。
少し下にスクロールすると答えがあります。
正解
7回
解説
最初の段階
まず、25頭の馬を5グループに分けます。
そのグループ内で1回ずつレースを行います。
すると、5グループ内における1位〜5位の馬が分かります。
グループ名を仮にA,B,C,D,Eとすると以下の通り。
※「A1」は「Aグループ内の1位」を表す
- A1, A2, A3, A4, A5
- B1, B2, B3, B4, B5
- C1, C2, C3, C4, C5
- D1, D2, D3, D4, D5
- E1, E2, E3, E4, E5
この時点で、各グループの4位および5位は「25頭の中でトップ3頭」にはなれないので候補から外れます。
レースが5回行われた段階で、残った馬は以下の15頭。
- A1, A2, A3
- B1, B2, B3
- C1, C2, C3
- D1, D2, D3
- E1, E2, E3
ちょっと注意
ここからが少し厄介です。
一見、1位の馬だけでレースを行って上位3頭を選べばいいように思えます。
しかしグループ間の順位差がはっきりしていないため、その場合に選んだ3頭は全25頭の中でのトップ3頭にはならない可能性があります。
たとえば、Aグループに全頭最速の3頭が固まっている場合。
このとき「全体で最速の3頭」はA1, A2, A3です。
A〜Eの1位のみでレースを行うと、A2とA3が実は全頭の2位3位という事実に気づけません。
このままでは不十分です。
かといって、いちいち「1位同士でレース」「2位同士でレース」「3位同士でレース」などとやっていたら必要なレース数がムダに増えていくだけ。
何か、もっといい方法はないのでしょうか？
ちょっとしたテクニック
冴えたやり方があります。
6レース目はとりあえず、各グループ1位の馬5頭による競争を行います。
順位が
1位：A1
2位：B1
3位：C1
4位：D1
5位：E1
になったと仮定します。
このとき、少なくともD1とE1は「全体のトップ3」には入れないことが確定します。
と同時に、D1,E1より遅いD,Eグループの2位3位も「全体のトップ3」には入れないことが判明します。
残った候補は以下の9頭。
- A1, A2, A3
- B1, B2, B3
- C1, C2, C3
もう少し考えてみる
さて、6レース目の結果の一部をもう一度見てみましょう。
1位：A1
2位：B1
3位：C1
よく考えたら、C2とC3は「全体でトップ3頭」には入れません。
C1より速い馬が現時点で2頭もいるからです。
同様に、B3にもチャンスはありません。
以上を考えると、6レース終了時点で残る候補は以下の6頭。
- A1, A2, A3
- B1, B2
- C1
最後のレース
A1は、B1とC1に勝っています。
つまりA1は全25頭で最速の馬です。
なので最後の7レース目では、A1を除く5頭での競争になります。
A1、および最終レースの1位2位が「全25頭で最も速いトップ3の馬」です。
参考
Answer to Puzzle #59: 25 Horses, Find the Fastest 3
