MathLabs

第5题

给定整数 N≥2N \ge 2。有 N(N+1)N(N+1) 名身高互不相同的足球运动员站成一排。亚历克斯爵士想从这一排中去掉 N(N−1)N(N-1) 名运动员,使剩下的 2N2N 名运动员组成的新一排满足以下 NN 个条件:两个最高的运动员之间没有任何人,第三高与第四高的运动员之间没有任何人,…\ldots,两个最矮的运动员之间没有任何人。证明这总是可以做到的。
第 5/7 步:每个幸存的区块仍有足够多的人
∀j≠k: N≤∣Gj∩(p,N(N+1)]∣≤N+1\forall j\neq k:\ N\le \big|G_j\cap(p,N(N+1)]\big|\le N+1
详细分析

由于除 GkG_k 以外的任何区块在被删去的前缀 x1,…,xpx_1,\ldots,x_p 中至多出现 11 名成员,满足 j≠kj\neq k 的每个区块 GjG_j 在位置 pp 右侧未被删去的运动员中,仍保留着其 N+1N+1 名成员里至少 NN 名。如有需要,从任何仍剩 N+1N+1 名成员的区块中再舍弃一名多余的幸存者,使剩下的 N−1N-1 个区块都恰好被削减到 NN 人,从而总共得到恰好 (N−1)N(N-1)N 人组成的候选池。