Maths Olympiad Prep

Library / /91 of 520

Number theory Difficulty 5.6 AIME, harder Find the answer

The sets AA and BB are subsets of the positive integers. The sum of any two different elements from AA is an element of BB. The quotient of any two different elements from BB (where we divide the largest by the smallest) is an element of AA. Determine the maximum number of elements in ABA \cup B.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Suppose AA contains at least three elements, say a<b<ca < b < c, so bab - a is positive, thus it must hold that a+cbaa + c \leq b - a. This gives cb2ac \leq b - 2a. Therefore, AA contains at most two elements.
Suppose BB contains at least four elements, say a<b<c<da < b < c < d. Then AA contains the three distinct elements da,db\frac{d}{a}, \frac{d}{b}, and dc\frac{d}{c}. But AA cannot contain three distinct elements, contradiction. Therefore, BB contains at most three elements.
In total, ABA \cup B contains at most 5 elements. This is possible, for example with A={2,4}A = \{2, 4\} and B={3,6,12}B = \{3, 6, 12\}. Now 2+4=6B2 + 4 = 6 \in B and 126=63=2A\frac{12}{6} = \frac{6}{3} = 2 \in A and 123=4A\frac{12}{3} = 4 \in A, so this pair of sets satisfies the conditions. We conclude that ABA \cup B contains at most 5 elements.
Finding a pair of sets that satisfies the conditions can be done as follows. Suppose BB contains the elements a<b<ca < b < c. Then AA contains the elements cb,ba\frac{c}{b}, \frac{b}{a}, and ca\frac{c}{a}, with ca\frac{c}{a} being the largest. Since AA contains only two elements, it must hold that cb=ba\frac{c}{b} = \frac{b}{a}. Furthermore, the sum of the two elements in AA must be in BB, so ba+caB\frac{b}{a} + \frac{c}{a} \in B. Write b=tab = ta, then c=tb=t2ac = tb = t^2a and ba+ca=t+t2\frac{b}{a} + \frac{c}{a} = t + t^2. Now you see that bb can equal t+t2t + t^2 by choosing a=t+1a = t + 1. With t=1t = 1, you get b=ab = a, so this does not work; with t=2t = 2, you get the solution mentioned above.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.