Same Sum Subsets

Posted on 24th Mar 2026

题目
- 分析
- 思考
- C++程序

题目

Amy让Brad从$1$到$100$之间选出$10$个互不相同的数，悄悄写在一张纸上。

她随后说，她愿意用$100:1$打赌：Brad选出的这$10$个数中，一定存在两个非空、互不相交的子集，它们的元素和相同。

Amy是在胡说吗？

分析

Amy并没有胡说；她一定是对的。

关键是看这$10$个数的所有非空子集的和。

$10$个元素一共有$2^{10}-1=1023$个非空子集。另一方面，这$10$个数都在$1$到$100$之间，而且互不相同，所以它们的总和最多出现在取最大的$10$个数时，也就是$91+92+\cdots+100=955$。

因此，任一非空子集的和只能是$1$到$955$之间的某个整数，最多只有$955$种可能。

但非空子集却有$1023$个，比可能的和还多。由鸽笼原理，必有两个不同的非空子集$A,B$满足$\sum A=\sum B$。

现在还差一步：题目要求这两个子集必须互不相交。

如果$A,B$有公共元素，就把公共部分从两边同时删去。删去相同的元素后，两边的和仍然相等，而且这两个新子集显然互不相交。

还要说明删完以后两边都不是空集。

如果$A\setminus B$为空，就说明$A$里的每个元素本来也都在$B$里，也就是$A\subseteq B$。但$A,B$又是不同子集，所以$B$里一定还有至少一个不在$A$里的元素。由于这里所有数都是正数，把这个额外元素加进去以后，$B$的元素和就会严格大于$A$的元素和，也就是$\sum B>\sum A$。这和前面已经知道的$\sum A=\sum B$矛盾。

所以$A\setminus B$不可能为空。同理，$B\setminus A$也不可能为空。

因此，确实存在两个非空且互不相交的子集，它们的元素和相同。

所以答案是：Amy没有疯，她稳赢。

思考

如果把题目里的$10$个数改成$n$个数，同样的思路仍然适用。

$n$个数共有$2^n-1$个非空子集；而这$n$个互不相同、落在$1$到$100$之间的数，它们的总和最大出现在取最大的$n$个数时，也就是$(101-n)+(102-n)+\cdots+100=\frac{n(201-n)}{2}$。

因此，只要$2^n-1>\frac{n(201-n)}{2}$$，就仍然能用同样的鸽笼原理保证：一定存在两个非空、互不相交的子集，它们的元素和相同。

直接代入可得：

当$n=9$时，$2^9-1=511$，而最大的总和是$92+\cdots+100=864$，这个估计还不够；
当$n=10$时，$2^{10}-1=1023$，而最大的总和是$91+\cdots+100=955$，这时已经足够。

所以按这个简单而直接的计数方法来看，$n=10$正好是开始“保险”的门槛；当$n\le 9$时，这个赌注就不能再靠同样的理由来保证了。

C++程序

下面这个程序就按题目原意来写：输入这$10$个数，程序枚举所有非空子集，并寻找两组非空、互不相交、元素和相同的子集。

如果你想直接下载源码，可以点击这里：same_sum_subsets.cpp.txt。由于GRAV通常不会直接提供.cpp文件，这里使用可下载的文本版本；下载后把文件名改回same_sum_subsets.cpp即可。

程序的做法很直接：

用位掩码枚举这$10$个数的所有非空子集；
开一个数组，数组下标就是子集和，数组里的值就是第一次出现这个和时对应的掩码；
一旦再次遇到相同的子集和，就把两边的公共部分删去；
若删完后两边都非空，就输出这两组子集。

#include <iostream>
#include <vector>

using namespace std;

int subsetSum(const vector<int>& numbers, int mask)
{
    int total = 0;
    for (int i = 0; i < static_cast<int>(numbers.size()); ++i)
    {
        if (mask & (1 << i))
        {
            total += numbers[i];
        }
    }
    return total;
}

void printSubset(const vector<int>& numbers, int mask)
{
    cout << "{";
    bool first = true;
    for (int i = 0; i < static_cast<int>(numbers.size()); ++i)
    {
        if (mask & (1 << i))
        {
            if (!first)
            {
                cout << ", ";
            }
            cout << numbers[i];
            first = false;
        }
    }
    cout << "}";
}

int main()
{
    const int n = 10;
    vector<int> numbers(n);
    cout << "请输入这 10 个数：";
    for (int i = 0; i < n; ++i)
    {
        cin >> numbers[i];
    }

    int firstMaskBySum[956] = {};

    for (int mask = 1; mask < (1 << n); ++mask)
    {
        int sum = subsetSum(numbers, mask);

        if (firstMaskBySum[sum] == 0)
        {
            firstMaskBySum[sum] = mask;
            continue;
        }

        int otherMask = firstMaskBySum[sum];
        int leftOnly = otherMask & ~mask;
        int rightOnly = mask & ~otherMask;

        if (leftOnly != 0 && rightOnly != 0)
        {
            cout << "找到两组非空且互不相交、和相同的子集：\n";
            printSubset(numbers, leftOnly);
            cout << " 和 ";
            printSubset(numbers, rightOnly);
            cout << "，它们的元素和都是 " << subsetSum(numbers, leftOnly) << "。\n";
            return 0;
        }
    }

    cout << "没有找到满足条件的两组子集。\n";
    return 0;
}

Table of Contents

题目

分析

思考

C++程序