整数列{x(n)}满足x(0)=2,|x(k)|=|x(k-1)+1| (k≥1). 求|x(1)+...+x(2019)|的最小值

王守恩

elim 发表于 2019-10-31 19:23
a(n) 是什么?, 递推公式验证到哪里了?

可以归到 “爬楼梯” 问题。
  a(3)=2，a(2)=1，a(1)=3
a(4)=Abs(a(3) - a(2) - a(1))
a(5)=Abs(a(4) - a(3) - a(2))
a(6)=Abs(a(5) - a(4) - a(3))
a(7)=Abs(a(6) - a(5) - a(4))
a(8)=Abs(a(7) - a(6) - a(5))
a(9)=Abs(a(8) - a(7) - a(6))

elim

王守恩 发表于 2019-10-31 04:34
可以归到 “爬楼梯” 问题。
  a(3)=2，a(2)=1，a(1)=3
a(4)=Abs(a(3) - a(2) - a(1))

你这个关系式很可能是对的. 或可从我得到的通项推出. 但从这个形式得到 a(n) 的计算量似乎还是要遍历它前面的所有a(k).

王守恩

elim 发表于 2019-10-31 21:04
你这个关系式很可能是对的. 或可从我得到的通项推出. 但从这个形式得到 a(n) 的计算量似乎还是要遍历它前 ...

谢谢elim！怎么来化简这通项公式？我想不出来了。

题: 整数列{x(n)}满足x(0)=2,|x(k)|=|x(k-1)+1| (k≥1). 求|x(1)+x(2)+...+x(2019)|的最小值
设S(n)=|x(1)+x(2)+...+x(n)|的最小值，n=1,2,3,4,......

S(n)=3, 1, 2, 2, 1, 3, 0, 4, 1, 3, 2, 2, 3,
         1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5,
         0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6,
         0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6,
         1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5,
         3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7, 3,
         6, 4, 5, 5, 4, 6, 3, 7, 2, 8, 1, 9, 0,
         ..........

特别地，S(2019)=44

elim

这个式子是怎么推导出来的？是观察总结的结果吗？

王守恩

elim 发表于 2019-11-1 08:59
这个式子是怎么推导出来的？是观察总结的结果吗？

式子是观察总结出来的，还可以利用下面的2个方法。

方法一： “爬楼梯” 函数
LinearRecurrence[{1, -1, -1}, {3, 1, 2}, 30]

方法二：特殊方程求解
RecurrenceTable[{a[1] == 3, a[2] == 1, a[3] == 2,
  a[n] == Abs[a[n - 1] - a[n - 2] - a[n - 3]]}, a, {n, 30}]

elim

后两个方法其实也还是基于观察猜想. 不过什么观察会导致 √(n+9) 这种东西呢?

王守恩

elim 发表于 2019-11-1 14:06
后两个方法其实也还是基于观察猜想. 不过什么观察会导致 √(n+9) 这种东西呢?

