USAMO, 2009

Solution 1 (By Gabriel Carroll). First, we claim there exist $i, j$ such that $(s_i-s_j)(t_i-t_j) \neq 0$. Indeed, for any fixed $i$, because the sequence $s_1, s_2, \dots$ is non-constant, there is some $j$ such that $s_j \neq s_i$. If $t_j \neq t_i$ the claim follows, so suppose $t_j = t_i$. Because the sequence $t_1, t_2, \dots$ is nonconstant, there exists $k$ such that $t_k \neq t_i$. If $s_k \neq s_i$ the claim again follows, so suppose $s_k = s_i$. Then $(s_j - s_k)(t_j - t_k) = (s_j - s_i)(t_i - t_k) \neq 0$, and the claim is proven. We can reorder the pairs $(s_i, t_i)$ relative to each other without affecting either the hypothesis or the conclusion of the problem. So by a suitable reordering, we may assume that $(s_1 - s_2)(t_1 - t_2) \neq 0$.

Second, for any constants $a$ and $b$, we can replace $s_i$ by $s_i - a$ and $t_i$ by $t_i - b$ for all $i$ without affecting either the hypothesis or the conclusion of the problem (since all the differences $s_i - s_j$ and $t_i - t_j$ remain unchanged). In particular, by taking $a = s_1$ and $b = t_1$, we may assume that $s_1 = t_1 = 0$. So we have reduced the problem to the case $s_1 = t_1 = 0$, $s_2 \neq 0$, $t_2 \neq 0$.

Call a pair of positive rational numbers $(A, B)$ good if $AB$ is an integer, and $As_j$ and $Bt_j$ are also integers for all $j$.

Third, we show that a good pair exists. We know that for all $i \ge 2$, $(s_i - s_1)(t_i - t_1) = s_i t_i$ is an integer; and for all $i, j \ge 2$, $(s_i - s_j)(t_i - t_j) = s_i t_i - s_i t_j - s_j t_i + s_j t_j$ is an integer, which implies $s_i t_j + s_j t_i$ is an integer. Write the rational numbers $s_j, t_j$ in lowest terms as $s_j = p_j/q_j$ and $t_j = u_j/v_j$. We know that, for each $j$, $s_j t_j = p_j u_j / q_j v_j$ is an integer. Because $u_j$ is relatively prime to $v_j$, then, $p_j$ is divisible by $v_j$, say $p_j = d_j v_j$ for some integer $d_j$. We also know that
$$s_2 t_j + s_j t_2 = \frac{p_2 u_j}{q_2 v_j} + \frac{p_j u_2}{q_j v_2} = \frac{p_2 u_j q_j v_2 + p_j u_2 q_2 v_j}{q_2 v_j q_j v_2}$$
is an integer. In particular, $q_j$, being a factor of the denominator, must divide the numerator. But $q_j$ divides $p_2 u_j q_j v_2$, so it also divides the other term, $p_j u_2 q_2 v_j = d_j u_2 q_2 v_j^2$. Since $q_j$ is relatively prime to $p_j = d_j v_j$, it must divide $u_2 q_2$. Moreover, $u_2 q_2 \neq 0$, because of our assumption $t_2 \neq 0$. So we have a positive integer $A = |u_2 q_2|$ such that $As_j$ is an integer for all $j$. Analogously, we can find a positive integer $B$ such that $Bt_j$ is an integer for all $j$. This $(A, B)$ constitute a good pair, proving existence.

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 $As_i$ 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$, $As_i$ is not divisible by $p$. Then $Bt_i$ must be divisible by $p$, because $s_i t_i$ is an integer and so $(As_i)(Bt_i) = (AB)(s_i t_i)$ is an integer divisible by $p$. Likewise, there exists some $j$ such that $Bt_j$ is not divisible by $p$, but $As_j$ is. Now write
$$(AB)(s_i t_j + s_j t_i) - (As_j)(Bt_i) = (As_i)(Bt_j).$$
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 $s_i r = As_i$ and $t_i / r = Bt_i$ are integers for all $i$, from which our desired conclusion follows.

Solution 2 (By Lenhard Ng). For $p$ a prime, define the $p$-adic norm $\| \cdot \|_p$ on rational numbers as follows: for $r \neq 0$, $\|r\|_p$ is the unique integer $n$ for which we can write $r = p^n a/b$ with $a, b$ integers not divisible by $p$. (By convention, $\|0\|_p = +\infty$.) We will repeatedly use the well-known (or easy to prove) fact that for any rational numbers $r_1, r_2$, we have $\|r_1 \pm r_2\|_p \ge \min(\|r_1\|_p, \|r_2\|_p)$, with equality whenever $\|r_1\|_p \neq \|r_2\|_p$. The condition of the problem implies that
$$\|s_i - s_j\|_p \ge -\|t_i - t_j\|_p \qquad (1)$$
for all $i, j$ and all primes $p$.

