Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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