# Determine all positive integers $n$ for which $B_n=\{0\}$.

Let $A_1,A_2,...,A_n,...$ and $B_1,B_2,...,B_n,...$ be sequences of sets defined by $a_1=\emptyset$, $B_1=\{0\}$, $A_{n+1}=\{x+1|x\in B_n\},B_{n+1}=(A_n\cup B_n)\setminus(A_n\cap B_n)$. Determine all positive integers $n$ for which $B_n=\{0\}$.

I think this problem is from a Chinese Math Olympiad. Also by experimentation the answer seems to be all powers of 2.

-

You can show by induction that for $i$ between $2^k$ and $2^{k+1}$, there is always more than 0 in $B_i$, for $i=2^{k}$ there is only 0 and for $i=2^{k+1}+1$, there are exactly the powers of 2 ($1,2, \dots, 2^k$).
Let us do the induction step towards $k$ (small and large numbers will refer to numbers below $2^{k-1}$ and starting from $2^{k-1}$, respectively).
First, we notice that the presence and absence of numbers does not depend on numbers larger than itself, so starting from the powers of 2 in $B_{2^k+1}$, the numbers up to $2^{k-1}-1$ behave exactly as from the beginning. This already proves that $B_i$ contains more than 0 if $i$ is between $2^k+2^{k-1}$ and $2^{k+1}$, that there are no small numbers in $B_{2^{k+1}}$ and that $B_{2^{k+1}+1}$ will contain among the small numbers exactly the powers of two.
For the big numbers, we note that $2^{k-1}$ from $B_{2^k+1}$ cannot be removed for $2^{k-1}$ steps, because removing now would correspond to generating it earlier, but each number $n$ appears first at step $2n$, so it has not been generated before. Therefore, $2^{k-1}$ is in the first $2^{k-1}$ sets of our interval. This proves now that all the sets in our interval contain more than 0.
By the periodicity of the small numbers, $2^{k-1}$ will only return in time for $B_{2^{k+1}+1}$. But this means that the minimum of the large numbers increases by 1 at each step and reaches $2^{k+1}-1$ at $B_{2^{k+1}-1}$. Since $2^{k+1}-2$ was in the set before, it vanishes in $B_{2^{k+1}}$ as desired and returns as only one of the large numbers in $B_{2^{k+1}+1}$.