shadow_Mas 发表于 2025-9-19 21:45:36

求人工证明:集合{9个两位数}存在两个不相交的等和子集

按照集合的“互异性”定义,自然是9个不同的两位数。
这个问题被计算机穷举证明了,但我没有找到一个合理的数学证明,求教各位大神。

mathe 发表于 2025-9-20 08:03:43

计算机枚举应该比较合适。
当然如果换成十个数的集合,就可以轻松证明而不需要枚举了

northwolves 发表于 2025-9-20 22:54:27

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

mathe 发表于 2025-9-21 07:45:16

假定从{a, a+1, ..., a+M-1}中挑选9个数,那么{9个数}的1-5元子集数目为\(\sum_{h=1}^5 {9\choose h}=381\).
这381个子集元素和的最小值为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 发表于 2025-9-21 09:07:50

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 发表于 2025-9-21 11:44:25

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

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

mathe 发表于 2025-9-22 10:10:42

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 发表于 2025-9-22 15:18:22

推广一下:

探寻 \(n\) 元集合:其元素均为整数,取值范围为 \(\),且其所有子集的元素和互不相同。
显然,元素中不允许包含 \(0\),也不允许若干个元素的代数和为 \(0\),否则就与空集 \(\varnothing\) 的相同了。

若已知 \(3\) 个参数 \(( n, L, U )\) 中的 \(2\) 个,求未知的那个参数允许的取值范围。
或者:当 \(n\) 已知时,要求 \(U - L\) 取值尽可能小;否则,确定 \(n\) 最大可取多少?

比如,当前的 \(n=9, L=10\),计算 \(U\) 最小可为多少?(显然 \(99\) 是不够的)
或者,\(L=100, U=999\),计算 \(n\) 最大可为多少?

gxqcn 发表于 2025-9-23 16:03:54

显然,满足要求的集合可缩放,但不可平移
比如{4,5,6}满足,则缩放成{40,50,60}肯定满足,但平移成{1,2,3}就不满足了

在给定元素个数 \(n\) 后,则 \(\min\{U^2 - L^2\}\) 能达到多少?
这同时考虑了范围跨度及平均值综合因素。
页: [1]
查看完整版本: 求人工证明:集合{9个两位数}存在两个不相交的等和子集