2024 年浙江预赛

解答

计数所有二元子集，得

所以 $k\ge 5$。

反设 $k=5$。对每个 $x\in S$，定义

覆盖条件等价于任意不同 $x,y$ 都有 $I_x\cap I_y\ne \varnothing$。又

故平均值为 $5/2$，存在 $x$ 使 $|I_x|\le 2$。若 $|I_x|=1$，则所有其他 $I_y$ 都含这一唯一指标，相应的 $A_i$ 将含有全部 $998$ 个元素，矛盾。若 $|I_x|=2$，设为 $\{i,j\}$，则每个 $y\ne x$ 至少属于 $A_i,A_j$ 之一，而 $x$ 同时属于二者，故

也与左端等于 $998$ 矛盾。因此 $k\ne 5$，从而 $k\ge 6$。

下面构造 $k=6$。把 $S$ 的每个元素赋予一个非空指标集 $I_x\subseteq \{1,\dots ,6\}$： 各取 $248$ 个元素赋予

余下 $6$ 个元素依次赋予

令 $A_i=\{x\in S:i\in I_x\}$。上述指标集任意两个都有交集，且每个指标在前 $992$ 个元素中出现 $496$ 次、在最后六个元素中出现 $3$ 次，所以 $|A_i|=499$。于是任意二元子集都被某个 $A_i$ 覆盖。

故