跳至主要內容

奥林匹克计数谜题

Alex Sun2023年4月5日奇思妙想数学大约 3 分钟

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

1. 原题重述

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

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

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

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

1.1 穷举法

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

22000=1148⋯376⏞603≈1.148×10602 2^{2000} = \overbrace{1148 \cdots 376}^{603} \approx 1.148 \times 10^{602}

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

15⋅22000 \frac{1}{5} \cdot 2^{2000}

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

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

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)

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

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

[
    [],
    [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(x)=(1+x1)(1+x2)(1+x3)(1+x4)(1+x5) 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)

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

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

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

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

f0=0f1=1fi=fi−1+fi−2, i⩾2 \begin{aligned} f_0 &= 0 \\ f_1 &= 1 \\ f_{i} &= f_{i-1} + f_{i-2},\, i \geqslant 2 \end{aligned}

构造生成函数

F(x)=0+1x1+1x2+2x3+3x4+5x5+8x6+⋯ F(x) = 0 + 1x^1 + 1x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + \cdots

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

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

解得

F(x)=x1−x−x2 F(x) = \frac{x}{1 - x - x^2}

我们给它做一点变形：

F(x)=x1−x−x2=x(1−φx)(1+1φx)=1/51−φx−1/5 \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}}{} \end{aligned}