2009 USAMO Problems/Problem 6

Problem

Let $s_1, s_2, s_3, \ldots$ be an infinite, nonconstant sequence of rational numbers, meaning it is not the case that $s_1 = s_2 = s_3 = \cdots.$ Suppose that $t_1, t_2, t_3, \ldots$ is also an infinite, nonconstant sequence of rational numbers with the property that $(s_i - s_j)(t_i - t_j)$ is an integer for all $i$ and $j$ . Prove that there exists a rational number $r$ such that $(s_i - s_j)r$ and $(t_i - t_j)/r$ are integers for all $i$ and $j$ .

Solution

Suppose the $s_i$ can be represented as $\frac{a_i}{b_i}$ for every $i$ , and suppose $t_i$ can be represented as $\frac{c_i}{d_i}$ . Let's start with only the first two terms in the two sequences, $s_1$ and $s_2$ for sequence $s$ and $t_1$ and $t_2$ for sequence $t$ . Then by the conditions of the problem, we have $(s_2 - s_1)(t_2 - t_1)$ is an integer, or $(\frac{a_2}{b_2} - \frac{a_1}{b_1})(\frac{c_2}{d_2} - \frac{c_1}{d_1}) is an integer. Now we can set$ r = \frac{b_1 b_2}{d_1 d_2} $, because the least common denominator of$ s_2 - s_1 $is$ b_1 b_2 $and of$ t_2 - t_1 $is$ d_1 d_2 $, and multiplying or dividing appropriately by$ \frac{b_1 b_2}{d_1 d_2}$will always give an integer.

Now suppose we kept adding$ (Error compiling LaTeX. Unknown error_msg)s_i $and$ t_i $until we get to$ s_m = \frac{a_m}{b_m} $in sequence$ s $and$ t_m = \frac{c_m}{d_m} $in sequence$ t $, where$ m $is a positive integer. At this point, we will have$ r $=$ \frac{\prod_{n=1}^{m}b_n}{\prod_{n=1}^{m}d_n} $, because these are the least common denominators of the two sequences up to$ m $. As we keep adding$ s_i $and$ t_i $,$ r $will always have value$ \frac{\prod_{n=1}^{m}b_n}{\prod_{n=1}^{m}d_n}$, and we are done.

2009 USAMO (Problems • Resources)
Preceded by Problem 5	Followed by Last question
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

2009 USAMO Problems/Problem 6

Problem

Solution

See Also