Serbian Mathematical Olympiad

Solution:

We shall prove by induction on $k$ that the set $A$ contains at most $2^{k}$ distinct elements modulo $2^{2k}$. This trivially holds for $k=0$. Let $k>0$. By the induction hypothesis, the elements of the set $A$ give at most $2^{k-1}$ residues modulo $2^{2k-2}$. Suppose that the elements of $A$ give more than $2^{k}$ residues modulo $2^{2k}$. By the Pigeonhole Principle, at least three of these residues are equal modulo $2^{2k-2}$. But among these three residues, two differ by $2^{2k-1}(\bmod\ 2^{2k})$, contrary to the condition of the problem.
It follows that $|A| \leqslant 2^{\left[\frac{n+1}{2}\right]}$. An example of a set $A$ with $2^{\left[\frac{n+1}{2}\right]}$ elements is obtained by including numbers of the form $\sum_{i \in B} 4^{i}$ for all subsets $B$ of the set $\{0,1, \ldots,\left[\frac{n-1}{2}\right]\}$.

Second solution. We say that a set $X$ is happy if $v_{2}(x-y)$ is even for all $x, y \in X(x \neq y)$, and unhappy if $v_{2}(x-y)$ is odd for all $x, y \in X(x \neq y)$. Denote by $a_{n}$ and $b_{n}$, respectively, the maximal cardinalities of a happy and an unhappy subset of the set $T_{n}=\{1,2, \ldots, 2^{n}\}$.
Consider a happy set $A \subset T_{n}, n \geqslant 1$. Since $v_{2}(2x-2y)=v_{2}(x-y)+1$, the sets $A_{0}=\left\{\frac{x}{2}\mid x \in A, 2\mid x\right\}$ and $A_{1}=\left\{\left.\frac{x-1}{2} \right| x \in A, 2 \nmid x\right\}$ are unhappy subsets of the set $T_{n-1}$ and have at most $b_{n-1}$ elements each. On the other hand, if $A_{0} \subset T_{n-1}$ is an unhappy set, the set $\{2x, 2x+1 \mid x \in A_{0}\} \subset T_{n}$ is happy and has $2|A_{0}|$ elements. It follows that $a_{n}=2b_{n-1}$.
Similarly, if $B \subset T_{n}$ is an odd set, all of its elements have the same parity, and the set $B' = \left\{\left.\left\lceil\frac{x}{2}\right\rceil \right| x \in B\right\} \subset T_{n-1}$ is happy. On the other hand, if $B' \subset T_{n-1}$ is happy, the set $B=\{2x-1 \mid x \in B'\} \subset T_{n}$ is unhappy. From this, $b_{n}=a_{n-1}$.
The relations obtained give $a_{n}=2a_{n-2}$ for $n \geqslant 2$, so from $a_{0}=1$ and $a_{1}=2$, by simple induction we obtain $a_{n}=2^{\left[\frac{n+1}{2}\right]}$.