Taiwan IMO Selection Camp

We will prove that: $B_n = \{0\}$ if and only if $n = 2^k$ ($k \ge 0$).

Given a set $S$, let the notation $2S = \{2x \mid x \in S\}$ and $S + k = \{x + k \mid x \in S\}$ for any integer $k$.

First, for all $n \ge 1$, the elements of $A_n$ and $B_n$ are non-negative integers, and moreover $0 \notin A_n$ and $0 \in B_n$. This can be simply proved by induction.

Next, for $n \ge 2$, prove the following four properties:
(a) $A_{2n-1} = 2A_n - 1$;
(b) $B_{2n-1} = A_{2n-1} \cup B_{2n}$;
(c) $B_{2n} = 2B_n$;
(d) $1 \in B_{2n-1}$.

We prove this by induction. First check the case $n=2$, observing the first few terms: $A_2 = \{1\}$, $B_2 = \{0\}$, $A_3 = \{1\}$, $B_3 = \{0, 1\}$, $A_4 = \{1, 2\}$, $B_4 = \{0\}$, and one can verify each of these holds. Below we assume $n \ge 3$ and that the four properties hold for $n-1$. Regarding (a):

For (b) and (c), we first need to obtain
$$\begin{aligned} A_{2n-2} &= B_{2n-3} + 1 = (A_{2n-3} \cup B_{2n-2}) + 1 \\ &= ((2A_{n-1} - 1) \cup 2B_{n-1}) + 1 \\ &= 2A_{n-1} \cup (2B_{n-1} + 1). \end{aligned}$$

Regarding (b):
$$\begin{aligned} B_{2n-1} &= A_{2n-2} \cup B_{2n-2} - A_{2n-2} \cap B_{2n-2} \\ &= 2A_{n-1} \cup (2B_{n-1} + 1) \cup 2B_{n-1} \\ & \quad (2A_{n-1} \cup (2B_{n-1} + 1)) \cap 2B_{n-1} \\ &= (2B_{n-1} + 1) \cup 2A_{n-1} \cup 2B_{n-1} - 2A_{n-1} \cap 2B_{n-1} \\ &= (2B_{n-1} + 1) \cup (2A_{n-1} \cup 2B_{n-1} - 2A_{n-1} \cap 2B_{n-1}) \\ &= (2B_{n-1} + 1) \cup 2B_n \\ &= (B_{2n-2} + 1) \cup 2B_n \\ &= A_{2n-1} \cup 2B_n, \end{aligned}$$

$$\begin{aligned} B_{2n} &= A_{2n-1} \cup B_{2n-1} - A_{2n-1} \cap B_{2n-1} \\ &= A_{2n-1} \cup (A_{2n-1} \cup 2B_n) - A_{2n-1} \cap (A_{2n-1} \cup 2B_n) \\ &= A_{2n-1} \cup 2B_n - A_{2n-1} \\ &= 2B_n - A_{2n-1} \\ &= 2B_n - (2A_n - 1) \\ &= 2B_n, \end{aligned}$$
where the last equality is because $2B_n$ contains only even numbers while $2A_n - 1$ contains only odd numbers. Since (c) is finished, (b) is also finished.

Regarding (d): borrowing the earlier equation $B_{2n-1} = (2B_{n-1}+1)\cup2B_n$, since $0 \in B_{n-1}$ we have $1 \in B_{2n-1}$.

Finally we prove: $B_n = \{0\}$ if and only if $n = 2^k$ ($k \ge 0$). The "$\Leftarrow$" direction can be completed using $B_1 = \{0\}$ together with (c). As for the "$\Rightarrow$" direction, for all $n \ne 2^k$ it must be that $n = 2^k m$ where $k \ge 0$ and $m$ is a positive odd number not equal to 1. If $k=0$ then $n$ is odd, and by (d) we know $1 \in B_n \ne \{0\}$. If $k \ge 1$ then $B_n = 2^k B_m$, so $2^k \in B_n \ne \{0\}$. This completes the proof!