并排比较

2015 年安徽预赛 第 12 题

P010779 · 组合计数综合

已知 31 位学生参加了某次考试，考试共有 10 道题，每位学生解出了至少 6 道题.求证：存在两位学生，他们解出的题目中至少有 5 道相同.

2024 年中科大少年班营二 第 2 题

P009933 · 组合计数综合

设$q,n$为正整数，$A=\{1,2,\dots ,q\}$，$X=A^n$。 对$x=(x_1,\dots ,x_n),y=(y_1,\dots ,y_n)\in X$，定义

1. (1)

   对任意整数$r$，若$1\le r\le n$，证明：对每个固定$x\in X$，

   $$\#\{y\in X:d(x,y)\le r\}=\sum _{i=0}^r(q-1{)}^i(\genfrac{}{}{0ex}{}{n}{i}).$$
2. (2)

   证明恒等式

   $$q^n=\sum _{i=0}^n(q-1{)}^i(\genfrac{}{}{0ex}{}{n}{i}).$$

   只允许使用第(1)问的结论。

3. (3)

   设$r$为满足$1\le r\le n$的整数，$C\subseteq X$含$M$个元素，且满足：

   1. (i)

      $C$中任意两个不同元素的距离均不少于$r$；

   2. (ii)

      在满足条件(i)的所有子集中，$C$的元素个数最大。

   证明

   $$M\ge \frac{q^n}{\sum _{i=0}^{r-1}(q-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})}.$$