2026 年中科大少年班营一 · 第 6 题

解答

（1）按通常取子集的整数范围 $0\le m\le n$。若 $B=\{b_1<\cdots <b_m\}$ 完美，令 $c_i=b_i-(i-1)$，则 $1\le c_1<\cdots <c_m\le n-m+1$，反之也成立。因此概率为

其中无可行位置时分子为零，$m=0$ 时空集概率为一。 （2）证明更强命题：$r$ 个内部无相邻数、每个至少含 $r$ 个元素的有限整数集合，总能各选一元素，所选仍无相邻或重复。对 $r$ 归纳，$r=1$ 显然。取全部集合中的最小元素 $u$，从含它的一个集合选 $u$ 并删去该集合。从其他每个集合删去 $u,u+1$；内部不相邻保证最多删一个，而且全局最小性排除了任何小于 $u$ 的元素。于是余下 $r-1$ 个集合各至少有 $r-1$ 个元素，且所有剩余元素大于 $u+1$。用归纳从它们各取一元素，再加 $u$，仍无相邻或重复。取 $r=m$ 即得题目结论。