Maths Olympiad Prep

Library / /32 of 70

Number theory Difficulty 8.2 Shortlist Prove it Romania

Given a positive real number tt, determine the sets AA of real numbers containing tt, for which there exists a set BB of real numbers depending on AA, B4|B| \ge 4, such that the elements of the set AB={ab:aA,bB}AB = \{ab: a \in A, b \in B\} form a finite arithmetic progression.

Solution

The required sets are {t}\{t\}, {t,t}\{-t, t\}, {0,t}\{0, t\} and {t,0,t}\{-t, 0, t\}. It is readily checked that the elements of the Minkowski product of each of these sets and the set {1,0,1,2}\{-1, 0, 1, 2\} form a finite arithmetic progression.

Now, let AA and BB be sets of real numbers satisfying the conditions in the statement, and let A2|A| \ge 2 (the case A=1|A| = 1 is trivial). Clearly, AA and BB are both finite.

Let d>0d > 0 be the difference of the arithmetic progression ABAB, consider two distinct elements of AA, say xx and xx', and two distinct elements of BB, say yy and yy', and notice that the elements of AA, respectively BB, are integral multiples of d/(yy)d/(y-y'), respectively d/(xx)d/(x-x'). Scaling AA and BB accordingly, we may (and will) assume that AA and BB are both sets of integers. Dividing, if necessary, the elements of AA, respectively BB, by their greatest common divisor, we may (and will) further assume that the elements of AA, respectively BB, are jointly coprime: gcd A=1\text{gcd } A = 1 and gcd B=1\text{gcd } B = 1. Further, recall that AA and BB are both finite and let aa^*, respectively bb^*, be an element of AA, respectively BB, of maximal absolute value. If necessary, multiply by 1-1 to assume a>0a^* > 0 and b>0b^* > 0. Under these simplifying assumptions, we will show that AA is one of the sets {1,1}\{-1, 1\}, {0,1}\{0, 1\}, {1,0,1}\{-1, 0, 1\}, whence the conclusion.

Since gcd B=1\text{gcd } B = 1 and dd divides (xx)y(x - x')y for all xx and xx' in AA and all yy in BB, it follows that dd divides the difference of any two members of AA. Similarly, dd divides the difference of any two members of BB, and since B4|B| \ge 4, it follows that b>db^* > d.

Consider now elements aa in AA and bb in BB such that ab=abdab = a^*b^* - d, and notice that ab=abdbd>0ab = a^*b^* - d \ge b^* - d > 0. Moreover, a=a|a| = a^*, for otherwise abd=ab=ab(a1)b=abb<abda^*b^* - d = ab = |a||b| \le (a^* - 1)b^* = a^*b^* - b^* < a^*b^* - d which is a contradiction.

This means that d=abab=a(bb)ad = a^*b^* - |a||b| = a^*(b^* - |b|) \ge a^*. Now, since ada^* \le d, and the elements of AA are congruent modulo dd, the only possible options for AA are either subsets of {d,0,d}\{-d, 0, d\}, or {d/2,d/2}\{-d/2, d/2\} if dd is even, or finally sets of the form {a,ad}\{a^*, a^* - d\}, where d>a>add > a^* > |a^* - d|. The first two cases are covered by the answer.

To rule out the last option, notice that a=aa = a^* (since a=a>ad|a| = a^* > |a^* - d|), and therefore d=a(bb)d = a^*(b^* - |b|). This means that aa^* divides dd, so ad/2a^* \le d/2 and ada|a^* - d| \ge a^*, in contradiction with a>ada^* > |a^* - d|.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.