MathDB

We denote an arbitrary permutation of the integers

1

2

\ldots

n

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.

Problem Statement