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

shadow_Mas

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

mathe

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

northwolves

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

mathe

假定从{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

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]\)，且其所有子集的元素和互不相同。
显然，元素中不允许包含 \(0\)，也不允许若干个元素的代数和为 \(0\)，否则就与空集 \(\varnothing\) 的相同了。

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

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

gxqcn

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

在给定元素个数 \(n\) 后，则 \(\min\{U^2 - L^2\}\) 能达到多少？
这同时考虑了范围跨度及平均值综合因素。