Turkey — Team Selection Test

Let $f(n)$ be the total number of all permutations of $n$-tuple $(1, 2, \dots, n)$ satisfying $i + a_i \le j + a_j$ for all $1 \le i < j \le n$. Readily $f(1) = 1$.

If for some permutation $a_1 = n$, then $a_2 = n-1, a_3 = n-2, \dots, a_n = 1$ is the only possibility.

If for some permutation $a_{k+1} = n$ for some $k$, $1 \le k \le n-1$ then $n - a_{k+2} \le 1$ and $a_{k+2} = n-1$. Similarly we get $a_{k+j} = n+1-j$ for $3 \le j \le n-k$. Therefore, $(a_1, a_2, \dots, a_k)$ should be a permutation of $(1, 2, \dots, k)$ satisfying conditions. Now note that the concatenation of $(a_1, a_2, \dots, a_k)$ and $(a_{k+1}, \dots, a_n)$ also satisfies conditions.

Thus, $f(n) = 1 + f(1) + f(2) + \dots + f(n-1)$ and consequently $f(n) = 2f(n-1)$. Thus, $f(n) = 2^{n-1}$ and the answer is $2^{2013}$.