3. Let $a_{1}, a_{2}, \cdots, a_{n}$ represent any permutation of the integers $1,2, \cdots, n$. Let $f(n)$ be the number of such permutations such that
(i) $a_{1}=1$;
(ii) $\left|a_{i}-a_{i+1}\right| \leqslant 2 . i=1,2, \cdots, n-1$.
Determine whether $f(1996)$ is divisible by 3.
3. Verify that $f(1)=f(2)=1$ and $f(3)=2$.

Let $n \geqslant 4$. Then it must be that $a_{1}=1, a_{2}=2$ or 3.
For $a_{2}=2$, the number of permutations is $f(n-1)$, because by deleting the first term and reducing all subsequent terms by 1, we can establish a one-to-one correspondence of sequences.

If $a_{2}=3$, then $a_{3}=2$. In this case, $a_{4}=4$, and the number of such permutations is $f(n-3)$.

If $a_{3} \neq 2$, then 2 must come after 4. This implies that all odd numbers are in ascending order and all even numbers are in descending order. Therefore, $f(n)=f(n-1)+f(n-3)+1$.

For $n \geqslant 1$, let $r(n)$ be the remainder when $f(n)$ is divided by 3. Then we have
$$
\begin{array}{l}
r(1)=r(2)=1, r(3)=2, \\
r(n)=r(n-1)+r(n-3)+1 .
\end{array}
$$

The sequence of remainders forms a periodic sequence with a period of 8:
$$
\{1,1,2,1,0,0,2,0\} \text {. }
$$

Since $1994=4(\bmod 8)$, and $r(4)=1$,
$f(1996)$ is not divisible by 3.