最小集合

aimisiyou

从1-100里选择K个不同的数，其中必然存在四个数满足a+b=c+d，则K最小为多少？根据鸽巢原理，分成（1234）（5678）……25组，每组取三个（共75个），再多取一个则必然存在a+b=c+d的情形，显然K=76是满足的但不是最小的。

aimisiyou

找到一个抽屉，(18 36 44 48 49 50 52 59 69 94)，再加一个数必然存在a+b=c+d，但不确定是不是最小的抽屉。

northwolves

似乎9个就够了：
{{10, 32, 42, 49, 51, 52, 53, 57, 83}, {10, 32, 42, 49, 51, 52, 53,  65, 83}, {10, 32, 42, 49, 51, 52, 57, 65, 83}, {10, 32, 42, 49, 51,  53, 57, 65, 83}, {10, 32, 42, 51, 52, 53, 57, 65, 83}, {10, 42, 49,  51, 52, 53, 57, 65, 83}}

northwolves

似乎8个就够了：
{{10,32,42,49,51,52,53,83},{10,32,42,49,51,52,57,83},{10,32,42,49,51,52,65,83},{10,32,42,49,51,53,57,83},{10,32,42,49,51,53,65,83},{10,32,42,49,51,57,65,83},{10,32,42,51,52,53,57,83},{10,32,42,51,52,53,65,83},{10,32,42,51,52,57,65,83},{10,32,42,51,53,57,65,83},{10,42,49,51,52,53,57,83},{10,42,49,51,52,53,65,83},{10,42,49,51,52,57,65,83},{10,42,49,51,53,57,65,83},{10,42,51,52,53,57,65,83}}

northwolves

似乎7个就够了：
{{10,32,42,49,51,52,83},{10,32,42,49,51,53,83},{10,32,42,49,51,57,83},{10,32,42,49,51,65,83},{10,32,42,51,52,53,83},{10,32,42,51,52,57,83},{10,32,42,51,52,65,83},{10,32,42,51,53,57,83},{10,32,42,51,53,65,83},{10,32,42,51,57,65,83},{10,42,49,51,52,53,83},{10,42,49,51,52,57,83},{10,42,49,51,52,65,83},{10,42,49,51,53,57,83},{10,42,49,51,53,65,83},{10,42,49,51,57,65,83},{10,42,51,52,53,57,83},{10,42,51,52,53,65,83},{10,42,51,52,57,65,83},{10,42,51,53,57,65,83}}

aimisiyou

northwolves 发表于 2025-11-25 12:35
似乎9个就够了：
{{10, 32, 42, 49, 51, 52, 53, 57, 83}, {10, 32, 42, 49, 51, 52, 53,  65, 83}, {10, 3 ...

(10 32 42 49 51 52 53 57 83)再加个97，仍不存在a+b=c+d.

northwolves

6个:{{10,32,42,49,51,83},{10,32,42,51,52,83},{10,32,42,51,53,83},{10,32,42,51,57,83},{10,32,42,51,65,83},{10,42,49,51,52,83},{10,42,49,51,53,83},{10,42,49,51,57,83},{10,42,49,51,65,83},{10,42,51,52,53,83},{10,42,51,52,57,83},{10,42,51,52,65,83},{10,42,51,53,57,83},{10,42,51,53,65,83},{10,42,51,57,65,83}}

5个：
{{10, 32, 42, 51, 83}, {10, 42, 49, 51, 83}, {10, 42, 51, 52, 83}, {10, 42, 51, 53, 83}, {10, 42, 51, 57, 83}, {10, 42, 51, 65, 83}}

aimisiyou

northwolves 发表于 2025-11-25 13:06
6个:{{10,32,42,49,51,83},{10,32,42,51,52,83},{10,32,42,51,53,83},{10,32,42,51,57,83},{10,32,42,51,65 ...

应该是1~N的Sidon集。

northwolves

从1-100里选择K个不同的数，其中不存在四个数满足a+b=c+d，则K最大为多少？

k=11:  {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 98} 满足条件，不知道是不是最大

aimisiyou

northwolves 发表于 2025-11-25 14:51
从1-100里选择K个不同的数，其中不存在四个数满足a+b=c+d，则K最大为多少？

不知道是不是等价的。我是想取最少个数构成初始集合，且不存在和相等的两组。然后若再加入任何一个数字，都必然存在a+b=c+d出现。