Difference between revisions of "2009 USAMO Problems/Problem 6"

Revision as of 11:50, 21 August 2020

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.

@@ Line 3: / Line 3: @@
 == Solution ==
-{{solution}}
+Suppose the <math>s_i</math> can be represented as <math>\frac{a_i}{b_i}</math> for every <math>i</math>, and suppose <math>t_i</math> can be represented as <math>\frac{c_i}{d_i}</math>. Let's start with only the first two terms in the two sequences, <math>s_1</math> and <math>s_2</math> for sequence <math>s</math> and <math>t_1</math> and <math>t_2</math> for sequence <math>t</math>. Then by the conditions of the problem, we have <math>(s_2 - s_1)(t_2 - t_1)</math> is an integer, or <math>(\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 </math>r = \frac{b_1 b_2}{d_1 d_2}<math>, because the least common denominator of </math>s_2 - s_1<math> is </math>b_1 b_2<math> and of </math>t_2 - t_1<math> is </math>d_1 d_2<math>, and multiplying or dividing appropriately by </math>\frac{b_1 b_2}{d_1 d_2}<math> will always give an integer.
+Now suppose we kept adding </math>s_i<math> and </math>t_i<math> until we get to </math>s_m = \frac{a_m}{b_m}<math> in sequence </math>s<math> and </math>t_m = \frac{c_m}{d_m}<math> in sequence </math>t<math>, where </math>m<math> is a positive integer. At this point, we will have </math>r<math> = </math>\frac{\prod_{n=1}^{m}b_n}{\prod_{n=1}^{m}d_n}<math>, because these are the least common denominators of the two sequences up to </math>m<math>. As we keep adding </math>s_i<math> and </math>t_i<math>, </math>r<math> will always have value </math>\frac{\prod_{n=1}^{m}b_n}{\prod_{n=1}^{m}d_n}$, and we are done.
 == See Also ==
 {{USAMO newbox|year=2009|num-b=5|after=Last question}}
-[[Category:Problems with no solution]]
 [[Category:Olympiad Number Theory Problems]]
 {{MAA Notice}}

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

Difference between revisions of "2009 USAMO Problems/Problem 6"

Revision as of 11:50, 21 August 2020

Problem

Solution

See Also