CMO 1996 Problem 3

We denote an arbitrary permutation of the integers $1$ , $2$ , $\ldots$ , $n$ by $a_1$ , $a_2$ , $\ldots$ , $a_n$ . Let $f(n)$ denote the number of these permutations such that:

(1) $a_1 = 1$ ;

(2): $|a_i - a_{i+1}| \leq 2$ , $i = 1, \ldots, n - 1$ .

Determine whether $f(1996)$ is divisible by 3.