数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 266|回复: 30

给出正整数列 a1,a2,…,a18=2020 使得对 3≤k≤18 均有 1≤i<j<k 使得 ak=ai+aj

[复制链接]
发表于 2021-1-12 10:25 | 显示全部楼层 |阅读模式
求解答及思考方法, 谢谢

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
发表于 2021-1-12 14:10 | 显示全部楼层
其中的一种解法是(可能不唯一):
1    2     3    4     5    6     7      8       9      10      11      12     13     14      15     16        17       18
1, 2, 3, 4, 6, 7, 13, 20, 27,  47,  67, 114,181,295,476,771,1247, 2018

其中:  
a3 = a1+a2
a4 = a1+a3
a5 = a2+a4
a6 = a3+a4
a7 = a5+a6
a8 = a6+a7
a9 = a6+a8
a10=a8+a9
a11=a8+a10
a12=a11+a10
a13=a12+a11
a14=a13+a12
a15=a14+a13
a16=a15+a14
a17=a16+a15
a18=a17+a16
回复 支持 1 反对 0

使用道具 举报

发表于 2021-1-12 18:13 | 显示全部楼层
楼上 uk702 的解答很好!已收藏。
回复 支持 反对

使用道具 举报

发表于 2021-1-12 19:24 | 显示全部楼层
本帖最后由 uk702 于 2021-1-12 19:28 编辑

现考虑一般情况,继续求解。

容易验证,
当 n=3 时,a3 只能等于3,它只有一个解:{1, 2, 3}
当 n=4 时,a4 可以取 3, 4, 5 计3个值,共有:{1,2,3,3}, {1,2,3,4}, {1,2, 3, 5} 三个解,并且无论 a4=3 还是 4 还是 5,每个值的解都是唯一的(只有唯一的路径)。
当 n=5 时,a5 可以取 3,4,5,6,7,8 计 5 个值,互不相同的解共有 15 个(见如下),而只有  a5=8 时它的解才是唯一的,其余 4 个值都有多个解(多条路径)。
k = 5, [1, 2, 3, 3, 3]
k = 5, [1, 2, 3, 3, 4]
k = 5, [1, 2, 3, 3, 5]
k = 5, [1, 2, 3, 3, 6]
k = 5, [1, 2, 3, 4, 3]
k = 5, [1, 2, 3, 4, 4]
k = 5, [1, 2, 3, 4, 5]
k = 5, [1, 2, 3, 4, 6]
k = 5, [1, 2, 3, 4, 7]
k = 5, [1, 2, 3, 5, 3]
k = 5, [1, 2, 3, 5, 4]
k = 5, [1, 2, 3, 5, 6]
k = 5, [1, 2, 3, 5, 5]
k = 5, [1, 2, 3, 5, 7]
k = 5, [1, 2, 3, 5, 8]

对于指定的 n,求如下几个问题的答案:
1)记 M1(n) 为最大的 an,求 M1(n),使得 an 有解;
2)假设 k 为 3 ≤ k ≤ M1(n) 的正整数,那么是否对于所有的 k,an = k 时都有解?
3)假如限制各 ai 严格递增,对于给定 n,求它的所有解的总数,如 n=3 时,1个解;n=4 时,2 个解( (1,2,3,4) 和 (1,2,3,5) );n=5 时,满足严格递增的解共 6 个:
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 6]
[1, 2, 3, 4, 7]
[1, 2, 3, 5, 6]
[1, 2, 3, 5, 7]
[1, 2, 3, 5, 8]
4)对于给定 n,求使得 an 有唯一解的个数,如 n=3 时,有 1 个 an(3)有唯一解;n=4 时,有 3 个 an(3,4,5) 有唯一解;n=5时,有一个 an(8) 有唯一解。
5)假设 k 满足 3 ≤ k ≤ M1(n) ,如果不是所有的 k 都有解,那么,哪些 an=k 时有解,是否有通式或判断方法?
6)假设 k 满足 3 ≤ k ≤ M1(n) ,并且 an=k 时只有唯一的解,这样的 an 是否有通式或判断方法?


最后是楼主的问题,当 n=18 时,an=2018,它的解是否是唯一的?

回复 支持 反对

使用道具 举报

发表于 2021-1-12 21:36 | 显示全部楼层
本帖最后由 uk702 于 2021-1-12 21:43 编辑

经编程搜索,a18=2018 共有 2612 个严格递增的解, a18=2021 也有 2387 个解。


