Question 30
We denote an arbitrary permutation of the integers $1, \ldots, n$ by $a_{1}, \ldots, a_{n}$. Let $f(n)$ be the number of these permutations such that
(i) $a_{1}=1$;
(ii) $|a_{i}-a_{i+1}| \leq 2, \quad i=1, \ldots, n-1$.
Determine whether $f(1996)$ is divisible by $3$.
(i) $a_{1}=1$;
(ii) $|a_{i}-a_{i+1}| \leq 2, \quad i=1, \ldots, n-1$.
Determine whether $f(1996)$ is divisible by $3$.