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

王守恩

求{1, 2, ..., 100}的最大子集，使得没有等和2元子集。

比如子集{1,2,4,8,16,32,64}的C(7,2)=21个2元子集，各子集的和显然两两不等。但这不一定是长度最大的子集。

实际上要的并不是各个最大子集，而是最大子集的长度值，这才是唯一的。

王守恩

且记最大子集的长度为a(100), 不过100的规模太大了, 先从小数试起。
a(1)=1
a(2)=2
a(3)=3
a(4)=3
a(5)=4, {5,4,3,1}, {5,3,2,1}
a(6)=4, {6,5,4,2}, {6,4,3,2}, {6,5,4,1}
a(7)=4, {7,6,5,3}, ...
a(8)=5, {8,7,6,4,1}, ...
a(9)=5, {9,8,7,5,2}, ...
a(10)=5, {10,9,8,6,3}, ...
a(11)=5, {11,10,9,7,4}, ...
a(12)=5, {12,11,10,8,5}, ...
a(13)=6, {13,12,11,9,6,1}, ...
a(14)=6, {14,13,12,10,7,2}, ...
a(15)=6, {15,14,13,11,8,3}, ...
a(16)=6, {16,15,14,12,9,4}, ...
a(17)=6, {17,16,15,13,10,5}, ...
a(18)=6, {18,17,16,14,11,6}, ...
a(19)=6, {19,18,17,15,12,7}, ...
a(20)=6, {20,19,18,16,13,8}, ...
a(21)=7, {21,20,19,17,14,9,1}, ...
a(22)=7, {22,21,20,18,15,10,2}, ...
a(23)=7, {23,22,21,19,16,11,3}, ...
a(24)=7, {24,23,22,20,17,12,4}, ...
a(25)=7, {25,24,23,21,18,13,5}, ...
a(26)=7, {26,25,24,22,19,14,6}, ...
a(27)=7, {27,26,25,23,20,15,7}, ...
a(28)=7, {28,27,26,24,21,16,8}, ...
a(29)=7, {29,28,27,25,22,17,9}, ...
a(30)=8, {30,29,28,26,23,18,10,1}, ...
a(31)=8, {31,30,29,27,24,19,11,2}, ...
a(32)=8, {32,31,30,28,25,20,12,3}, ...
a(33)=8, {33,32,31,29,26,21,13,4}, ...
a(34)=8, {34,33,32,30,27,22,14,5}, ...
a(35)=8, {35,34,33,31,28,23,15,6}, ...
a(36)=8, {36,35,34,32,29,24,16,7}, ...
a(37)=8, {37,36,35,33,30,25,17,8}, ...
a(38)=8, {38,37,36,34,31,26,18,9}, ...
a(39)=9, {39,38,37,35,32,27,19,10}, ...
a(40)=9, {39,38,37,35,32,27,19,10}, ...

hujunhua

这个序列可以简并压缩，通过提取其中相同长度的项数。如果2楼的结果是正确的，那么这个序列就是
1, 1, 2, 3, 5, 8, 9, 9, ...

王守恩

A260998: Maximal size of a subset of Z_n with distinct sums of pairs (of distinct elements).

1, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10

有点相似但又不同。可能它的 Z_n 是同余系？

特别是它的序列还出现一处小小的波动 8, 7, 8, 好奇怪哦。看了列出的前254项，坡处都有小波动。

按我们的定义，a(n)是单调递增的，不可能出现波动。

王守恩

我们把{1,2,3,...,100}前移变为{0,1,2,...,99}, 将2#中的最大子集改为它的对称集，排算到100，结果如下：

