设 $a_1,a_2,\cdots,a_n$ 是整数 $1,2,\cdots ,n$ 的一个排列，且满足 ① $a_1=1$；② $|a_i-a_{i-1}|\leqslant 2$，$i=2,3,\cdots,n$．上述排列的个数记为 $f(n)$，试求 $f(2010)$ 被 $3$ 除的余数．
【难度】
【出处】
2010年湖南省高中数学竞赛
【标注】
【答案】
$1$
【解析】
可验证 $f(1)=1$，$f(2)=1$，$f(3)=2$，设 $n\geqslant 4$，则一定有 $a_1=1$，$a_2=2$ 或 $3$．
对于 $a_2=2$，排列数是 $f(n-1)$，这是因为通过删除第一项，且以后所有项都减 $1$，我们可以建立一一对应的数列．
对于 $a_2=3$，若有 $a_3=2$，则 $a_4=4$．这样排列数为 $f(n-3)$，若 $a_3\ne 2$，则 $2$ 一定排在 $4$ 的后面，由此得出所有奇数顺序排列的后面是所有偶数的倒序排列，因此$$f(n)=f(n-1)+f(n-3)+1.$$设 $r(n)$ 是 $f(n)$ 除以 $3$ 的余数，则 $r(1)=r(2)=1$，$r(3)=2$；
当 $n\geqslant 4$ 时，$$r(n)\equiv [r(n-1)+r(n-3)+1](\mod 3).$$由此得出 $\{r(n)\}$ 构成周期为 $8$ 的数列：$1,1,2,1,0,0,2,0,\cdots $
因为 $2010\equiv 2(\mod 8)$，所有 $r(2010)=1$，即 $f(2010)$ 被 $3$ 整除的余数为 $1$．
对于 $a_2=2$，排列数是 $f(n-1)$，这是因为通过删除第一项，且以后所有项都减 $1$，我们可以建立一一对应的数列．
对于 $a_2=3$，若有 $a_3=2$，则 $a_4=4$．这样排列数为 $f(n-3)$，若 $a_3\ne 2$，则 $2$ 一定排在 $4$ 的后面，由此得出所有奇数顺序排列的后面是所有偶数的倒序排列，因此$$f(n)=f(n-1)+f(n-3)+1.$$设 $r(n)$ 是 $f(n)$ 除以 $3$ 的余数，则 $r(1)=r(2)=1$，$r(3)=2$；
当 $n\geqslant 4$ 时，$$r(n)\equiv [r(n-1)+r(n-3)+1](\mod 3).$$由此得出 $\{r(n)\}$ 构成周期为 $8$ 的数列：$1,1,2,1,0,0,2,0,\cdots $
因为 $2010\equiv 2(\mod 8)$，所有 $r(2010)=1$，即 $f(2010)$ 被 $3$ 整除的余数为 $1$．
答案
解析
备注
