Maths Olympiad Prep

Library / /2 of 22

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Germany

Problem:

Let nn be a positive integer greater than one and B={1,2,,2n}B=\{1,2, \ldots, 2^{n}\}. A subset AA of BB is called funny if, of any two distinct elements x,yx, y of BB whose sum is a power of two, it contains exactly one. How many funny subsets does BB have?

Solution

Solution:

The number is 2n+12^{n+1}. We argue by complete induction on nn and set Bn={1,2,,2n}B_{n}=\{1,2, \ldots, 2^{n}\}.

Base case, n=1n=1. This case is clear: all four subsets of B1={1,2}B_{1}=\{1,2\} are funny.

Inductive step, nn+1n \longrightarrow n+1. So suppose it is already known that BnB_{n} has exactly 2n+12^{n+1} funny subsets. For each funny set AA of BnB_{n} construct the sets

Cn(A)={2n+1mmBn\A, m<2n},C_{n}(A)=\{2^{n+1}-m \mid m \in B_{n} \backslash A,\ m<2^{n}\},

Mn(A)=ACn(A)M_{n}(A)=A \cup C_{n}(A)

and

Nn(A)=Mn(A){2n+1}.N_{n}(A)=M_{n}(A) \cup\{2^{n+1}\}.

Evidently AA, Cn(A)C_{n}(A) and {2n+1}\{2^{n+1}\} are pairwise disjoint. The sets Mn(A)M_{n}(A) and Nn(A)N_{n}(A) are funny: to see this, let x,yx, y be distinct elements of Bn+1B_{n+1} whose sum is a power of two; without loss of generality let x<yx<y.

In the case 1x<y2n1 \leq x<y \leq 2^{n}, that is x,yBnx, y \in B_{n}, exactly one of the two is contained in Mn(A)M_{n}(A) resp. Nn(A)N_{n}(A), since AA is funny.

In the case 1x2n<y2n+11 \leq x \leq 2^{n}<y \leq 2^{n+1} we have 2n<x+y<2n+22^{n}<x+y<2^{n+2}, hence x+y=2n+1x+y=2^{n+1}; since x1x \geq 1, we have y2n+1y \neq 2^{n+1}. By the choice of Cn(A)C_{n}(A), either xx lies in AA or yy lies in Cn(A)C_{n}(A).

The case 2n<x<y2n+12^{n}<x<y \leq 2^{n+1} cannot occur, since then 2n+1<x+y<2n+22^{n+1}<x+y<2^{n+2}.

Conversely, if MM is a funny subset of Bn+1B_{n+1}, then evidently A:=MBnA:=M \cap B_{n} is a funny subset of BnB_{n}. The element y=2n+1xy=2^{n+1}-x of Bn+1B_{n+1} with 1x<2n1 \leq x<2^{n} is contained in MM if and only if xBnx \in B_{n} is not contained in AA, since x+y=2n+1x+y=2^{n+1} is a power of two. Thus, knowing MBnM \cap B_{n}, the funniness of MM determines, for all elements yy of Bn+1B_{n+1} with 2n<y<2n+12^{n}<y<2^{n+1}, whether they are contained in MM; the only remaining freedom is whether 2n+12^{n+1} is an element. Hence MM equals either Mn(A)M_{n}(A) or Nn(A)N_{n}(A), and to each funny subset of BnB_{n} exactly two funny subsets of Bn+1B_{n+1} can be assigned. 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 de; metadata (topic, difficulty) added by this project.