第5問

整数

N \ge 2

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

N(N+1)

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

N(N-1)

人を取り除き、残った

2N

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

N

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

\ldots

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

ステップ 7/7: 対を組み合わせて結論づける

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

P(1)\ \wedge\ \big(P(N-1)\Rightarrow P(N)\big)\ \Longrightarrow\ P(N)\ \ \forall N\ge 1

詳しい解説

対 $x_q,x_p$ と、帰納法の仮定から得られた $N-1$ 組の対とを合わせて、合計 $N$ 組の対が得られる。 $G_k$ は、それより後にある残り $N-1$ 個のブロックのどれよりも背が低く、それより前にあるものより背が高いので、また部分列自身のブロックが同じ左右の身長順序を受け継いでいるので、これら $N$ 組の対はちょうど連続する身長順位 $(1,2),(3,4),\ldots,(2N-1,2N)$ を、 $2N$ 人の生存者からなる最終的な列の中で占め、構成により各対は物理的に隣接している。これで帰納法の段階が完了し、主張はすべての $N\ge 1$ について成り立ち、特に問題が要求するすべての $N\ge 2$ についても成り立つ。