a(4)=         3,         {0,1,2},
a(5)=         4,         {0,1,2,4},
a(6)=         4,         {0,1,2,4},
a(7)=         4,         {0,1,2,4},
a(8)=         5,         {0,1,2,4,7},
a(9)=         5,         {0,1,2,4,7},
a(10)=        5,        {0,1,2,4,7},
a(11)=        5,        {0,1,2,4,7},
a(12)=        5,        {0,1,2,4,7},
a(13)=        6,        {0,1,2,4,7,12},
a(14)=        6,        {0,1,2,4,7,12},
a(15)=        6,        {0,1,2,4,7,12},
a(16)=        6,        {0,1,2,4,7,12},
a(17)=        6,        {0,1,2,4,7,12},
a(18)=        6,        {0,1,2,4,7,12},
a(19)=        6,        {0,1,2,4,7,12},
a(20)=        6,        {0,1,2,4,7,12},
a(21)=        7,        {0,1,2,4,7,12,20},
a(22)=        7,        {0,1,2,4,7,12,20},
a(23)=        7,        {0,1,2,4,7,12,20},
a(24)=        7,        {0,1,2,4,7,12,20},
a(25)=        7,        {0,1,2,4,7,12,20},
a(26)=        7,        {0,1,2,4,7,12,20},
a(27)=        7,        {0,1,2,4,7,12,20},
a(28)=        7,        {0,1,2,4,7,12,20},
a(29)=        7,        {0,1,2,4,7,12,20},
a(30)=        8,        {0,1,2,4,7,12,20,29},
a(31)=        8,        {0,1,2,4,7,12,20,29},
a(32)=        8,        {0,1,2,4,7,12,20,29},
a(33)=        8,        {0,1,2,4,7,12,20,29},
a(34)=        8,        {0,1,2,4,7,12,20,29},
a(35)=        8,        {0,1,2,4,7,12,20,29},
a(36)=        8,        {0,1,2,4,7,12,20,29},
a(37)=        8,        {0,1,2,4,7,12,20,29},
a(38)=        8,        {0,1,2,4,7,12,20,29},
a(39)=        9,        {0,1,2,4,7,12,20,29,38},
a(40)=        9,        {0,1,2,4,7,12,20,29,38},
a(41)=        9,        {0,1,2,4,7,12,20,29,38},
a(42)=        9,        {0,1,2,4,7,12,20,29,38},
a(43)=        9,        {0,1,2,4,7,12,20,29,38},
a(44)=        9,        {0,1,2,4,7,12,20,29,38},
a(45)=        9,        {0,1,2,4,7,12,20,29,38},
a(46)=        9,        {0,1,2,4,7,12,20,29,38},
a(47)=        9,        {0,1,2,4,7,12,20,29,38},
a(48)=        9,        {0,1,2,4,7,12,20,29,38},
a(49)=        9,        {0,1,2,4,7,2,20,29,38},
a(50)=        9,        {0,1,2,4,7,12,20,29,38},
a(51)=        9,        {0,1,2,4,7,12,20,29,38},
a(52)=        9,        {0,1,2,4,7,12,20,29,38},
a(53)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(54)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(55)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(56)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(57)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(58)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(59)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(60)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(61)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(62)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(63)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(64)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(65)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(66)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(67)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(68)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(69)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(70)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(71)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(72)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(73)=        10,        {0,1,2,4,7,12,20,29,38,52},
a(74)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(75)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(76)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(77)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(78)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(79)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(80)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(81)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(82)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(83)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(84)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(85)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(86)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(87)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(88)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(89)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(90)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(91)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(92)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(93)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(94)=        11,        {0,1,2,4,7,12,20,29,38,52,73},
a(95)=        12,        {0,1,2,4,7,12,20,29,38,52,73,94},
a(96)=        12,        {0,1,2,4,7,12,20,29,38,52,73,94},
a(97)=        12,        {0,1,2,4,7,12,20,29,38,52,73,94},
a(98)=        12,        {0,1,2,4,7,12,20,29,38,52,73,94},
a(99)=        12,        {0,1,2,4,7,12,20,29,38,52,73,94},
a(100)=        12,        {0,1,2,4,7,12,20,29,38,52,73,94}

找到A010672：A B_2 sequence: a(n) = least value such that the sequence increases and pairwise sums of distinct terms are all distinct.
0, 1, 2, 4, 7, 12, 20, 29, 38, 52, 73, 94, 127, 151, 181, 211, 257, 315, 373, 412, 475, 530, 545, 607, 716, 797, 861, 964, 1059, 1160, 1306, 1385, 1434, 1555, 1721, 1833, 1933, 2057, 2260, 2496, 2698, 2873, 3060, 3196, 3331, 3628, 3711, 3867, 4139, 4446, 4639

王守恩

