Let $A$ and $B$ be two sets of real numbers. Suppose that the elements of the set $AB = \{ab: a\in A, b\in B\}$ form a finite arithmetic progression. Prove that one of these sets contains no more than three elements
Problem
Source: Ukraine TST 2015 p7
Tags: arithmetic sequence, Sets, Product, algebra
UK2019Project
15.05.2020 15:28
Bummmmmmppppppppp
math_pi_rate
15.05.2020 15:54
I had tried this problem a little bit when it was posted, but I left it after seeing that I had a case bash at hand . I doubt if I'll be trying this again any time soon, so I'll just post the progress I had at that time (in particular, if someone has some ideas on how to handle the case bash succinctly, then do post it here). The proof proceeds in three steps, as given below-
FTSOC assume that both the sets have at least $4$ elements. Let $A=\{a_1,a_2, \dots ,a_m\}$ and $B=\{b_1,b_2, \dots ,b_n\}$, and suppose the common difference of the finite AP formed by $AB$ is $d$ (with $d$ taken as positive). As $|A|,|B|>1$, so we must have $d>0$ (since $A,B$ are sets, not multisets). Also WLOG assume $a_1,b_1 \neq 0$. Then, for all $i \in [m-1]$ and $j \in [n]$, we have $$\frac{b_j(a_{i+1}-a_i)}{d} \in \mathbb{Z} \quad (\spadesuit)$$This means that $$\frac{b_j}{b_1} \in \mathbb{Q} \text{, and similarly, } \frac{a_j}{a_1} \in \mathbb{Q} \quad (\heartsuit)$$where the indices are appropriately chosen. Now, notice that if $A,B$ satisfy the given conditions, then so do $xA,yB$ for non-zero reals $x,y$ (since this simply amounts to multiplying each element of $AB$ by $xy$). This means that $$A'=\frac{A}{a_1} \text{ and } B'=\frac{B}{b_1}$$also work. But, using $(\heartsuit)$, we know that all elements of both $A',B'$ are rationals. Multiplying elements of $A',B'$ by the LCM of their corresponding denominators, we get two sets of integers. So effectively, it suffices to work with integer sets.
So suppose both $A$ and $B$ consist of integers, and sort them as $a_1<a_2< \dots <a_m$ and $b_1<b_2< \dots <b_n$ (the assumption that $a_1,b_1 \neq 0$ no longer holds). Since elements of $AB$ are also integers, so we must have $d \in \mathbb{N}$. Also, by dividing each element of $A,B$ with the GCD of their sets, we may WLOG assume that $\gcd(A)=\gcd(B)=1$. Finally assume that $n \leq m$. Now, from $(\spadesuit)$, we know that $d \mid b_j(a_{i+1}-a_i)$. We first deal with the case $d>1$. Suppose there exists an index $i$ with $d \nmid a_{i+1}-a_i$. Then there is some $r>1$ with $r \mid d$ such that $r \mid b_j$ for all $j \in [n]$, which is contrary to $\gcd(B)=1$. So $d \mid a_{i+1}-a_i$ for all $i \in [m-1]$. Applying a similar result for $B$, we may say that $d \mid b_{j+1}-b_j$ for every $j \in [n-1]$. In particular, this means that $$0 \not \equiv a_1 \equiv a_2 \equiv \dots \equiv a_m \pmod{d} \Rightarrow a_m-a_1 \geq (m-1)d$$Now, since elements of $AB$ form an AP with common difference $d$ and consisting of at most $mn$ elements, so the difference between any two elements of set $AB$ is at most $(mn-1)d$. This gives $$(mn-1)d \geq |b_j(a_m-a_1)| \geq |b_j|(m-1)d \Rightarrow |b_j| \leq \frac{mn-1}{m-1}=n+\frac{n-1}{m-1} \leq n+1$$where $j \in [n]$. But, we also have $b_n-b_1 \geq (n-1)d$ in a similar manner as before, which means that $$(n-1)d \leq b_n-b_1 \leq (n+1)-(-n-1)=2n+2 \Rightarrow d \leq \frac{2n+2}{n-1}=2+\frac{4}{n-1} \Rightarrow d \leq 3$$where we use our original assumption that $n \geq 4$.
From the above analysis, it suffices to consider the cases $d=1,2,3$. We handle these cases separately.
For $d=3$, the last inequality above gives $n \leq 5$, which in turn implies that $|b_j| \leq n+1 \leq 6$. As there are at most $4$ non-zero integers in $[-6,6]$ which leave the same remainder modulo $3$, so we must have $n=4$. Also, in the previous inequality, if $m \neq n$, then we have $|b_j|<n+1$, which gives $b_n-b_1 \leq n-(-n)=2n$. Then $d \leq \frac{2n}{n-1}<3$ for $n=4$, which is not true. So we get $m=n=4$. But, for $m=n$, we can use similar calculations as above to show $|a_i| \leq 6$. Then, since $3$ does not divide any $a_i$, so the possible sets are $\{-5,-2,1,4\}$ and $\{-4,-1,2,5\}$. Since the first set is simply the negative of the second set, so we can WLOG assume that $A=B=\{-4,-1,2,5\}$. It's easy to check that this doesn't work (In particular, $25$ is present in $AB$ but $22$ is not).
$\text{ }$
Now consider $d=2$. If $a_1,a_2, \dots ,a_m$ do not form an AP with common difference $d$, then $a_m-a_1 \geq md$. Then in a similar fashion as our calculations above, we have $$|b_j| \leq \frac{mn-1}{m}=n-\frac{1}{m} \Rightarrow |b_j| \leq n-1$$But then $$(n-1)d \leq b_n-b_1 \leq 2n-2 \Rightarrow d \leq 2$$Since $d=2$, so this means that equality holds for the inequality of the previous line, i.e. $b_n=b_1+2(n-1)$, which in turn gives that the $b_i$'s form an AP with common difference $2$. In particular, this gives that at least one of the sets $A$ or $B$ form an AP with common difference $2$. (Incomplete)
$\text{ }$
Finally take $d=1$. If all the elements of the set $AB$ have same sign, then the elements of the sets $A$ and $B$ must also have same sign (however, these common signs might be different for $A$ and $B$). If this common sign is minus sign, then we can simply multiply the whole set by $-1$ to get a positive set, and then rearrange the elements to get the same ordering as before. But then $a_mb_n$ is the maximum element of $AB$, while the second largest element is either $a_{m-1}b_n$ or $a_mb_{n-1}$. Since the difference between these two elements is one, so we get either $a_m \leq 1$ or $b_n \leq 1$. But, for $m,n \geq 4$, we have $a_m>a_1 \geq 1$ and $b_n>b_1 \geq 1$, a contradiction. So the set $AB$ must have two elements of different signs. (Incomplete)