Maths Olympiad Prep

Library / /264 of 397

Combinatorics Difficulty 6.3 National Olympiad Prove it Taiwan

Let A1=A_1 = \emptyset, B1={0}B_1 = \{0\}. For all n2n \ge 2, construct recursively as follows:
An={x+1xBn1}, A_n = \{x + 1 \mid x \in B_{n-1}\},
Bn=An1Bn1An1Bn1, B_n = A_{n-1} \cup B_{n-1} - A_{n-1} \cap B_{n-1},
Find all nn for which Bn={0}B_n = \{0\}?

(Note: For any sets AA and BB, the set ABA - B denotes {xAxB}\{x \in A \mid x \notin B\}.)

Solution

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

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

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

Next, for n2n \ge 2, prove the following four properties:
(a) A2n1=2An1A_{2n-1} = 2A_n - 1;
(b) B2n1=A2n1B2nB_{2n-1} = A_{2n-1} \cup B_{2n};
(c) B2n=2BnB_{2n} = 2B_n;
(d) 1B2n11 \in B_{2n-1}.

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

For (b) and (c), we first need to obtain
A2n2=B2n3+1=(A2n3B2n2)+1=((2An11)2Bn1)+1=2An1(2Bn1+1). \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):
B2n1=A2n2B2n2A2n2B2n2=2An1(2Bn1+1)2Bn1(2An1(2Bn1+1))2Bn1=(2Bn1+1)2An12Bn12An12Bn1=(2Bn1+1)(2An12Bn12An12Bn1)=(2Bn1+1)2Bn=(B2n2+1)2Bn=A2n12Bn, \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}

B2n=A2n1B2n1A2n1B2n1=A2n1(A2n12Bn)A2n1(A2n12Bn)=A2n12BnA2n1=2BnA2n1=2Bn(2An1)=2Bn, \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 2Bn2B_n contains only even numbers while 2An12A_n - 1 contains only odd numbers. Since (c) is finished, (b) is also finished.

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

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.