下面是 2018 的前 10 个解和后10个解:
k = 18, [1, 2, 3, 5, 6, 7, 13, 20, 27, 47, 67, 114, 181, 295, 476, 771, 1247, 2018]
k = 18, [1, 2, 3, 5, 6, 8, 14, 20, 34, 54, 68, 122, 176, 298, 474, 772, 1246, 2018]
k = 18, [1, 2, 3, 5, 6, 8, 14, 20, 34, 54, 88, 122, 176, 298, 474, 772, 1246, 2018]
k = 18, [1, 2, 3, 5, 6, 8, 14, 22, 30, 52, 82, 134, 216, 350, 484, 834, 1184, 2018]
k = 18, [1, 2, 3, 5, 6, 8, 14, 22, 36, 50, 86, 136, 186, 322, 458, 780, 1238, 2018]
k = 18, [1, 2, 3, 5, 6, 8, 14, 22, 36, 58, 94, 152, 246, 398, 412, 810, 1208, 2018]
k = 18, [1, 2, 3, 5, 6, 9, 14, 20, 34, 54, 68, 122, 176, 298, 474, 772, 1246, 2018]
k = 18, [1, 2, 3, 5, 6, 9, 14, 20, 34, 54, 88, 122, 176, 298, 474, 772, 1246, 2018]
k = 18, [1, 2, 3, 5, 6, 9, 14, 23, 28, 51, 74, 125, 199, 324, 523, 847, 1171, 2018]
k = 18, [1, 2, 3, 5, 6, 9, 14, 23, 37, 51, 74, 125, 199, 324, 523, 847, 1171, 2018]
...
k = 18, [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 398, 631, 1008, 1010, 2018]
k = 18, [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 398, 775, 1008, 1010, 2018]
k = 18, [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 432, 576, 1008, 1010, 2018]
k = 18, [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 466, 471, 937, 1081, 2018]
k = 18, [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 615, 704, 1314, 2018]
k = 18, [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 615, 992, 1026, 2018]
k = 18, [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 631, 1008, 1010, 2018]
k = 18, [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 699, 704, 1314, 2018]
k = 18, [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 992, 1026, 2018]
k = 18, [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1008, 1010, 2018]

a18=2021 有解如下:
k = 18, [1, 2, 3, 5, 6, 7, 12, 19, 25, 44, 69, 113, 182, 295, 477, 772, 1249, 2021]

点评

解的数量应该与“兔子数列”的差有关,会有规律来吗?  发表于 2021-1-14 19:12

评分

参与人数 1威望 +15 收起 理由
王守恩 + 15 洗耳恭听!

查看全部评分

回复 支持 反对

使用道具 举报

发表于 2021-1-13 18:25 | 显示全部楼层
本帖最后由 王守恩 于 2021-1-13 18:26 编辑
uk702 发表于 2021-1-12 21:36
经编程搜索,a18=2018 共有 2612 个严格递增的解, a18=2021 也有 2387 个解。


uk702!
此题与《正整数递增数列 {a(n)} 满足 a(n+2)=a(n+1)+a(n)(n≥1),已知 a(7)=120,求 a(8)》有联系吗?

点评

《正整数递增数列 {a(n)} 满足 a(n+2)=a(n+1)+a(n)(n≥1),已知 a(7)=120,求 a(8),也就是 tid=2043503 ,如果要正推,可根据 120*(sqrt(5)+1)/2 = 194 大致判断出来。  发表于 2021-1-13 19:30
这么说吧,显然 an 的最大值 M1(n) 满足 M1(n+1) = M1(n) + M1(n-1) 这个关系, 当 an 越接近 M1(n),则其中的越多项必须满足 a(n+1) = a(n)+a(n-1) 的关系。  发表于 2021-1-13 19:28
回复 支持 反对

使用道具 举报

发表于 2021-1-14 19:46 | 显示全部楼层
本帖最后由 uk702 于 2021-1-14 21:54 编辑
王守恩 发表于 2021-1-13 18:25
uk702!
此题与《正整数递增数列 {a(n)} 满足 a(n+2)=a(n+1)+a(n)(n≥1),已知 a(7)=120,求 a(8)》有联 ...


#4 楼提的几个问题,
1)记 M1(n) 为最大的 an,求 M1(n),使得 an 有解;
这个问题很简单,也比较显然, an 的最大值 M1(n) 满足 M1(n+1) = M1(n) + M1(n-1) 这个关系。
M1(1)=1, M1(2)=2, M1(3)=3, M1(4)=5, M1(5)=8, M1(6)=13, M1(7)=21, M1(8)=34, M1(9)=55, ...

2)假设 k 为 3 ≤ k ≤ M1(n) 的正整数,那么是否对于所有的 k,an = k 时都有解?
这个问题经编程确认,n =3,4,5,6 时,对于满足 3 ≤ k ≤ M1(n) 的正整数,an =k 都有解,


