MathLabs

第5問

整数 N≥2N \ge 2 が与えられている。互いに身長が異なる N(N+1)N(N+1) 人のサッカー選手が一列に並んでいる。サー・アレックスは、この列から N(N−1)N(N-1) 人を取り除き、残った 2N2N 人からなる新しい列において、次の NN 個の条件がすべて成り立つようにしたい。最も背の高い二人の間には誰もいない、背が3番目と4番目に高い二人の間には誰もいない、…\ldots、最も背の低い二人の間には誰もいない。これが常に可能であることを示せ。
ステップ 1/7: 問題を NN に関する帰納法に帰着する
前のステップ次のステップ
ざっくり言うと

選手を取り除く操作は単調であるから、自然な戦略は一度に一組の隣接した対を切り離し、まったく同じ問題のより小さな版に対して帰納を進めることである。

N(N+1)=2N+N(N−1)N(N+1)=2N+N(N-1)
詳しい解説

NN に関する強い帰納法によって、すべての整数 N≥1N\ge 1 について次を示す：互いに身長の異なる N(N+1)N(N+1) 人の選手からなる列は、常に N(N−1)N(N-1) 人を取り除くことで 2N2N 人の生存者を残すことができ、その連続する身長順位の組 (2k−1,2k)(2k-1,2k)（k=1,…,Nk=1,\ldots,N）はいずれも得られた列の中で物理的に隣接する。問題が要求する範囲 N≥2N\ge 2 はこの特別な場合として含まれる。基本ケース N=1N=1 では誰も取り除く必要がなく、選手はわずか 22 人しかいないので、唯一必要な組は自明に隣接している。