Project Euler 106

发表于 2022-05-06 更新于 2025-12-23 分类于 Project Euler 阅读次数：本文字数： 1.7k 阅读时长 ≈ 2 分钟

Project Euler 106

题目

Special subset sums: meta-testing

Let $S(A)$ represent the sum of elements in set $A$ of size $n$. We shall call it a special sum set if for any two non-empty disjoint subsets, $B$ and $C$, the following properties are true:

$S(B) \neq S(C)$; that is, sums of subsets cannot be equal.
If $B$ contains more elements than $C$ then $S(B) > S(C)$.

For this problem we shall assume that a given set contains n strictly increasing elements and it already satisfies the second rule.

Surprisingly, out of the $25$ possible subset pairs that can be obtained from a set for which $n = 4$, only $1$ of these pairs need to be tested for equality (first rule). Similarly, when $n = 7$, only $70$ out of the $966$ subset pairs need to be tested.

For $n = 12$, how many of the $261625$ subset pairs that can be obtained need to be tested for equality?

NOTE: This problem is related to Problem 103 and Problem 105.

解决方案

由于已经假定了集合$A$已经满足了第二个条件，因此，只需要考虑两个集合$B,C$大小相同（$|B|=|C|=k$）时的情形。

容易发现，不需要求和的情形是：对于 $\forall i:1\leq i\leq k$，$B$中的第$i$小元素都小于（或大于）$C$中的第$i$小元素。在最后得出需要求和的时候，需要将这部分情形减去，留下的则计入答案。

因此，首先需要从$A$中选取$2k$个元素，其中$k$个分给$B$集合，另外$k$个分给$C$。由于$B,C$的先后不需要关心，因此一共有$\dfrac{\binom{2k}{k}}{2}$种分法。

下一个问题的正式描述：已知集合中有$2k$个不同的元素，其中$k$个分给$B$集合，另外$k$个分给$C$。（不失一般性，）对于 $\forall i:1\leq i\leq k$，$B$中的第$i$小元素都小于$C$中的第$i$小元素，有多少种划分方法？

为解决这个问题，先以一个例子说明：

设$k=3$，那么就将$1\sim 6$这$6$个数进行放入集合$B$和$C$中。

如果第$i$个数放入$B$中，那么字符串第$i$位记为左圆括号’(‘，否则记为右圆括号’)’。

那么有$5$种方法：

括号字符串	$B$	$C$
()()()	${1,3,5}$	${2,4,6}$
()(())	${1,3,4}$	${2,5,6}$
(())()	${1,2,5}$	${3,4,6}$
((()))	${1,2,3}$	${4,5,6}$
(()())	${1,2,4}$	${3,5,6}$

每个括号字符串对应着一种分配方法。可以发现这个括号字符串有一下特点：

左圆括号和右圆括号的数量相等
每个字符串的前缀中，左圆括号的数量不会少于右圆括号。这也就说明了，$B$中的每一个数，$C$中总有更大的数和它们一一对应。

符合这种特征的字符串的个数，称为卡特兰数，在OEIS中为A000108。第$n$项为$C(n)=\dfrac{\binom{2n}{n}}{n+1}$。

综上所述，答案为：

$\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2k}\left(\dfrac{\binom{2k}{k}}{2}-\dfrac{\binom{2k}{k}}{k+1}\right)$

代码

from tools import C

N = 12
ans = sum(C(N, 2 * k) * (C(2 * k, k) // 2 - C(2 * k, k) // (k + 1)) for k in range(1, N // 2 + 1))
print(ans)