培玉 · 一试

专题地图 › 组合计数综合

2023 年吉林预赛

F4解答题组合计数综合

设 $n$ 为给定的正整数，

S_{n} \subseteq {α ∣ α = (p_{1}, p_{2}, \dots, p_{n}), p_{k} \in {0, 1}, k = 1, 2, \dots, n} .

对于集合 $S_{n}$ 中的任意元素 $β = (x_{1}, x_{2}, \dots, x_{n})$ 和 $γ = (y_{1}, y_{2}, \dots, y_{n})$ ，满足：若 $β = γ$ ，则 $\sum_{i = 1}^{n} x_{i} y_{i}$ 为奇数；若 $β \neq = γ$ ，则 $\sum_{i = 1}^{n} x_{i} y_{i}$ 为偶数。

（1）当 $n = 5$ 时，求集合 $S_{5}$ 中元素个数的最大值；

（2）当 $n \geq 6$ 时，求集合 $S_{n}$ 中元素个数的最大值。

作答

这是解答题，请在纸上写出完整过程。写完后对照解答给自己评分。

解析

为什么评为 F4（会透露解法方向）

需把自交为奇、互交为偶转为任意非空子集和非零，再由两个子集碰撞的对称差证明所有子集和互异，最后建立 $2^{m} \leq 2^{n}$ 并构造达到。

用到的方法（会透露解法方向）

核心工具：剩余类、幂周期与局部排除、抽屉原理与极端构造

专题卡：代数编码与操作不变量