Problem:
Let s1,s2,s3,… be an infinite, nonconstant sequence of rational numbers, meaning it is not the case that s1=s2=s3=⋯. Suppose that t1,t2,t3,… is also an infinite, nonconstant sequence of rational numbers with the property that (si−sj)(ti−tj) is an integer for all i and j. Prove that there exists a rational number r such that (si−sj)r and (ti−tj)/r are integers for all i and j.
Solution:
First, we claim there exist i,j such that (si−sj)(ti−tj)=0. Indeed, for any fixed i, because the sequence s1,s2,… is nonconstant, there is some j such that sj=si. If tj=ti the claim follows, so suppose tj=ti. Because the sequence t1,t2,… is nonconstant, there exists k such that tk=ti. If sk=si the claim again follows, so suppose sk=si. Then (sj−sk)(tj−tk)=(sj−si)(ti−tk)=0, and the claim is proven.
We can reorder the pairs (si,ti) relative to each other without affecting either the hypothesis or the conclusion of the problem. So by a suitable reordering, we may assume that (s1−s2)(t1−t2)=0.
Second, for any constants a and b, we can replace si by si−a and ti by ti−b for all i without affecting either the hypothesis or the conclusion of the problem (since all the differences si−sj and ti−tj remain unchanged). In particular, by taking a=s1 and b=t1, we may assume that s1=t1=0. So we have reduced the problem to the case s1=t1=0,s2=0,t2=0.
Call a pair of positive rational numbers (A,B) good if AB is an integer, and Asj and Btj are also integers for all j.
Third, we show that a good pair exists.
We know that for all i≥2,(si−s1)(ti−t1)=siti is an integer; and for all i,j≥2, (si−sj)(ti−tj)=siti−sitj−sjti+sjtj is an integer, which implies sitj+sjti is an integer. Write the rational numbers sj, tj in lowest terms as sj=pj/qj and tj=uj/vj. We know that, for each j,sjtj=pjuj/qjvj is an integer. Because uj is relatively prime to vj, then, pj is divisible by vj, say pj=djvj for some integer dj. We also know that
s2tj+sjt2=q2vjp2uj+qjv2pju2=q2vjqjv2p2ujqjv2+pju2q2vj
is an integer. In particular, qj, being a factor of the denominator, must divide the numerator. But qj divides p2ujqjv2, so it also divides the other term, pju2q2vj=dju2q2vj2. Since qj is relatively prime to pj=djvj, it must divide u2q2. Moreover, u2q2=0, because of our assumption t2=0. So we have a positive integer A=∣u2q2∣ such that Asj is an integer for all j. Analogously, we can find a positive integer B such that Btj is an integer for all j. This (A,B) constitute a good pair, and existence is proven.
Now we are ready to complete our proof. We know that some good pair exists. We consider a good pair for which the product AB is as small as possible. We will show that AB=1.
Suppose that, for the minimal good pair, AB>1; then AB has a prime factor p. If the integer Asi is divisible by p for all i, then we can divide A by p and obtain a new good pair (A/p,B) having a smaller product than before - a contradiction. So for some i,Asi is not divisible by p. Then Bti must be divisible by p, because siti is an integer and so (Asi)(Bti)=(AB)(siti) is an integer divisible by p. Likewise, there exists some j such that Btj is not divisible by p, but Asj is.
Now write
(AB)(sitj+sjti)−(Asj)(Bti)=(Asi)(Btj)
All the parenthesized factors are integers, and the left-hand side is divisible by p, but the right-hand side is not. This contradiction completes the proof that the minimal good pair satisfies AB=1.
But now take the minimal good pair (A,B), and let r=A. We have that sir=Asi and ti/r=Bti are integers for all i, from which our desired conclusion follows.
Solution 2. For p a prime, define the p-adic norm ∥⋅∥p on rational numbers as follows: for r=0,∥r∥p is the unique integer n for which we can write r=pna/b with a,b integers not divisible by p. (By convention, ∥0∥p=+∞.) We will repeatedly use the wellknown (or easy to prove) fact that for any rational numbers r1,r2, we have ∥r1±r2∥p≥ min(∥r1∥p,∥r2∥p), with equality whenever ∥r1∥p=∥r2∥p. The condition of the problem implies that
∥si−sj∥p≥−∥ti−tj∥p(4)
for all i,j and all prime p.
We claim in fact that
∥si−sj∥p≥−∥tk−tl∥p
for all i,j,k,l and all prime p. Suppose otherwise; then there exist i,j,k,l,p for which ∥si− sj∥p<−∥tk−tl∥p. Since ∥si−sj∥p=∥(si−sk)−(sj−sk)∥p≥min(∥si−sk∥p,∥sj−sk∥p), at least one of ∥si−sk∥p and ∥sj−sk∥p, say the former, is strictly less than −∥tk−tl∥p. By (4), it follows that ∥ti−tk∥p>∥tk−tl∥p, and thus ∥ti−tl∥p=∥(ti−tk)+(tk−tl)∥p= ∥tk−tl∥p. Then by (4) again, ∥si−sl∥p≥−∥tk−tl∥p and ∥sk−sl∥p≥−∥tk−tl∥p, whence ∥si−sk∥p=∥(si−sl)−(sk−sl)∥p≥−∥tk−tl∥p, contradicting the assumption that ∥si−sk∥p<−∥tk−tl∥p. This proves the claim.
Now for each prime p, define the integer f(p)=mini,j∥si−sj∥p. Choose i0,j0,k0,l0 such that si0=sj0 and tk0=tl0; then f(p) exists since it is bounded below by −∥tk0−tl0∥p (by the claim) and above by ∥si0−sj0∥p. Moreover, if p does not divide the numerator or denominator of either si0−sj0 or tk0−tl0, then ∥si0−sj0∥p=∥tk0−tl0∥p=0 and thus f(p)=0. It follows that f(p)=0 for all but finitely many primes.
We can now define r=∏pp−f(p), where the product is over all primes. For any i,j, we have ∥si−sj∥p≥f(p) for all p by construction, and so (si−sj)r is an integer. On the other hand, for any k,l and any prime p,∥tk−tl∥p≥−∥si−sj∥p for all i,j by the claim, and so ∥tk−tl∥p≥−f(p). It follows that (tk−tl)/r is an integer for all k,l, whence r is the desired rational number.
This problem and the first solution was suggested by Gabriel Carroll. The second solution was suggested by Lenhard Ng.
The problems on this page are the property of the MAA's American Mathematics Competitions