计算机枚举证明的组合问题，求是否有数学解法

shadow_Mas

证明：对于任意9个互不相同的两位数构成的集合，总能找到两个不相交的子集，使得他们的和相等
这个问题已经被计算机暴力枚举证明了，但我尚没有找到一个合理的数学解，求教各位大神

hujunhua

描述需要更清晰，如果按“9个互不相同的两位数总可以划分为和相等的两堆”显然是不成立的，因为无法保证这9个两位数之和是偶数。

mathe

其实就是要证明这九个数集合必然存在两个不同的子集具有相同的和。
计算机枚举应该比较合适。
当然如果换成十个数的集合，就可以轻松证明而不需要枚举了

northwolves

穷举了10-39 30个数字的9数集合，未找到反例

mathe

我们查看从M个连续数字中挑选9个数字，那么这9个元素1-5个元素构成的子集数目为\(\sum_{h=1}^5 {9\choose h}=381\).
于是如果如果\(M=70\),假设这M个数为a,a+1,...,a+M-1, 那么这318个集合元素和的最小值为a,最大值为(a+M-1)+(a+M-2)+...+(a+M-5)=5a+5M-15
对于本题a=10,M=70,得到最小值10，最大值385， 所以最多只能由376中不同的选择，所以381个子集中必然有和相同的。
也就是10-79的集合中选择9个数，9个数必然有两个子集元素和相同

northwolves

10到44中任意取8个不同的两位数，总能找到两个不相交的子集和相等。而对于10到45，存在反例，如：{11, 17, 20, 22, 23, 24, 25, 45}
45到62中任意取8个不同的两位数，总能找到两个不相交的子集和相等。而对于45到61，存在反例，如：{45, 46, 47, 48, 49, 50, 51, 61}

gxqcn

northwolves 发表于 2025-9-20 22:54
穷举了10-39 30个数字的9数集合，未找到反例

9 个数的非空子集有 2^9 -1 = 511 个，用鸽笼原理很容易证明，若在 10~62 间取值，必存在等和子集

mathe

8个互不相同的两位数，有24895种，可以使得所有子集的元素和互不相同。
而且其中有两种方案最小元素可以高达58，比较让人意外:
8:{ 56 58 60 76 85 91 94 97 }
8:{ 56 59 62 77 86 94 95 96 }
8:{ 56 62 68 80 83 97 98 99 }
8:{ 56 62 68 80 95 97 98 99 }
8:{ 57 60 63 69 79 96 97 98 }
8:{ 57 60 63 79 88 96 97 98 }
8:{ 58 59 60 77 86 92 95 98 }
8:{ 58 61 64 79 89 97 98 99 }

gxqcn

推广一下：

某组 n 个整数，取值范围为 [L, U]，其所有子集的元素和互不相同。
若已知 3 个参数 ( n, L, U ) 中的 2 个，求未知的那个参数允许的取值范围。

显然，整数元素中，不允许包含 0；也不允许若干个元素的代数和为 0，否则就与空集的相同了。