求{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}, ... 这个序列可以简并压缩，通过提取其中相同长度的项数。如果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没有通项公式——我来补一个——虽然很丑。
seq = {0};pairSums = {};nextTerm = 1;pairSumsUpdate := JoinhasDuplicates := !
DuplicateFreeQDo;pairSums = pairSumsUpdate;AppendTo;, 50]seq + 1 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, ......
这个通项公式也可以。
t = {1}; k = 1; sms = {}; Do != {}, k++]; sms = Join; AppendTo, {50}]; t
又：{1, 2, ..., n}没有等和对的最大子集a(k)可以有很多数字串——只要把这个"A"换一下就行。
t = {1}; k = 1; sms = {}; Do != {}, k++]; sms = Join; AppendTo, {50}]; t 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
页:
[1]
2