Consider the set $A=\{1,2,3\ldots ,2^n\}, n\ge 2$. Find the number of subsets $B$ of $A$ such that for any two elements of $A$ whose sum is a power of $2$ exactly one of them is in $B$. Aleksandar Ivanov
Problem
Source: Bulgarian National Olympiad 2006 Day 1 Problem 1
Tags: combinatorics proposed, combinatorics
Xixas
05.06.2006 19:08
Let's call a subset $B$ satisfying the conditions of the problem proper. We are going to prove that the number of proper subsets is $2^{n+1}$. Considering the case $n=2$ it is easy to see that the proper subsets are $\{1\},\ \{3\},\ \{1, 2\},\ \{1, 4\},\ \{1, 2, 4\},\ \{3, 2\},\ \{3, 4\},\ \{3, 2, 4\}$ so there are $8$ proper subsets. Now assume we have proven the result for all naturals up to $n$ and we wish to prove it for $n+1$. Take a proper subset $B_n$ for $n$ and note that if $a\in [1; 2^n-1]$ and $a\in B_n$ then $2^{n+1}-a\notin B_{n+1}$ ($B_{n+1}$ is a proper subset for $n+1$). And if $a\notin B_n$ then $2^{n+1}-a\in B_{n+1}$. And we may choose freely whether $2^{n+1}\in B_{n+1}$ or not. In such a way we get that every subset $B_n$ corresponds to exactly two subsets $B_{n+1}$ (which clearly satisfy the conditions). And every $B_{n+1}$ corresponds to some $B_n$. The result follows.
WakeUp
17.10.2011 20:56
Later posted here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1365040#p1365040
biomathematics
12.06.2018 15:17
Consider a graph $G_n$ on $2^n$ vertices labelled from $1$ to $2^n$, where $i$ and $j$ are joined if their sum is a power of $2$.
-> We can show that $G_n$ has no cycles.
-> We can show that the vertices with the same highest power of $2$ form the connected components of $G_n$.
-> Thus there are $n+1$ disjoint trees that make up $G_n$, and the sizes of the trees are $1,1,2,\cdots,2^{n-1}$.
-> We want to choose exactly one of the endpoints for every edge for our set $B$. It is easy to see that for each tree, we have only $2$ choices.
Thus our answer is $2^{n+1}$.
Jcdmgdhnv
04.02.2021 04:40
bilarev wrote: Consider the set $A=\{1,2,3\ldots ,2^n\}, n\ge 2$. Find the number of subsets $B$ of $A$ such that for any two elements of $A$ whose sum is a power of $2$ exactly one of them is in $B$. Aleksandar Ivanov 4(2^n-2)