4. For an integer $a, a \neq 0$, denote by $v_{2}(a)$ the largest non-negative integer $k$ such that $2^{k} \mid a$. For a given $n \in \mathbb{N}$, determine the largest possible cardinality of a subset $A$ of the set $\left\{1,2,3, \ldots, 2^{n}\right\}$ with the following property:

$$
\text { for all } x, y \in A, x \neq y, \text { the number } v_{2}(x-y) \text { is even. }
$$

(Dušan Đukić)
4. We will 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}$ remainders modulo $2^{2k-2}$. Assume that the elements of $A$ give more than $2^k$ remainders modulo $2^{2k}$. By the Dirichlet principle, at least three of these remainders are equal modulo $2^{2k-2}$. But among these three remainders, two differ by $2^{2k-1} \pmod{2^{2k}}$, contradicting 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 $\left\{0,1, \ldots,\left[\frac{n-1}{2}\right]\right\}$.

Second solution. We say that a set $X$ is lucky if $v_2(x-y)$ is even for all $x, y \in X (x \neq y)$, and unlucky if $v_2(x-y)$ is odd for all $x, y \in X (x \neq y)$. Let $a_n$ and $b_n$ be the maximum cardinality of a lucky and an unlucky subset of the set $T_n = \left\{1, 2, \ldots, 2^n\right\}$, respectively.

Consider a lucky 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\rvert\, x \in A, 2 \nmid x\right\}$ are unlucky 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 unlucky set, the set $\left\{2x, 2x+1 \mid x \in A_0\right\} \subset T_n$ is lucky 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 its elements have the same parity, and the set $B' = \left\{\left.\left\lceil\frac{x}{2}\right\rceil \right\rvert\, x \in B\right\} \subset T_{n-1}$ is lucky. On the other hand, if $B' \subset T_{n-1}$ is lucky, the set $B = \left\{2x-1 \mid x \in B'\right\} \subset T_n$ is unlucky. Hence, $b_n = a_{n-1}$.

The obtained relations give $a_n = 2a_{n-2}$ for $n \geqslant 2$, and from $a_0 = 1$ and $a_1 = 2$, simple induction yields $a_n = 2^{\left[\frac{n+1}{2}\right]}$.