奥林匹克计数谜题

3Blue1Brown 奥林匹克计数谜题讲解，视频地址 YouTube。

• 1. 原题重述
  • 1.1 穷举法
  • 1.2 生成函数
• 2. 使用单位根解决问题
  • 2.1 五次单位根
  • 2.2 构造生成函数
  • 2.3 利用单位根滤波
  • 2.4 计算结果
• 3. 总结
• 4. 参考资料

1. 原题重述

本题来源于 3Blue1Brown 在 YouTube: Olympiad level counting 视频中介绍的题目，其原题目出自 Titus Andreescu & Zuming Feng. 102 Combinatorial Problems，如果你想了解更多，推荐看原视频。

原题：Find the number of subsets of $\{1,\,\cdots,\,2000\}$, the sum of whose elements is divisible by $5$.

翻译：对于集合 $\{1,\,2,\,3,\,\cdots,\,2000\}$，它有多少个子集满足条件：子集中所有数之和能被 $5$ 整除？

首先，我们先举几个例子。对于子集 $\{3,\,1,\,4\}$，其和为 $8$，不满足条件，因此它不是结果之一。而对于子集 $\{2,\,3,\,5\}$，其和为 $10$，满足条件。

1.1 穷举法

如果使用穷举法，是一定能计算出来的，只不过使用计算机计算所需的时间可能要超过宇宙历史。因为这个 $2000$ 个元素集合的子集个数为

$$2^{2000} = \overbrace{1148 \cdots 376}^{603} \approx 1.148 \times 10^{602}$$

我们猜测，每一种情况（和模 $5$ 的数字分别是 $0,\,1,\,2,\,3,\,4$）的子集应该是大致相等的，我们猜测结果为

$$\frac{1}{5} \cdot 2^{2000}$$

很不幸这个数字不是整数，我们想知道确切结果。

但是穷举法对于少数几个的数字也是可以计算的，例如 $5$ 个：

set_length = 5
s = 1 << set_length

count = 0
for i in range(s):
    bin_repr = bin(i).removeprefix('0b').zfill(set_length)[::-1]
    subset = [
        k for k, v in zip(range(1, set_length + 1), bin_repr)
        if v == '1'
    ]
    print(subset)
    sum_subset = sum(subset)
    if sum_subset % 5 == 0:
        count += 1
print(count)

我们通过手动计算，也可以得到 $5$ 个元素的数组满足条件的子集有 $8$ 个。

我们把不同的子集归类一下：

[
    [],
    [1],
    [2],
    [1, 2], [3],
    [1, 3], [4],
    [2, 3], [1, 4], [5],
    [1, 2, 3], [2, 4], [1, 5],
    [1, 2, 4], [3, 4], [2, 5],
    [1, 3, 4], [1, 2, 5], [3, 5],
    [2, 3, 4], [1, 3, 5], [4, 5],
    [1, 2, 3, 4], [2, 3, 5], [1, 4, 5],
    [1, 2, 3, 5], [2, 4, 5],
    [1, 2, 4, 5], [3, 4, 5],
    [1, 3, 4, 5],
    [2, 3, 4, 5],
    [1, 2, 3, 4, 5]
]

和相同的子集被安排在同一行，计算它们的个数，发现它们居然存在某种对称？

1.2 生成函数

考虑生成函数

$$p\left(x\right) = \left(1 + x^1\right)\left(1 + x^2\right)\left(1 + x^3\right)\left(1 + x^4\right)\left(1 + x^5\right)$$

我们将每个项展开，每个变量的系数就是和为指数的子集数量。

很神奇？可以使用项的选择来解释，也可以使用二项式定理解释，具体可以自行理解。

作者在此举例了斐波那契数列的一种非常有趣的解法。

不妨定义斐波那契数列 $\{f_n\}$ 如下：

