Turkey — Team Selection Test

**The answer is $1024$.**
Let us call a partition of $\{1, 2, \dots, n\}$ into two sets *nice partition for $n$*, if none of the sets contains two distinct elements whose sum is a power of $2$. Let $p_n$ be the number of nice partitions for $n$. We observe that removing $n$ from a nice partition for $n$ gives a nice partition for $n-1$. Therefore, we can obtain the nice partitions for $n$ by adding $n$ to the nice partitions for $n-1$.
If $2^m < n < 2^{m+1}$ for some positive integer $m$, then as $2^m < n+1 \le n + (n-1) < 2^{m+2}$ and $1 \le 2^{m+1}-n \le n-1$, we must add $n$ into the set not containing $2^{m+1}-n$. Therefore, $p_n = p_{n-1}$.
If $n = 2^m$ for some positive integer $m$, then since $2^m < n + 1 \le n + (n-1) < 2^{m+1}$, we can add $n$ into any of the sets and hence $p_n = 2 \cdot p_{n-1}$.
As $p_2 = 2$ and $2^{10} < 2012 < 2^{11}$, we conclude that $p_{2012} = 2^{10} = 1024$.