MathLabs

第5問

整数 N≥2N \ge 2 が与えられている。互いに身長が異なる N(N+1)N(N+1) 人のサッカー選手が一列に並んでいる。サー・アレックスは、この列から N(N−1)N(N-1) 人を取り除き、残った 2N2N 人からなる新しい列において、次の NN 個の条件がすべて成り立つようにしたい。最も背の高い二人の間には誰もいない、背が3番目と4番目に高い二人の間には誰もいない、…\ldots、最も背の低い二人の間には誰もいない。これが常に可能であることを示せ。
ステップ 2/7: 列を身長ブロックに分割する
G1<G2<⋯<GN,∣Gj∣=N+1G_1<G_2<\cdots<G_N,\qquad |G_j|=N+1
詳しい解説

選手たちを位置の順に x1,…,xN(N+1)x_1,\ldots,x_{N(N+1)} と並べ、それぞれに全体での身長順位を与える。身長だけに基づいて、彼らを NN 個の連続したブロック G1,…,GNG_1,\ldots,G_N に分割し、各ブロックの大きさは N+1N+1 とする。こうすると GjG_j のどの成員も Gj+1G_{j+1} のどの成員より背が低くなる。最終的な 2N2N 人の生存者が各ブロックからちょうど 22 人ずつを含むなら、それらの対は自動的にブロックの順序どおり、必要な連続する身長順位 (2j−1,2j)(2j-1,2j) を占める。