MathLabs

第5题

给定整数 N≥2N \ge 2。有 N(N+1)N(N+1) 名身高互不相同的足球运动员站成一排。亚历克斯爵士想从这一排中去掉 N(N−1)N(N-1) 名运动员，使剩下的 2N2N 名运动员组成的新一排满足以下 NN 个条件：两个最高的运动员之间没有任何人，第三高与第四高的运动员之间没有任何人，…\ldots，两个最矮的运动员之间没有任何人。证明这总是可以做到的。
第 3/7 步：最先出现的重复区块出现得很早
上一步下一步
N+1>N  ⟹  ∃ q<p≤N+1: xq,xp∈GkN+1>N\implies \exists\, q<p\le N+1:\ x_q,x_p\in G_k
详细分析

从左到右逐个位置扫描这一排，在第一个使得 xpx_p 所在区块中已经出现过更早的运动员 xqx_q（满足 q<pq<p）的下标 pp 处停下；把这个重复出现的区块记为 GkG_k。由于只有 NN 个区块，这样的重复必定发生在最前面的 N+1N+1 个位置之中，即根据鸽笼原理，被扫描的 N+1N+1 名运动员不可能全部落在不同的区块里。pp 的最小性于是迫使除 GkG_k 以外的每个区块在初始片段 x1,…,xpx_1,\ldots,x_p 中至多贡献 11 名运动员，而 GkG_k 在其中恰好贡献 22 名运动员，即 xqx_q 与 xpx_p。