MathDB

Modlova 3rd tst, problem 4

Source: Moldova TST III

March 26, 2006

combinatorics proposedcombinatorics

Problem Statement

Let

f(n)

denote the number of permutations

(a_{1}, a_{2}, \ldots ,a_{n})

of the set

\{1,2,\ldots,n\}

, which satisfy the conditions:

a_{1}=1

and

|a_{i}-a_{i+1}|\leq2

, for any

i=1,2,\ldots,n-1

. Prove that

f(2006)

is divisible by 3.

Back to Problems View on AoPS