aimisiyou 发表于 4 天前

最小集合

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

aimisiyou 发表于 3 天前

本帖最后由 aimisiyou 于 2025-11-25 16:57 编辑

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

northwolves 发表于 3 天前

似乎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 发表于 3 天前

似乎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 发表于 3 天前

似乎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 发表于 3 天前

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 发表于 3 天前

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 发表于 3 天前

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 发表于 3 天前

本帖最后由 northwolves 于 2025-11-25 14:56 编辑

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

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

aimisiyou 发表于 3 天前

本帖最后由 aimisiyou 于 2025-11-25 15:03 编辑

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

不知道是不是等价的。我是想取最少个数构成初始集合，且不存在和相等的两组。然后若再加入任何一个数字，都必然存在a+b=c+d出现。
页: [1] 2 3
查看完整版本: 最小集合