最小集合

northwolves

王守恩 发表于 2025-11-27 10:51
从{1, 2, 3, 4, ..., n}里选择k个不同的数, 没有等和对。若再加1个数(剩下数任选)则必有等和对。记k最小 =  ...

1. sidon[s_]:=DuplicateFreeQ[Total/@Subsets[s,{2}]];f[n_]:=(a=Range@n;b=Range[Ceiling[n*4/5]];Do[v=Subsets[b,{m}];For[k=1,k<=Length@v,k++,t=v[[k]];If[sidon[t],w=Complement[a,t];
   
2. If[AllTrue[w,!sidon[Union[t,{#}]]&],Return[{n,Length@t,t}]]]],{m,7}]);
   
3. Do[Print[f[n]],{n,40}]

复制代码

{1,1,{1}}
{2,2,{1,2}}
{3,3,{1,2,3}}
{4,3,{1,2,3}}
{5,3,{1,2,4}}
{6,4,{1,2,3,5}}
{7,4,{1,2,3,5}}
{8,4,{1,2,3,6}}
{9,4,{1,2,3,7}}
{10,4,{1,2,4,7}}
{11,4,{1,2,4,8}}
{12,4,{1,2,4,9}}
{13,4,{3,5,6,10}}
{14,5,{1,2,3,5,10}}
{15,5,{1,2,3,5,11}}
{16,5,{1,2,3,5,12}}
{17,5,{1,2,3,6,12}}
{18,5,{1,2,3,6,13}}
{19,5,{1,2,3,6,14}}
{20,5,{1,2,4,6,15}}
{21,5,{1,2,5,7,15}}
{22,5,{1,3,4,8,17}}
{23,5,{1,3,6,7,17}}
{24,5,{2,4,7,8,18}}
{25,5,{3,7,8,10,20}}
{26,5,{4,8,9,11,21}}
{27,5,{6,10,12,17,20}}
{28,5,{7,14,15,18,20}}
{29,6,{1,2,3,6,9,21}}
{30,6,{1,2,3,6,9,22}}
{31,6,{1,2,3,6,9,23}}
{32,6,{1,2,3,9,21,24}}
{33,6,{1,2,4,8,13,27}}
{34,6,{1,2,4,8,13,27}}
{35,6,{1,2,5,7,14,28}}
{36,6,{1,2,7,11,24,26}}
{37,6,{1,2,9,11,22,26}}
{38,6,{1,2,9,11,24,28}}
{39,6,{1,3,10,11,25,29}}
{40,6,{1,3,10,11,26,30}}

northwolves

{41,6,{1,9,11,22,23,27}}
{42,6,{1,10,11,22,24,28}}
{43,6,{1,15,20,21,23,33}}
{44,6,{3,12,13,24,26,30}}
{45,6,{5,13,15,26,27,31}}
{46,6,{6,14,16,27,28,32}}
{47,6,{8,14,24,28,31,36}}
{48,6,{11,16,23,25,33,34}}
{49,6,{12,17,24,26,34,35}}
{50,7,{1,2,3,7,14,34,37}}
{51,7,{1,2,3,10,16,32,35}}
{52,7,{1,2,3,10,16,34,37}}
{53,7,{1,2,3,10,16,35,38}}
{54,7,{1,2,3,13,16,32,38}}
{55,7,{1,2,3,13,16,34,40}}
{56,7,{1,2,3,13,16,35,41}}
{57,7,{1,2,9,14,18,38,40}}
{58,7,{1,2,9,14,18,39,41}}
{59,7,{1,2,9,14,18,40,42}}
{60,7,{1,2,9,14,18,41,43}}

northwolves

k=8:  {15, 25, 32, 43, 46, 68, 69, 70}
         {18, 28, 35, 46, 49, 71, 72, 73}

northwolves

这几组还是有规律的：

k=8:
{17,23,40,50,53,60,61,62}
{18,24,41,51,54,61,62,63}
{6,28,38,43,56,62,63,64}
{7,29,39,44,57,63,64,65}
{8,30,40,45,58,64,65,66}
{12,33,36,40,51,65,66,67}
{15,29,40,44,47,66,67,68}
{14,24,31,42,45,67,68,69}
{15,25,32,43,46,68,69,70}

王守恩

重点是找“节点”。1, 2, 3, 6, 14, 29, 50, ...

a(81)=8, {12, 14, 17, 20, 21, 31, 50, 70}——15#——{12, 14, 17, 20, 21, 31, 50, 70, 90}——去掉1个。

a(119)=9, {1, 38, 48, 50, 57, 62, 65, 66, 100}——18#——往前冲一冲。

a(63,64,65,66)=7, {1, 7, 22, 31, 32, 34, 51}——可以跳。

aimisiyou

王守恩 发表于 2025-11-28 10:48
重点是找“节点”。1, 2, 3, 6, 14, 29, 50, ...

a(81)=8, {12, 14, 17, 20, 21, 31, 50, 70}——15#——{ ...

有什么好的算法？

王守恩

有什么好的算法？——我只是好玩！！！譬如:

a(405)=15,  {32, 93, 118, 126, 130, 134, 141, 148, 223, 225, 244, 254, 263, 289, 306}——我还是不敢说这串数是正确的。——谢谢 northwolves！

帖子《求{1, 2, ..., 100}没有等和对的最大子集》里面有一串数——a(16)=148, {0, 3, 5, 6, 32, 49, 59, 68, 93, 106, 118, 126, 130, 134, 141, 148}——谢谢mathe！！！

{0, 3, 5, 6, 32, 49, 59, 68, 93, 106, 118, 126, 130, 134, 141, 148}——把“0”去掉。替换几个就得到上面的数字串了。

替换用的是这个代码(21#)。——B = 要替换的数。——谢谢 northwolves ！

1. n = 405; A = {32, 93, 118, 126, 130, 134, 141, 148, 223, 225, 244, 254, 263, 289, 306};
   
2. B = 32;(*要替换的数*)minVal = 32;(*最小值*)maxVal = n;(*最大值*)
   
3. F@t_ := Length@Union[Total /[url=home.php?mod=space&uid=6175]@[/url] Subsets[t, {2}]] == Binomial[Length@t, 2]; Manipulate[newA = ReplacePart[A, Position[A, B][[1]] -> newValue];
   
4. result = If[F@newA && ! Or @@ Table[F@Append[newA, x], {x, Complement[Range@n, newA]}], "正确", "错误"];
   
5. Column[{"新集合: " <> ToString[newA], "结果: " <> result}], {newValue, minVal, maxVal, 1, Appearance -> "Labeled"}, TrackedSymbols :> {newValue}]

复制代码

验算用的是这个代码。——会显示"正确",  "错误"。

1. n = 405; A = {32, 93, 118, 126, 130, 134, 141, 148, 223, 225, 244, 254, 263, 289, 306};
   
2. F[t_] := Length[DeleteDuplicates[Total /@ Subsets[t, {2}]]] == Binomial[Length[t], 2]; S = Range[n]; p = Complement[S, A]; m = True;
   
3. For[i = 1, i <= Length[p] && m, i++, x = p[[i]]; If[F[Append[A, x]], m = False;];]; If[F[A] && m, Print["正确"],  Print["错误"]]

复制代码

王守恩

接楼上的方法。

还是利用——帖子《求{1, 2, ..., 100}没有等和对的最大子集》里面的数字串——谢谢mathe！！！

a (1) = 1, {1},
a (2) = 2, {1, 2},
a (5) = 3, {2, 3, 4},
a (13) = 4, {3, 5, 6, 10}——相同的k, 应该取最大的那个n。
a (28) = 5, {7, 14, 15, 18, 20}
a (49) = 6, {12, 17, 24, 26, 34, 35}
a (69) = 7, {19, 24, 32, 33, 36, 47, 54}
a (104) = 8, {18, 28, 35, 46, 49, 71, 72, 73}
a (122) = 9, {21, 29, 41, 43, 66, 72, 73, 83, 99}
a (139) = 10, {44, 45, 51, 57, 72, 76, 87, 90, 92, 116}
a (155) = 11, {22, 37, 40, 54, 63, 67, 71, 83, 102, 107, 135}
a (173) = 12, {34, 42, 57, 60, 72, 79, 84, 85, 86, 134, 143, 154}
a (259) = 13, {54, 69, 85, 94, 101, 103, 105, 147, 148, 171, 177, 185, 212}
a (333) = 14, {19, 31, 76, 100, 124, 125, 126, 162, 208, 213, 216, 222, 235, 287}
a (405) = 15, {32, 93, 118, 126, 130, 134, 141, 148, 223, 225, 244, 254, 263, 289, 306}

答案肯定有问题——只能是给出一种趋势。

从{1, 2, 3, 4, ..., n}里选择k个不同的数, 没有等和对。若再加1个数(剩下数任选)则必有等和对。记k最小 = a(n)。

王守恩

northwolves 发表于 2025-11-28 10:02
这几组还是有规律的：

k=8:

a (1) = 1, {1},
a (2) = 2, {1, 2},
a (5) = 3, {2, 3, 4},
a (13) = 4, {3, 5, 6, 10}
a (28) = 5, {7, 14, 15, 18, 20}
a (49) = 6, {12, 17, 24, 26, 34, 35}
a (69) = 7, {19, 24, 32, 33, 36, 47, 54}
a (104) = 8, {18, 28, 35, 46, 49, 71, 72, 73}——只有这一个解吗？

这些答案有错的吗？—先试试—后面的不敢动。——太难了！

northwolves

王守恩 发表于 2025-12-2 10:11
a (1) = 1, {1},
a (2) = 2, {1, 2},
a (5) = 3, {2, 3, 4},

{104,8,{19,29,36,47,50,72,73,74}}
{105,8,{19,29,36,47,50,72,73,74}}