MathLabs

第5题

给定整数 N≥2N \ge 2。有 N(N+1)N(N+1) 名身高互不相同的足球运动员站成一排。亚历克斯爵士想从这一排中去掉 N(N−1)N(N-1) 名运动员，使剩下的 2N2N 名运动员组成的新一排满足以下 NN 个条件：两个最高的运动员之间没有任何人，第三高与第四高的运动员之间没有任何人，…\ldots，两个最矮的运动员之间没有任何人。证明这总是可以做到的。
第 6/7 步：对参数为 N−1N-1 的更小实例递归
上一步下一步
(N−1)N=(N−1)((N−1)+1)(N-1)N=(N-1)\big((N-1)+1\big)
详细分析

被削减后的候选池仍是一排身高互不相同的运动员，保持原来从左到右的顺序，按身高分成 N−1N-1 个连续的区块，每块恰好有 NN 人——这正是参数为 N−1N-1 时所要求的形状，因为 (N−1)N=(N−1)((N−1)+1)(N-1)N=(N-1)\big((N-1)+1\big)。于是归纳假设可以应用到这个子行上，产生 2(N−1)2(N-1) 名新的幸存者，从 N−1N-1 个区块中各恰好取出 22 人，组成 N−1N-1 对，每一对在子行内都物理相邻，并占据其中连续的身高名次。