第5問

整数

N \ge 2

が与えられている。互いに身長が異なる

N(N+1)

人のサッカー選手が一列に並んでいる。サー・アレックスは、この列から

N(N-1)

人を取り除き、残った

2N

人からなる新しい列において、次の

N

個の条件がすべて成り立つようにしたい。最も背の高い二人の間には誰もいない、背が3番目と4番目に高い二人の間には誰もいない、

\ldots

、最も背の低い二人の間には誰もいない。これが常に可能であることを示せ。

ステップ 3/7: 最初の繰り返しブロックは早い段階で現れる

前のステップ次のステップ

N+1>N\implies \exists\, q<p\le N+1:\ x_q,x_p\in G_k

詳しい解説

行を左から右へ、位置ごとに走査し、 $x_p$ を含むブロックがすでに以前の選手 $x_q$ （ $q<p$ ）を含んでいる最初の添字 $p$ で止める。この繰り返されたブロックを $G_k$ と呼ぶ。ブロックはわずか $N$ 個しかないので、そのような繰り返しは最初の $N+1$ 個の位置の中で必ず起こる。すなわち鳩の巣原理により、走査した $N+1$ 人の選手がすべて異なるブロックに属することはできない。 $p$ の最小性により、 $G_k$ 以外のどのブロックも初めの区間 $x_1,\ldots,x_p$ に高々 $1$ 人しか寄与できず、一方 $G_k$ はそこにちょうど $2$ 人、すなわち $x_q$ と $x_p$ を寄与する。