最小集合

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}}