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

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

d (x, y) = # {i \in {1, \dots, n} : x_{i} \neq = y_{i}} .

(1)
对任意整数 $r$ ，若 $1 \leq r \leq n$ ，证明：对每个固定 $x \in X$ ，
$# {y \in X : d (x, y) \leq r} = i = 0 \sum r (q - 1)^{i} (i n) .$
(2)
证明恒等式
$q^{n} = i = 0 \sum n (q - 1)^{i} (i n) .$
只允许使用第(1)问的结论。
(3)
设 $r$ 为满足 $1 \leq r \leq n$ 的整数， $C \subseteq X$ 含 $M$ 个元素，且满足：
1. (i)
  $C$ 中任意两个不同元素的距离均不少于 $r$ ；
2. (ii)
  在满足条件(i)的所有子集中， $C$ 的元素个数最大。
证明
$M \geq \frac{q ^{n}}{i = 0 \sum r - 1 ( q - 1 ) ^{i} ( i n )} .$