$$\begin{aligned} f_0 &= 0 \\ f_1 &= 1 \\ f_{i} &= f_{i-1} + f_{i-2},\, i \geqslant 2 \end{aligned}$$

构造生成函数

$$F(x) = 0 + 1x^1 + 1x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + \cdots$$

由于 $f_{i} = f_{i-1} + f_{i-2}$ 显然有

$$F(x) = xF(x) + x^2F(x) + x$$

解得

$$F(x) = \frac{x}{1 - x - x^2}$$

我们给它做一点变形：

$$\begin{aligned} F(x) &= \frac{x}{1 - x - x^2} \\ &= \frac{x}{\left(1 - \varphi x\right)\left(1 + \frac{1}{\varphi} x\right)} \\ &= \frac{1 / \sqrt{5}}{1 - \varphi x} - \frac{1/\sqrt{5}}{1 + \frac{1}{\varphi} x} \end{aligned}$$

其中 $\varphi = \frac{1 + \sqrt{5}}{2}$ 是黄金分割比。通过这种方式，我们可以利用生成函数的代数性质来推导数列的通项公式。

2. 使用单位根解决问题

2.1 五次单位根

回到我们的原问题。我们考虑五次单位根 $\omega = e^{2\pi i / 5}$，它具有以下性质：

$$\omega^5 = 1$$

所有五次单位根为 $1, \omega, \omega^2, \omega^3, \omega^4$，它们满足：

$$1 + \omega + \omega^2 + \omega^3 + \omega^4 = 0$$

2.2 构造生成函数

对于集合 $\{1, 2, 3, \cdots, 2000\}$，我们构造生成函数：

$$P(x) = \prod_{k=1}^{2000} (1 + x^k)$$

展开后，$x^n$ 的系数表示和为 $n$ 的子集个数。

2.3 利用单位根滤波

我们需要计算和能被 5 整除的子集个数，可以利用单位根的性质：

$$\frac{1}{5} \sum_{j=0}^{4} P(\omega^j)$$

这是因为对于任意整数 $n$：

$$\frac{1}{5} \sum_{j=0}^{4} \omega^{jn} = \begin{cases} 1, & \text{if } 5 \mid n \\ 0, & \text{otherwise} \end{cases}$$

2.4 计算结果

计算 $P(1)$：

$$P(1) = \prod_{k=1}^{2000} (1 + 1) = 2^{2000}$$

对于 $P(\omega^j)$ 其中 $j \neq 0$，由于 $\omega^5 = 1$，我们有：

$$P(\omega^j) = \prod_{k=1}^{2000} (1 + \omega^{jk})$$

由于周期性，可以将 $k$ 按模 5 分组计算。经过计算，当 $j \neq 0$ 时：

$$P(\omega^j) = (-1)^{400} \cdot \omega^{j \cdot 1000 \cdot 2001 / 2} = \omega^{j \cdot 2001000}$$

由于 $2001000 \equiv 0 \pmod{5}$，所以 $\omega^{j \cdot 2001000} = 1$。

因此答案为：

$$\frac{1}{5}(2^{2000} + 1 + 1 + 1 + 1) = \frac{2^{2000} + 4}{5}$$

3. 总结

本题通过以下步骤解决：

1. 生成函数构造：将组合问题转化为多项式问题
2. 单位根滤波：利用单位根的性质筛选满足条件的项
3. 周期性计算：利用单位根的周期性简化计算

这种方法不仅适用于本题，还可以推广到更一般的模运算组合计数问题。通过这个优雅的解法，我们避免了直接枚举 $2^{2000}$ 个子集，而是利用数学工具在常数时间内得到了答案。

4. 参考资料

• https://www.youtube.com/watch?v=bOXCLR3Wric - 3Blue1Brown: Olympiad level counting
• https://link.springer.com/book/10.1007/978-0-8176-8222-4 - 102 Combinatorial Problems
• https://puzzlingthroughmed.com/olympiad-counting-puzzle/ - 详细解析