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

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

(Dušan Djukić)
4. We shall prove by induction on $k$ that set $A$ can contain at most $2^{k}$ different elements modulo $2^{2 k}$. This is trivial for $k=0$; let $k>0$. By the induction hypothesis, the elements of $A$ give at most $2^{k-1}$ different residues modulo $2^{2 k-2}$. Suppose that they give more than $2^{k}$ residues modulo $2^{2 k}$. Then by the pigeonhole principle, some three elements are equal modulo $2^{2 k-2}$, and among these three, two differ by $2^{2 k-1}\left(\bmod 2^{2 k}\right)$, contradiction the problem condition.

It follows that $|A| \leqslant 2^{\left[\frac{n+1}{2}\right]}$. An example with exactly $2^{\left[\frac{n+1}{2}\right]}$ elements can be obtained by including the numbers of the form $\sum_{i \in B} 4^{i}$, where $B$ runs through all subsets of $\left\{0,1, \ldots,\left[\frac{n-1}{2}\right]\right\}$.

Second solution. We call a set $X$ happy if $v_{2}(x-y)$ is even for all distinct $x, y \in X$, and unhappy if $v_{2}(x-y)$ is odd for all distinct $x, y \in X$. Let $a_{n}$ and $b_{n}$ be the maximal cardinalities of happy and unhappy subsets of the set $T_{n}=\left\{1,2, \ldots, 2^{n}\right\}$, respectively.

Consider a happy subset $A \subset T_{n}, n \geqslant 1$. Since $v_{2}(2 x-2 y)=v_{2}(x-y)+1$, sets $A_{0}=\left\{\frac{x}{2}|x \in A, 2| x\right\}$ and $A_{1}=\left\{\left.\frac{x-1}{2} \right\rvert\, x \in A, 2 \nmid x\right\}$ are unhappy subsets of $T_{n-1}$ having at most $b_{n-1}$ elements each. On the other hand, if $A_{0} \subset T_{n-1}$ is unhappy, then $\left\{2 x, 2 x+1 \mid x \in A_{0}\right\} \subset T_{n}$ is a happy set with $2\left|A_{0}\right|$ elements. Therefore $a_{n}=2 b_{n-1}$.

Similarly, if $B \subset T_{n}$ is unhappy, all its elements have the same parity, so $B^{\prime}=$ $\left\{\left.\left\lceil\frac{x}{2}\right\rceil \right\rvert\, x \in B\right\} \subset T_{n-1}$ is a happy set. Conversely, if $B^{\prime} \subset T_{n-1}$ happy, then $B=\left\{2 x-1 \mid x \in B^{\prime}\right\} \subset T_{n}$ is unhappy. Therefore $b_{n}=a_{n-1}$.

The above relations yield $a_{n}=2 a_{n-2}$ for $n \geqslant 2$, so the equalities $a_{0}=1$ and $a_{1}=2$ imply $a_{n}=2^{\left[\frac{n+1}{2}\right]}$.