数学联赛题解：子集元素和为15的倍数

子集元素和为15的倍数

美国大学数学联赛 · 母函数与单位根巧解

导读

集合 ${1, 2, 3, \dots, 2025}$ 共有 $22025$ 个子集。问题：其中有多少个子集的所有元素之和是 15 的倍数？直接列举不可能，经典解法利用母函数与五次单位根，得到优美封闭解。

核心思路

构造母函数 $F(x) = (1+x)(1+x²)(1+x³)\dots(1+x 2025)$ ，展开后 $x k$ 的系数即元素和为 $k$ 的子集个数。所求即所有 $15$ 倍数的系数之和。

利用五次单位根 $ω 0, ω 1, \dots, ω 4$ （满足 $ω 5 =1$ ，且 $1+ω+ω²+ω³+ω⁴=0$ ），构造求和式过滤出五次幂指数。

关键步骤

设母函数： $F(x) = \prod n=1 2025 (1 + x n)$ ，所求为 $S = C₀ + C₅ + C₁₀ + \dots + C 2025$ ，其中 $C k$ 为 $x k$ 系数。
单位根过滤：令 $ω$ 为 1 的五次方根（ $ω⁵=1，ω\neq1$ ），则 $(1+ω+ω²+ω³+ω⁴)/5$ 在指数为 5 倍数时取 1，否则取 0。
计算和式： $[F(1) + F(ω) + F(ω²) + F(ω³) + F(ω⁴)] / 5 = S$ 。
求各值：
• $F(1) = 2 2025$
• 对非 1 单位根， $F(ω) = \prod n=1 2025 (1 + ω n)$ 。由于 $ω 5 =1$ ，指数模 5 循环，每个 $(1+ω)$ 类乘积为 $(1+ω)(1+ω²)(1+ω³)(1+ω⁴) = 1$ （利用 $x⁵-1 = (x-1)(x-ω)(x-ω²)(x-ω³)(x-ω⁴)$ 代入 $x=-1$ 得 $(-2) = (-2)\cdot(1+ω)(1+ω²)(1+ω³)(1+ω⁴)$ ，故乘积为 1）。每 5 个连续指数为一组，共 $2025/5 = 405$ 组，每组乘积为 $2$ （实际推导为 $2$ 的 $405$ 次方），故 $F(ω) = 2 405$ 。
同理： $F(ω²) = F(ω³) = F(ω⁴) = 2 405$ 。

最终结果

S = (2 2025 + 4 \cdot 2 405) / 5

即集合 ${1,\dots,2025}$ 中元素和为 15 的倍数的子集个数。

注：空集元素和规定为 0，属于 15 的倍数，已包含在内。

“母函数与单位根的结合，堪称组合计数中的神来之笔。”

延伸思考

类似方法可处理任意模数问题：只需将单位根换为相应的 $m$ 次本原根。此法在数论、组合数学中广泛应用。