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

kids20082008

求解答及思考方法, 谢谢

uk702

其中的一种解法是（可能不唯一）：
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

luyuanhong

楼上 uk702 的解答很好！已收藏。

uk702

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

容易验证，
当 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，它的解是否是唯一的？

uk702

经编程搜索，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]

王守恩

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)》有联系吗？

uk702

王守恩 发表于 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)，爆炸速度绝不是兔子数列可以比的。

其它问题恐怕都不好回答。

uk702

对编程验证有兴趣的各位同学可参考如下 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. 
   
4. # 求各 ai 严格递增的解
   
5. for k=4:18
   
6.     t=k-1;
   
7.     b=[];
   
8.     for u=1:length(a[t])
   
9.         mx = a[t][u][end]
   
10.         for i=1:length(a[t][u])-1
    
11.             for j=i+1:length(a[t][u])
    
12.                 s = a[t][u][i] + a[t][u][j]; #println((a[t][u][i], a[t][u][j], s));
    
13.                 if s > mx
    
14.                     tp = copy(a[t][u]); tp = append!(tp, s); #println(tp);
    
15.                     append!(b, [tp]); #println("b = $b");
    
16.                 end   
    
17.             end
    
18.         end
    
19.     end
    
20.     b=unique(b)
    
21.     append!(a, [b]);
    
22.     for x in a[k]
    
23.         println("k = $k, ", (x))
    
24.     end
    
25. end
    

复制代码

uk702

记 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

王守恩

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