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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.