数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【数学研究】 › 难题征解 › 求{1, 2, ..., 100}没有等和对的最大子集
1234下一页
返回列表 发新帖
查看: 702|回复: 40

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

[复制链接]
王守恩
发表于 2025-7-1 05:40:41 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要 登录 才可以下载或查看，没有账号？欢迎注册

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

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

实际上要的并不是各个最大子集，而是最大子集的长度值，这才是唯一的。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复

使用道具 举报

王守恩
 楼主| 发表于 2025-7-1 09:37:01 | 显示全部楼层
且记最大子集的长度为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
发表于 2025-7-1 13:33:31 | 显示全部楼层
这个序列可以简并压缩，通过提取其中相同长度的项数。如果2楼的结果是正确的，那么这个序列就是
1, 1, 2, 3, 5, 8, 9, 9, ...

评分

参与人数 1威望 +36 金币 +36 贡献 +36 经验 +36 鲜花 +36 收起 理由
王守恩 + 36 + 36 + 36 + 36 + 36 高人！！！

查看全部评分

毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

王守恩
 楼主| 发表于 2025-7-1 14:02:36 | 显示全部楼层
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)是单调递增的，不可能出现波动。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

王守恩
 楼主| 发表于 2025-7-2 07:31:07 | 显示全部楼层
我们把{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 10:24:48 | 显示全部楼层
王守恩 发表于 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
发表于 2025-7-2 10:29:42 | 显示全部楼层
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#中所说的那个简并序列。这个序列不是递增的，有点出乎意料。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

王守恩
 楼主| 发表于 2025-7-2 10:42:05 | 显示全部楼层
题目是 aimisiyou的——从1~100中至少选出多少个不同的数，必然存在四个不同的数，满足a+b=c+d?
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

王守恩
 楼主| 发表于 2025-7-2 18:54:31 | 显示全部楼层
备忘——记录一下手工解题的过程。

求{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
发表于 2025-7-3 15:47:00 | 显示全部楼层
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

点评

hujunhua
3与2对称，4与1对称  发表于 2025-7-3 21:35

评分

参与人数 2威望 +12 金币 +16 贡献 +12 经验 +12 鲜花 +12 收起 理由
王守恩 + 6 + 8 + 6 + 6 + 6 “19”好不容易才出来。
hujunhua + 6 + 8 + 6 + 6 + 6 很给力!

查看全部评分

毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

1234下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2025-7-21 14:14 , Processed in 0.028425 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2025 Discuz! Team.

快速回复 返回顶部 返回列表