MathLabs

第5题

给定整数 N≥2N \ge 2。有 N(N+1)N(N+1) 名身高互不相同的足球运动员站成一排。亚历克斯爵士想从这一排中去掉 N(N−1)N(N-1) 名运动员，使剩下的 2N2N 名运动员组成的新一排满足以下 NN 个条件：两个最高的运动员之间没有任何人，第三高与第四高的运动员之间没有任何人，…\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 名运动员，所以唯一需要的一对显然相邻。