IBM Ponder This #048 · 2002 年 4 月

本题根据 John G. Fletcher 的建议改编。给定较小的正整数 k 和较大的正整数 N，初始向量 (x(1),…,x(k)) 的各分量为 0 至 N 的整数。

每一步同时把各分量替换为它与右邻之差的绝对值，末尾与开头相邻：y(i)=|x(i)-x(i+1)|（i=1,…,k-1），y(k)=|x(k)-x(1)|，然后令 x(i)=y(i)。

如果存在整数 j，使所有分量都属于 {0,j}，就称该状态为终态，包括全零状态。从终态继续操作，仍然是同一个 j 对应的终态。每个初态在有限步后都会到达终态；首次到达所需步数称为其“寿命”。

例如，(8,9,2,6) 依次变为 (1,7,4,2)、(6,3,2,1)、(3,1,1,5)、(2,0,4,2)、(2,4,2,0)、(2,2,2,2)，所以寿命为 6。

第一部分：对 k=1,…,12 分别判断，是否存在只依赖于 k 的常数 c(k)>0 和 d(k)，使每个足够大的 N 都有一个初态，其寿命至少为 c(k)N-d(k)。给出哪些 k 可以、哪些不可以，并分别证明。c(k) 表示依赖于 k 的常数，而不是 c 与 k 的乘积。原题所举的 k 分类只是回答格式示例，不是提示答案。

第二部分：k=13 时结论如何？

解答

认真尝试后再打开

待补充。