n=7 时,这时 M1(n) = 21,对于满足 3 ≤ k ≤ M1(n) 的正整数,除了 k=20 外,其余的 an =k 都有解。
n=8 时,这时 M1(n) = 34,对于满足 3 ≤ k ≤ M1(n) 的正整数,除了 k=32,33 外,其余的 an =k 都有解。
n=9 时,这时 M1(n) = 55,对于满足 3 ≤ k ≤ M1(n) 的正整数,除了 k=48,51~54 外,其余的 an =k 都有解。

3)关于解的个数,如果只考虑严格递增的解,那么
n=4 时,an=4 和 5 各有 1 个解;
n=5 时,an=5 有1个解,an=6 和 7 有 2 个解,an=8 有 1 个解;
n=6 时,an=6 有1个解,7是3个解,8是5个解,9是6个解,10是4个解,11是3个解,12和13是1个解,呈现类似二项式分布的结构。

随着 n 的增大,总解的个数以远超指数的规模爆炸,可能堪比n^n 或者诸如 2^(1.618^n),爆炸速度绝不是兔子数列可以比的。

其它问题恐怕都不好回答。
回复 支持 反对

使用道具 举报

发表于 2021-1-14 19:55 | 显示全部楼层
对编程验证有兴趣的各位同学可参考如下 julia 代码。
  1. #http://www.mathchina.com/bbs/forum.php?mod=viewthread&tid=2044556&page=1&extra=#pid2395817
  2. a=[[1], [[1,2]], [[1,2,3]]]

  3. # 求各 ai 严格递增的解
  4. for k=4:18
  5.     t=k-1;
  6.     b=[];
  7.     for u=1:length(a[t])
  8.         mx = a[t][u][end]
  9.         for i=1:length(a[t][u])-1
  10.             for j=i+1:length(a[t][u])
  11.                 s = a[t][u][i] + a[t][u][j]; #println((a[t][u][i], a[t][u][j], s));
  12.                 if s > mx
  13.                     tp = copy(a[t][u]); tp = append!(tp, s); #println(tp);
  14.                     append!(b, [tp]); #println("b = $b");
  15.                 end   
  16.             end
  17.         end
  18.     end
  19.     b=unique(b)
  20.     append!(a, [b]);
  21.     for x in a[k]
  22.         println("k = $k, ", (x))
  23.     end
  24. end
复制代码
回复 支持 反对

使用道具 举报

发表于 2021-1-15 07:05 | 显示全部楼层
本帖最后由 uk702 于 2021-1-15 07:24 编辑

记 S(n) 为 k=n 时的最大解集的数量,则 \(S(n) = S(n-1)\frac{(n-1)(n-2)}{2}\),由此知有 \(S(n+1)=\frac{(n!)^{2}}{n2^n}\) >= \((\frac{n}{c_1})^{(2-)n}\)

若记 s(n) 为  k=n 时的严格递增解的数量,则 s(n) 显然要大大大小于 S(n),但猜测有 >= \((\frac{n}{c_2})^{cn}\),其中 c>1
回复 支持 反对

使用道具 举报

发表于 2021-1-17 09:26 | 显示全部楼层
本帖最后由 王守恩 于 2021-1-17 11:00 编辑
uk702 发表于 2021-1-15 07:05
记 S(n) 为 k=n 时的最大解集的数量,则 \(S(n) = S(n-1)\frac{(n-1)(n-2)}{2}\),由此知有 \(S(n+1)=\frac ...


uk702!8楼我不会用。这串数会长得不快吧?
记 F(n)=1, 2, 3, 5, 8, 13, 21, 34, 55, ......   
记 S(k) 为 k的最大解集的数量,我们约定:n< k的项数 ≤n+1。
k=01, 项数是1, S(01)=1  F(1)
k=02, 项数是2, S(02)=1  F(2)
k=03, 项数是3, S(03)=1  F(3)
k=04, 项数是4, S(04)=1
k=05, 项数是4, S(05)=1  F(4)
k=06, 项数是5, S(06)=2
k=07, 项数是5, S(07)=2
k=08, 项数是5, S(08)=1  F(5)
k=09, 项数是6, S(09)=6
k=10, 项数是6, S(10)=4
k=11, 项数是6, S(11)=3
k=12, 项数是6, S(12)=1
k=13, 项数是6, S(13)=1  F(6)
k=14, 项数是7, S(14)=1
k=15, 项数是7, S(15)=1
k=16, 项数是7, S(16)=1
k=17, 项数是7, S(17)=1
k=18, 项数是7, S(18)=1
k=19, 项数是7, S(19)=1
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2021-1-23 10:22 , Processed in 0.076172 second(s), 17 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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