2010 年湖南预赛 · 第 18 题

解答

显然 $f(1)=1,f(2)=1,f(3)=2$。当 $n\ge 4$，第二项只能为二或三。第二项二时，删去首项一并将其余数减一，得到 $f(n-1)$ 种。第二项三、第三项二时，第四项只能四；删去前三项并平移其余数，得到 $f(n-3)$ 种。 若第二项三但第三项不为二，二以后只有四能接入，且接入后不能再离开，所以二必为末项。这类排列恰有一种。为说明唯一性，考虑同样步长限制下，从最小数一走遍一至 $r$ 并以二结束的排列。$r\ge 3$ 时首步只能到三；删一后反转排列再全减一，就变为规模 $r-1$ 的同一问题，规模二只有一种，故归纳得一直唯一。 因此

令 $g(n)=f(n)+1$，模三满足 $g(n)=g(n-1)+g(n-3)$，初态为 $(2,2,0)$。前八项余数为

接着三项重新为 $2,2,0$。完整三项状态已回返，后续由递推唯一确定，所以八为一个周期。$2010\equiv 2(\mathrm{mod}8)$，得 $g(2010)\equiv 2$，所以 $\boxed{f(2010)\equiv 1(\mathrm{mod}3)}$。