TAX de PAZZLE、2022年1月号の解答です。
代表候補25人のランナーから足の速い上位から代表3人を選出したい。競技トラックの関係上、１レースでは同時に5人しか走ることができず、また、あろうことか、タイムを計るストップウォッチが壊れてしまった。
代表候補は、何本走ってもタイムが落ちることがなく自己ベストタイムを常に出せるとした場合、何レースをすれば代表3人を確実に確定させることができるだろうか。
この問題のポイントは、終盤のレースの参加者をどのように組むか、です。
まずは25人の走力を一度は確認しないと順位付けしようがないので、5人ずつ5レースを行います。便宜上、最初のレースの参加者を着順でA1、A2、A3、A4、A5とし、2レース目も同様にB1、B2・・、というルールで、E5まで記号であらわすこととします。
1つのレースに走力が高い人が集まっている可能性があるので、各レース3着までは、全体の3位以内の可能性があります。逆に言えば、各レース4位以下の人はこの時点で代表には選ばれません。
次に6レース目ですが、各レースで1位になった走者5人で競います。たとえばその着順がA1、B1、C1、D1、E1だとすると、D1、E1は4位以下なので代表から外れます。そうすると自ずとD2,D3,E2,E3も外れます。さらに、C1が3位ということはC2,C3も外れ、同様の考えでB3も全体の3位以上ではありえないので外れます。
この時点での代表候補は、A1,A2,A3,B1,B2,C1の6人。ただし、A1は、各レースの1位同士のレースで1位を取っていることから、代表候補全体での1位であることが確定するので、代表確定です。
そして、7レース目、A2,A3,B1,B2,C1の5人でレースを行い、その上位2名が、代表候補全体の2位、3位であることが確定します。
というわけで、代表確定までに必要なレース数は７レースでした！