We claim in fact that
$$\|s_i - s_j\|_p \geq -\|t_k - t_l\|_p$$
for all $i, j, k, l$ and all prime $p$. Suppose otherwise; then there exist $i, j, k, l, p$ for which $\|s_i - s_j\|_p < -\|t_k - t_l\|_p$. Since $\|s_i - s_j\|_p = \|(s_i - s_k) - (s_j - s_k)\|_p \geq \min(\|s_i - s_k\|_p, \|s_j - s_k\|_p)$, at least one of $\|s_i - s_k\|_p$ and $\|s_j - s_k\|_p$, say the former, is strictly less than $-\|t_k - t_l\|_p$. By (1), it follows that $\|t_i - t_k\|_p > \|t_k - t_l\|_p$, and thus $\|t_i - t_l\|_p = \|(t_i - t_k) + (t_k - t_l)\|_p = \|t_k - t_l\|_p$. Then by (1) again, $\|s_i - s_l\|_p \geq -\|t_k - t_l\|_p$ and $\|s_k - s_l\|_p \geq -\|t_k - t_l\|_p$, whence $\|s_i - s_k\|_p = \|(s_i - s_l) - (s_k - s_l)\|_p \geq -\|t_k - t_l\|_p$, contradicting the assumption that $\|s_i - s_k\|_p < -\|t_k - t_l\|_p$. This proves the claim.

Now for each prime $p$, define the integer $f(p) = \min_{i,j} \|s_i - s_j\|_p$. Choose $i_0, j_0, k_0, l_0$ such that $s_{i_0} \neq s_{j_0}$ and $t_{k_0} \neq t_{l_0}$; then $f(p)$ exists since it is bounded below by $-\|t_{k_0} - t_{l_0}\|_p$ (by the claim) and above by $\|s_{i_0} - s_{j_0}\|_p$. Moreover, if $p$ does not divide the numerator or denominator of either $s_{i_0} - s_{j_0}$ or $t_{k_0} - t_{l_0}$, then $\|s_{i_0} - s_{j_0}\|_p = \|t_{k_0} - t_{l_0}\|_p = 0$ and thus $f(p) = 0$. It follows that $f(p) = 0$ for all but finitely many primes.

We can now define $r = \prod_p p^{-f(p)}$, where the product is over all primes. For any $i, j$, we have $\|s_i - s_j\|_p \geq f(p)$ for all $p$ by construction, and so $(s_i - s_j)r$ is an integer. On the other hand, for any $k, l$ and any prime $p$, $\|t_k - t_l\|_p \geq -\|s_i - s_j\|_p$ for all $i, j$ by the claim, and so $\|t_k - t_l\|_p \geq -f(p)$. It follows that $(t_k - t_l)/r$ is an integer for all $k, l$, whence $r$ is the desired rational number.

Solution 3 (Based on work by Evan O'Dorney). As in the first solution, we reduce to the case $s_1 = t_1 = 0$ and conclude that $s_i t_j + s_j t_i$ is an integer for $i, j \geq 2$. For each positive integer $n \geq 2$, let $S_n$ be the set of rational numbers $r$ such that $s_i r$ and $t_i/r$ are integers for $i = 2, 3, \dots, n$. Clearly, we have $S_{n+1} \subseteq S_n$. On the other hand, since neither sequence is constant, there exists some $n$ such that $s_i$ and $t_j$ are nonzero for some indices $i, j$ in $\{2, 3, \dots, n\}$. If we write $s_i = a/b$ and $t_j = c/d$ in lowest terms, then for any $r = e/f \in S_n$ written in lowest terms, $f$ must divide $a$ and $e$ must divide $c$. This proves that $S_n$ is a finite set, and therefore so is $S_k$ for $k > n$.

Now form the polynomials
$$P(x) = s_2 + s_3 x + \dots + s_n x^{n-1} \quad \text{and} \quad Q(x) = t_2 + t_3 x + \dots + t_n x^{n-1}$$
and note that $P(x)Q(x)$ has integer coefficients (because its coefficients are sums of terms of the form $s_i t_j + s_j t_i$ and $s_i t_i$). By Gauss' lemma, there exists a rational number $r$ such that $P(x)r$ and $Q(x)/r$ have integer coefficients, so $r \in S_n$ and $S_n$ is non-empty.

We now have a decreasing sequence of finite sets $S_2 \supseteq S_3 \supseteq \dots$, each of which is non-empty. Their intersection must then be non-empty (e.g., because there is a least cardinality, and once that is achieved the sets are all equal). For any $r$ in that intersection, then, we have that $s_i r$ and $t_i/r$ are integers for all $i$, giving the desired conclusion.