最小集合

northwolves

k=12: {1, 2, 3, 5, 8, 13, 21, 30, 39, 53, 74, 95}

northwolves

求{1, 2, ..., 100}没有等和对的最大子集

northwolves

k=13:  {1,2,12,18,22,35,43,58,61,73,80,85,87}

aimisiyou

northwolves 发表于 2025-11-25 16:25
k=13:  {1,2,12,18,22,35,43,58,61,73,80,85,87}

不是等价的。我找到了(18 36 44 48 49 50 52 59 69 94)，然后再加入一个数必然存在a+b=c+d.

aimisiyou

northwolves 发表于 2025-11-25 16:25
k=13:  {1,2,12,18,22,35,43,58,61,73,80,85,87}

K=9,(12 14 17 20 21 31 50 70 90)
K=9,(10 29 48 57 59 62 65 66 86)

aimisiyou

第2个例子给出的突破口似乎更多。能否找到K=8情形？

王守恩

从{1,2,3,4,...,n}里选择k个不同的数, 不存在等和对。若再加1个数(剩下数任选)则必有等和对。则k最小=__。——题目是这个？

王守恩

k=9,{1, 38, 48, 50, 57, 62, 65, 66, 100}——手工计算。有错吗？

王守恩

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

a(1)=1, {1},
a(2)=2, {1,2},
a(3)=3, {1,2,3},
a(4)=3, {1,2,3},
a(5)=3, {1,2,4},
a(6)=4, {1,2,3,5},
a(7)=4, {1,2,3,5},
a(8)=4, {1,2,3,6},
a(9)=4, {1,2,3,7},
a(10)=4, {1,2,4,7},
a(11)=4, {1,2,4,8},
a(12)=4, {1,2,4,9},
a(13)=4, {3,5,6,10},
a(14)=5, {1,2,3,5,10},
a(15)=5, {1,2,3,5,11},
a(16)=5, {1,2,3,5,12},
a(17)=5, {1,2,3,6,12},
a(18)=5, {1,2,3,6,13},
a(19)=5, {1,2,3,6,14},
a(20)=5, {1,2,4,6,15},
a(21)=5, {1,2,5,7,15},
a(22)=5, {1,3,4,8,17},
a(23)=5, {1,3,6,7,17},
a(24)=5, {2,4,7,8,18},
a(25)=5, {3,7,8,10,20},
别指望我——我来不了了。——手工计算错误难免。

aimisiyou

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

暴力总归不是那么省力……