Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2009 USAMO Problems/Problem 6"
 
(One intermediate revision by the same user not shown)
Line 5: Line 5:
 
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})</math> 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.  
 
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})</math> 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}</math>, and we are done.
+
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> so that <math>(t_m - t_i)(s_m - s_i)</math> is an integer for all <math>i</math> with <math>1 \le i < m</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}</math>, and we are done.
  
 
== See Also ==
 
== See Also ==

Latest revision as of 11:19, 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 $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$ so that $(t_m - t_i)(s_m - s_i)$ is an integer for all $i$ with $1 \le i < m$, 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.

See Also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_USAMO_Problems/Problem_6&oldid=132292"