绝对值数列最大值问题

anonymous

求正整数m的最大值，使得存在各项都不大于2018的正整数数列a(1),a(2), ..., a(m)满足对任意的3≤m≤n，都有a(n)=|a(n-1)-a(n-2)|。

把2018改成小一点的数，比如3,4,5,6,7, 对应的最大值
3，6
4,  7
5,  9
6,  10
7,  12
感觉规律不明显

mathe

你好像少算了一项
3 4 1 3 2 1 1
4 5 1 4 3 2 1 1
5 6 1 5 4 1 3 2 1 1
6 7 1 6 5 1 4 3 1 2 1 1
7 8 1 7 6 1 5 4 1 3 2 1 1

mathe

根据上面规律，要求所有数据不超过n,那么长度最长的序列要从n-1,n开始。
n为偶数时，长度为(3n+2)/2,n为奇数时，长度为(3n+1)/2. 可以统一写成\(\lfloor\frac{3n+2}2\rfloor\)

mathe

我们如果总是查看两个相邻的数对的变化，也就是看$(a_{k-1},a_k)\to(a_k,a_{k+1})$的变化
我们证明如下的结论，
  对于一个数对$(a,b)$,其中$a\neq b$而且$a\ge 3,b\ge 3$, 那么除了$(b-1,b)$以外，所有的数对最多变化三次，使得$\max{a,b}$至少减2.
可以分类证明
i) $2\le b\le a-2$, 于是经过一轮变换$(a,b)\to(b,a-b)$,使得最大值从a变化为$max{b,a-b}\le a-2$
ii)$(a,1)\to (1,a-1) \to (a-1,a-2)\to (a-2,1)$正好经过三轮变换，最大值减2.
iii) $(a,a-1)\to(a-1,1)\to (1,a-2)$, 经过两轮，最大值减2
iv) $b\ge 2a\ge 2$, $(a,b)\to (b,b-a)\to (b-a,a)$
v) $(1,b)\to(b,b-1)\to(b-1,1)\to(1,b-2)$正好3轮最大值减2
vi) $1\lt a\lt b-1$, $(a,b)\to (b,b-a)\to (b-a,a)$两轮最大值至少减2

mathe

现在我们再查看三步以内会变换到(b-1,b)而且最大值不小于3的状态的情况，只有
$(3b-1,b)\to(b,2b-1)\to(2b-1,b-1)\to(b-1,b)$
$(b-1,3b-2)\to(3b-2,2b-1)\to(2b-1,b-1)\to(b-1,b)$
$(5b-3,3b-2)\to(3b-2,2b-1)\to(2b-1,b-1)\to(b-1,b)$
其中$(5b-3,3b-2)\to(3b-2,2b-1)$已经至少减少2了，同样$(3b-2,2b-1)\to(2b-1,b-1)$在$b\ge3$时也至少减少2,都不会达到(b-1,b)状态就提前结束，可以不予讨论
而b=2时$(3b-2,2b-1)=(4,3)\to(3,1)\to(1,2)$,两轮到达(1,2)
同样(b-1,3b-2)出发时$b\ge 3$也提前终止，我们只需要考虑b=2的情况，对应$(1,4)\to(4,3)\to(3,1)\to(1,2)\to(2,1)\to(1,1)$是最大值为4时一个特殊的最长序列。
同样$(3b-1,b)\to(b,2b-1)$也提前终止。
所以实际上除了特例$(1,4)\to(4,3)\to(3,1)\to(1,2)\to(2,1)\to(1,1)$我们只需要再分析
$(b,2b-1)\to(2b-1,b-1)\to(b-1,b)$
$(2b-1,b-1)\to(b-1,b)$
这两种情况，它们都最多经过两步，而后面会继续跟上$(b-1,b)\to(b,1)\to(1,b-1)\to(b-1,b-2)\to(b-2,1)$,所以最多再经过四步后最大值减2,而且必然状态不是(b-1,b)形
所以我们得出除了特例$(1,4)\to(4,3)\to(3,1)\to(1,2)\to(2,1)\to(1,1)$（正好是最大值是4的另外一组最优结果，也只有最大值是4有两种最优结果）
那么最大值不小于3的任何初始状态，除了形如(b-1,b)的初始状态以外，要么三步内最大值减2，要么六步以内最大值减4.而且目的状态不是(b-1,b)形。
而(b-1,b)经过四步转化为(b-2,1)，同样目的状态不是(b-1,b)形。
由此可以总结出3#提到的长度已经是最优的了。