Olympiad Maths Prep

Library / /7 of 11

Number theory Difficulty 6.3 National olympiad Prove it Czech Republic

Let AA, BB be sets of positive integers such that a sum of arbitrary two different numbers from AA is in BB and a ratio of arbitrary two different numbers from BB (greater one to smaller one) is in AA. Find the maximum number of elements in ABA \cup B.
(Martin Panák)

Solution

Initially we will prove that the set AA consists of at most two numbers. Suppose that three numbers a<b<ca < b < c belong to the set AA. Then the numbers a+b<a+c<b+ca+b < a+c < b+c are in BB and therefore the number
b+ca+c=1+baa+c \frac{b+c}{a+c} = 1 + \frac{b-a}{a+c}
has to be in AA. This is a contradiction because 0<ba<a+c0 < b-a < a+c and the number is not integer.

If the set BB contains four numbers k<l<m<nk < l < m < n, then the set AA will contain three different numbers n/kn/k, n/ln/l, n/mn/m. So the set BB has at most three elements and ABA \cup B has at most five elements.

We achieve the number 55 of elements if A={a,b}A = \{a, b\}, B={k,l,m}B = \{k, l, m\}, where a<ba < b and l/k=m/l=al/k = m/l = a, m/k=bm/k = b. Then b=a2b = a^2 (a2a \ge 2) and a+a2a + a^2 is one of the elements of BB; the next two elements are either a2+a3a^2 + a^3 and a3+a4a^3 + a^4 or 1+a1 + a and a2+a3a^2 + a^3. E.g. sets A={2,4}A = \{2, 4\}, B={3,6,12}B = \{3, 6, 12\} have five elements together.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.