Problem

Source: 2015 Taiwan TST Round 3 Quiz 2 Problem 2

Tags: Taiwan, number theory, Taiwan TST 2015



Consider the permutation of $1,2,...,n$, which we denote as $\{a_1,a_2,...,a_n\}$. Let $f(n)$ be the number of these permutations satisfying the following conditions: (1)$a_1=1$ (2)$|a_i-a_{i-1}|\le2, i=1,2,...,n-1$ what is the residue when we divide $f(2015)$ by $4$ ?