Problem 1788

Solution: We discuss below the recurrence for $f(n)$. Suppose $a_1, a_2, \dots, a_n$ satisfies the conditions of the problem; since $a_1 = 1$, we have $a_2 = 2$ or $3$.
(Case 1): $a_2 = 2$. Let $b_i = a_{i+1} - 1$, then $b_1, b_2, \dots, b_{n-1}$ satisfies the conditions of the problem, so the number of permutations in this case is $f(n-1)$.
(Case 2): $a_2 = 3$ and $a_3 = 2$, then we must have $a_4 = 4$. Consider $c_i = a_{i+3} - 3$, then $c_1, c_2, \dots, c_{n-3}$ satisfies the conditions of the problem, so the number of permutations in this case is $f(n-3)$.
(Case 3): $a_2 = 3$ and $a_3 \ge 4$. Suppose $a_{k+1}$ is the first even number to appear in this permutation. By condition 2, $a_1, a_2, \dots, a_k$ are $1, 3, 5, \dots, 2k-1$, and $a_{k+1} = 2k$ or $2k-2$.
(Case 3-1): $a_{k+1} = 2k$. By discussion, the only possibility is $a_{k+2}, a_{k+3}, \dots, a_n = 2k - 2, 2k-4, \dots, 2$.

(Case 3-2): $a_{k+1} = 2k - 2$. By discussion, the only possibility is $a_{k+2}, a_{k+3}, \cdots, a_n = 2k - 4, 2k - 6, \cdots, 2$.
Therefore, Case 3 has only one possibility: first arrange in increasing order all positive odd numbers $\le n$, then arrange in decreasing order all positive even numbers $\le n$.

Combining the above, we have
$$f(n) = f(n-1) + f(n-3) + 1.$$
Using this formula to compute, we find that the residues of $f(n)$ modulo 4, in order, are:
1, 1, 2, 0, 2, 1, 2, 1, 3, 2, 0, 0, 3, 0, 1, 1, 2, 0, 2, ...
which is a sequence with period 14. Also, 2015 = 143 $\times$ 14 + 13, so
$$f(2015) = f(13) = 3 \pmod{4}.$$