MathLabs

第5题

给定整数 N≥2N \ge 2。有 N(N+1)N(N+1) 名身高互不相同的足球运动员站成一排。亚历克斯爵士想从这一排中去掉 N(N−1)N(N-1) 名运动员,使剩下的 2N2N 名运动员组成的新一排满足以下 NN 个条件:两个最高的运动员之间没有任何人,第三高与第四高的运动员之间没有任何人,…\ldots,两个最矮的运动员之间没有任何人。证明这总是可以做到的。
第 2/7 步:把这一排分成身高区块
G1<G2<⋯<GN,∣Gj∣=N+1G_1<G_2<\cdots<G_N,\qquad |G_j|=N+1
详细分析

按位置顺序把运动员列为 x1,…,xN(N+1)x_1,\ldots,x_{N(N+1)},并给每个人赋予其整体身高名次。仅按身高把他们分成 NN 个连续的区块 G1,…,GNG_1,\ldots,G_N,每块大小为 N+1N+1,使得 GjG_j 中的每个成员都比 Gj+1G_{j+1} 中的每个成员矮。若最终的 2N2N 名幸存者恰好在每个区块中各含 22 人,这些配对就会自动按区块顺序占据所需的连续身高名次 (2j−1,2j)(2j-1,2j)。