题: 整数列{x(n)}满足x(0)=A,|x(k)|=|x(k-1)+1| (k≥1). 求|x(1)+x(2)+...+x(2019)|的最小值
设S(n)=|x(1)+x(2)+...+x(n)|的最小值，n=1,2,3,4,......
任意一道题都要回到这2个公式上来。
第1个公式表示第 1 行或者第 1 列，
第2个公式表示第 m 行或者第 m 列，
譬如：主帖用的是第10行或者第10列，
a(00)=0, 1, 1, 0, 2, 1, 1, 2, 0, 3, 1, 2, 2, 1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0,
a(01)=1, 1, 0, 2, 1, 1, 2, 0, 3, 1, 2, 2, 1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5,
a(02)=1, 0, 2, 1, 1, 2, 0, 3, 1, 2, 2, 1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1,
a(03)=0, 2, 1, 1, 2, 0, 3, 1, 2, 2, 1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4,
a(04)=2, 1, 1, 2, 0, 3, 1, 2, 2, 1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2,
a(05)=1, 1, 2, 0, 3, 1, 2, 2, 1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3,
a(06)=1, 2, 0, 3, 1, 2, 2, 1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3,
a(07)=2, 0, 3, 1, 2, 2, 1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2,
a(08)=0, 3, 1, 2, 2, 1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4,
a(09)=3, 1, 2, 2, 1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1,
a(10)=1, 2, 2, 1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5,
a(11)=2, 2, 1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0,
a(12)=2, 1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6,
a(13)=1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1,
a(14)=3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5,
a(15)=0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2,
a(16)=4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4,
a(17)=1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4, 3,
a(18)=3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4, 3, 3,
a(19)=2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4, 3, 3, 4,
a(20)=2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4, 3, 3, 4, 2,
a(21)=3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5,
a(22)=1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1,
a(23)=4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6,
a(24)=0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0,
a(25)=5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7,
a(26)=1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1,
a(27)=4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6,
a(28)=2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2,
a(29)=3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5,
a(30)=3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3,
a(31)=2, 4, 1, 5, 0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4,
a(32)=4, 1, 5, 0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4,
a(33)=1, 5, 0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3,
a(34)=5, 0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5,
a(35)=0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2,
a(36)=6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6,
a(37)=1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1,
a(38)=5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7,
a(39)=2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0,
a(40)=4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8,
a(41)=3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 1,
a(42)=3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 1, 7,
a(43)=4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 1, 7, 2,
a(44)=2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 1, 7, 2, 6,
a(45)=5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 1, 7, 2, 6, 3,
a(46)=1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 1, 7, 2, 6, 3, 5,
a(47)=6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4,
a(48)=0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4,
a(49)=7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5,
a(50)=1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5, 3,
a(51)=6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5, 3, 6,
a(52)=2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5, 3, 6, 2,
a(53)=5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5, 3, 6, 2, 7,
a(54)=3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5, 3, 6, 2, 7, 1,
a(55)=4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5, 3, 6, 2, 7, 1, 8,
a(56)=4, 3, 5, 2, 6, 1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5, 3, 6, 2, 7, 1, 8, 0,
a(57)=3, 5, 2, 6, 1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5, 3, 6, 2, 7, 1, 8, 0, 9,
a(58)=5, 2, 6, 1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5, 3, 6, 2, 7, 1, 8, 0, 9, 1,
a(59)=2, 6, 1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5, 3, 6, 2, 7, 1, 8, 0, 9, 1, 8,
a(60)=6, 1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5, 3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2,
a(61)=1, 7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5, 3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7,
a(62)=7, 0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5, 3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7, 3,
a(63)=0, 8, 1, 7, 2, 6, 3, 5, 4, 4, 5, 3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7, 3, 6,
a(64)=8, 1, 7, 2, 6, 3, 5, 4, 4, 5, 3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7, 3, 6, 4,
a(65)=1, 7, 2, 6, 3, 5, 4, 4, 5, 3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7, 3, 6, 4, 5,
a(66)=7, 2, 6, 3, 5, 4, 4, 5, 3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7, 3, 6, 4, 5, 5,
a(67)=2, 6, 3, 5, 4, 4, 5, 3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7, 3, 6, 4, 5, 5, 4,
a(68)=6, 3, 5, 4, 4, 5, 3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7, 3, 6, 4, 5, 5, 4, 6,
a(69)=3, 5, 4, 4, 5, 3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7, 3, 6, 4, 5, 5, 4, 6, 3,
a(70)=5, 4, 4, 5, 3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7, 3, 6, 4, 5, 5, 4, 6, 3, 7,
a(71)=4, 4, 5, 3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7, 3, 6, 4, 5, 5, 4, 6, 3, 7, 2,
a(72)=4, 5, 3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7, 3, 6, 4, 5, 5, 4, 6, 3, 7, 2, 8,
a(73)=5, 3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7, 3, 6, 4, 5, 5, 4, 6, 3, 7, 2, 8, 1,
a(74)=3, 6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7, 3, 6, 4, 5, 5, 4, 6, 3, 7, 2, 8, 1, 9,
a(75)=6, 2, 7, 1, 8, 0, 9, 1, 8, 2, 7, 3, 6, 4, 5, 5, 4, 6, 3, 7, 2, 8, 1, 9, 0,

王守恩

elim 发表于 2019-11-1 14:06
后两个方法其实也还是基于观察猜想. 不过什么观察会导致 √(n+9) 这种东西呢?

题: 整数列{x(n)}满足x(0)=A,|x(k)|=|x(k-1)+1| (k≥1). 求|x(1)+x(2)+...+x(2019)|的最小值
设S(n)=|x(1)+x(2)+...+x(n)|的最小值，n=1,2,3,4,......
任意一道题都要回到这2个公式上来。
只要知道a(0)，答案就是唯一的了。

elim

王守恩 发表于 2019-11-1 12:52
题: 整数列{x(n)}满足x(0)=A,|x(k)|=|x(k-1)+1| (k≥1). 求|x(1)+x(2)+...+x(2019)|的最小值
设S(n)=|x( ...

这个大家都无异议. 你的帖子什么新的都没说.

王守恩

简单一点。x(1)=±A，S(n)=|x(1)+x(2)+...+x(n)|的最小值，