第5题

给定整数

N \ge 2

。有

N(N+1)

名身高互不相同的足球运动员站成一排。亚历克斯爵士想从这一排中去掉

N(N-1)

名运动员，使剩下的

2N

名运动员组成的新一排满足以下

N

个条件：两个最高的运动员之间没有任何人，第三高与第四高的运动员之间没有任何人，

\ldots

，两个最矮的运动员之间没有任何人。证明这总是可以做到的。

第 4/7 步：保留重复的一对，删去其余部分

上一步下一步

S\gets S\cup\{x_q,x_p\},\quad D\gets\big([1,p]\setminus\{q,p\}\big)\cup\big(G_k\setminus\{x_q,x_p\}\big)

详细分析

把 $x_q$ 和 $x_p$ 放入幸存集合 $S$ 中，然后删去初始片段 $x_1,\ldots,x_p$ 中的其他所有运动员，以及排在后面的 $G_k$ 中剩余的所有成员。位置 $q$ 与 $p$ 之间严格地没有任何人存活，于是 $x_q$ 与 $x_p$ 在幸存者中变得物理相邻，恰好符合从 $G_k$ 中取出的这一对所要求的条件。