王守恩 发表于 2025-7-2 07:31
我们把{1,2,3,...,100}前移变为{0,1,2,...,99}, 将2#中的最大子集改为它的对称集，排算到100，结果如下：

...

如果保持{1, 2, 3, ..., 100}, 不把首数前移为0，那么对应的序列为A011185：

{1, 2, 3, 5, 8, 13, 21, 30, 39, 53, 74, 95, 128, 152, 182, 212, 258, 316, 374, 413, 476, 531, 546, 608, 717, 798, 862, 965, 1060, 1161, 1307, 1386, 1435, 1556, 1722, 1834, 1934, 2058, 2261, 2497, 2699, 2874, 3061, 3197, 3332, 3629, 3712,...}

A011185没有通项公式——我来补一个——虽然很丑。

1. seq = {0};pairSums = {};nextTerm = 1;pairSumsUpdate := Join[pairSums, nextTerm + seq]hasDuplicates := !
   
2. DuplicateFreeQ[pairSumsUpdate]Do[While[hasDuplicates, nextTerm++];pairSums = pairSumsUpdate;AppendTo[seq, nextTerm];, 50]seq + 1

复制代码

hujunhua

A010672的差分
1, 1, 2, 3, 5, 8, 9, 9, 14, 21, 21, 33, 24, 30, 30, 46, 58, 58, 39, 63, 55, 15, 62, 109, 81, 64, 103, 95, 101, 146, 79, 49, 121, 166, 112, 100, 124, 203, 236, 202, 175, 187, 136, 135, 297, 83, 156, 272, 307, 193
即3#中所说的那个简并序列。这个序列不是递增的，有点出乎意料。

王守恩

题目是 aimisiyou的——从1~100中至少选出多少个不同的数，必然存在四个不同的数，满足a+b=c+d?

王守恩

备忘——记录一下手工解题的过程。

求{1, 2, ..., n}没有等和对的最大子集a(k),  n>3。

a(3)=3, {1,2,3}——每次只要关注末尾2个数之间数是否有解就可以了。譬如:
a(4)=5, {1,2,3,5}——3,5之间有4——1,2,3,4有解。
a(5)=8, {1,2,3,5,8}——5,8之间有6,7——1,2,3,5,6-1,2,3,5,7有解。
a(6)=13, {1,2,3,5,8,13}——8,13之间有9,10,11,12——1,2,3,5,8,9-1,2,3,5,8,12有解。
a(7)=21, {1,2,3,5,8,13,21}——13,21之间有14-20——1,2,3,5,8,13,14-1,2,3,5,8,13,20有解。
a(8)=30, {1,2,3,5,8,13,21,30}——21,30之间有22-29——1,2,3,5,8,13,21,22-1,2,3,5,8,13,21,29有解。
a(9)=39, {1,2,3,5,8,13,21,30,39}——30,39之间有31-38——1,2,3,5,8,13,21,30,31-1,2,3,5,8,13,21,38有解。
a(10)=53, {1,2,3,5,8,13,21,30,39,53}
a(11)=74, {1,2,3,5,8,13,21,30,39,53,74},
a(12)=95, {1,2,3,5,8,13,21,30,39,53,74,95},

得到——A011185——1, 2, 3, 5, 8, 13, 21, 30, 39, 53, 74, 95, 128, 152, 182, 212, 258, 316, 374, 413, 476, 531, 546, 608, 717, 798, 862, 965, 1060, 1161, 1307, 1386, 1435, 1556, 1722, 1834, 1934, 2058, ......

这个通项公式也可以。

1. t = {1}; k = 1; sms = {}; Do[k++; While[Intersection[sms, t + k] != {}, k++]; sms = Join[sms, t + k, {k}]; AppendTo[t, k], {50}]; t

复制代码

又：{1, 2, ..., n}没有等和对的最大子集a(k)可以有很多数字串——只要把这个"A"换一下就行。

1. t = {1}; k = 1; sms = {}; Do[k++; While[Intersection[sms, t + k] != {}, k++]; sms = Join[sms, t + k, {A*k}]; AppendTo[t, k], {50}]; t

复制代码

mathe

Depth:7
1 2 3 5 9 14 19
Depth:7
1 2 3 8 11 15 19
Depth:7
1 5 9 12 17 18 19
Depth:7
1 6 11 15 17 18 19