How Many Good Permutations?

Let $E_k$ denote the number of good permutations of $(a_1, a_2, \cdots , a_k).$

Claim: $E_{k+1} = 2 E_k \quad \forall \ k \in \mathbb{N_{\geq 3}}$

Proof: Let $(a_1, a_2, \cdots , a_k, a_{k+1})$ be any good permutation of $(1, 2, \cdots , k).$ Note that $\begin{array}{lcl} k \mid 2(a_1 + a_2 + \cdots + a_k) & \implies & k \mid 2(a_1 + a_2 + \cdots + a_{k+1} ) - 2a_{k+1} \\ & \implies & k \mid 2(1+2 + \cdots + (k+1)) - 2 a_{k+1} \\ & \implies & k \mid (k+1)(k+2) - 2 a_{k+1} . \end{array}$ But, $(k+1)(k+2) - 2 a_{k+1} \equiv 1 \cdot 2 = 2 a_{k+1} \equiv 2 (1 - a_{k+1}) \pmod{k},$ so $2(a_{k+1}-1)$ must be a multiple of $k.$ Thus, $a_{k+1}$ is either $1, \dfrac{k+2}{2},$ or $k+1$ .

I claim $a_{k+1} \neq \dfrac{k+1}{2}.$ Assume the contrary. Note that $\begin{array}{c}2(a_1 + a_2 + \cdots + a_{k-1}) & = & 2(a_1 + a_2 + \cdots + a_{k+1}) - 2a_k -2 a_{k+1} \\ & = & 2(1 + 2 + \cdots + (k+1)) - 2a_k - (k+2) \\ & = & (k+1)(k+2) - (k+2) - 2 a_k \\ & \equiv & 1 - 2 a_k \pmod{k}. \end{array}$ Thus, $2a_k - 1$ must be a multiple of $k,$ so $a_k = \dfrac{k+2}{2}.$ But this implies $a_k = a_{k+1},$ contradiction.

Thus, $a_{k+1}$ is either $k+1$ or $1.$ We have $E_k$ good permutations of $(1, 2, \cdots , k+1)$ where $a_{k+1}= k+1.$ We also have $E_k$ good permutations of $k+1$ where $a_{k+1}= 1$ because for any good permutation $(a_1, a_2, \cdots , a_n, a_{n+1} )$ where $a_{n+1}= k+1,$ $(n+2)-a_1, (n+2) - a_2, \cdots , (n+2) - a_3, \cdots , (n+2) - a_{n+1})$ forms a good permutation with its last element $n+2 - (n+1)= 1.$ Thus, $E_{k+1}= E_k + E_k= 2 E_k,$ proving our claim. $\blacksquare$

---

Note that all permutations of $(1, 2, 3)$ are good, so $E_3= 3!= 6.$ Now, solving the recurrence for $E_k$ gives $E_k= 3 \cdot 2^{k-1}.$ Our desired answer is $\boxed{E_{2014} = 3 \cdot 2^{2013}},$ whose last three digits are $\boxed{288}.$

---

This problem is adapted from ISL 2008 C2 .

Sreejato, I like your solution. I used basically the same method.

When constructing the good permutations of $1,2, \dots, n+1$ from good permutations of $1,2, \ldots, n$ , I preferred using the following two constructions:

1. Simply append $n+1$ to the end: $(a_1, a_2, \ldots, a_n) \rightarrow (a_1, a_2, \ldots, a_n, n+1)$

2. Add 1 to each of them and then append 1 to the end: $(a_1, a_2, \ldots, a_n) \rightarrow (a_1 + 1, a_2 + 1, \ldots, a_n + 1, 1)$

(also, I think there is a typo in your proof. You wrote $\frac{k+2}{2}$ in two places where I think you meant $\frac{k+1}{2}$ )