MathLabs

第5题

给定整数 N≥2N \ge 2。有 N(N+1)N(N+1) 名身高互不相同的足球运动员站成一排。亚历克斯爵士想从这一排中去掉 N(N−1)N(N-1) 名运动员，使剩下的 2N2N 名运动员组成的新一排满足以下 NN 个条件：两个最高的运动员之间没有任何人，第三高与第四高的运动员之间没有任何人，…\ldots，两个最矮的运动员之间没有任何人。证明这总是可以做到的。
第 7/7 步：组合各对并得出结论
上一步下一步
P(1) ∧ (P(N−1)⇒P(N)) ⟹ P(N)  ∀N≥1P(1)\ \wedge\ \big(P(N-1)\Rightarrow P(N)\big)\ \Longrightarrow\ P(N)\ \ \forall N\ge 1
详细分析

对 xq,xpx_q,x_p 与由归纳假设得到的 N−1N-1 对合在一起，共给出 NN 对。由于 GkG_k 比排在它之后的其余 N−1N-1 个区块中的任何一个都矮，又比排在它之前的都高，并且子行自身的区块沿袭了同样的从左到右的身高顺序，所以这 NN 对恰好占据最终由 2N2N 名幸存者组成的一排中连续的身高名次 (1,2),(3,4),…,(2N−1,2N)(1,2),(3,4),\ldots,(2N-1,2N)，并且按构造每一对都物理相邻。至此归纳步骤完成，故命题对每个 N≥1N\ge 1 都成立，特别地，对题目所要求的每个 N≥2N\ge 2 也成立。