Problem 1. Consider the set $A=\left\{1,2,3,4, \ldots, 2^{n}\right\}, n \geq 2$. Find the number of the subsets $B$ of $A$, such that if the sum of two elements of $A$ is a power of 2 then exactly one of them belongs to $B$.

Aleksandar Ivanov
1. Let $B$ be a subset of $A$ having the given property. Since $1+3=2^{2}$, we have that exactly one of the numbers 1 or 3 belongs to $B$.

If $1 \in B$ then $3 \notin B$. We prove by induction that for any integer $t, 0 \leq$ $t2.2^{l}=2^{l+1}$ giving $0<2^{l+1}-(4 s+5)<4 s+5$. Set $x=4 s+5$ and $y=2^{l+1}-(4 s+5)$. Then $x+y=2^{l+1}$ and since $y$ is of the form $4 m+3$ we conclude that $y \notin B$ and therefore $4(s+1)+1 \in B$. Analogously $4(s+1)+3 \notin B$.

If $1 \notin B$ then $3 \in B$ and we prove as above that the integers of the form $4 t+1$ belong to $B$ and the integers of the form $4 t+3$ do not.

Therefore the odd numbers in $B$ are either all integers of the form $4 t+1$ or all integers of the form $4 t+3$.

Let $x=2^{p} x_{0}$ and $y=2^{q} y_{0}$, where $x_{0}$ and $y_{0}$ are odd and $p$ and $q$ are positive integers. If $2^{p} x_{0}+2^{q} y_{0}=2^{k}$ and $p \neq q$, say $p<q$, then $x_{0}+2^{q-p} y_{0}=2^{k-p}$, which is impossible. Therefore $p=q$ and it follows that the sum of the elements from distinct sets $A_{i}=\left\{2^{i} a: a\right.$ is an odd integer $\}, i=1,2, \ldots n$ is not a power of 2 . For any $A_{i}$, after dividing by $2^{i}$ and applying the above arguments, we obtain that either all integers of the form $2^{i}(4 t+1)$ are in $B$ or all integers of the form $2^{i}(4 t+3)$ are in $B$.

Therefore there exist $2^{n+1}$ sets $B$ with the given property.