Difference between revisions of "1995 AIME Problems/Problem 8"
m (outline) |
(expand) |
||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | For how many ordered pairs of positive | + | For how many ordered pairs of positive [[integer]]s <math>(x,y),</math> with <math>y<x\le 100,</math> are both <math>\frac xy</math> and <math>\frac{x+1}{y+1}</math> integers? |
== Solution == | == Solution == | ||
| − | Since <math>y|x</math>, <math>y+1|x+1</math>, then <math>\text{gcd}\,(y,x)=y</math> and <math>\text{gcd}\,(y+1,x+1)=y+1</math>. By the [[Euclidean | + | Since <math>y|x</math>, <math>y+1|x+1</math>, then <math>\text{gcd}\,(y,x)=y</math> (the bars indicate [[divisibility]]) and <math>\text{gcd}\,(y+1,x+1)=y+1</math>. By the [[Euclidean algorithm]], these can be rewritten respectively as <math>\text{gcd}\,(y,x-y)=y</math> and <math>\text{gcd}\, (y+1,x-y)=y+1</math>, which implies that both <math>y,y+1 | x-y</math>. Also, as <math>\text{gcd}\,(y,y+1) = 1</math>, it follows that <math>y(y+1)|x-y</math>. {{ref|1}} |
| − | <cmath>\sum_{y=1}^{99} \left\lfloor\frac{100-y}{y(y+1)} \right\rfloor = \boxed{085}</cmath> | + | |
| + | Thus, for a given value of <math>y</math>, we need the number of multiples of <math>y(y+1)</math> from <math>0</math> to <math>100-y</math> (as <math>x \le 100</math>). It follows that there are <math>\left\lfloor\frac{100-y}{y(y+1)} \right\rfloor</math> satisfactory positive integers for all integers <math>y \le 100</math>. The answer is | ||
| + | |||
| + | <cmath>\sum_{y=1}^{99} \left\lfloor\frac{100-y}{y(y+1)} \right\rfloor = 49 + 16 + 8 + 4 + 3 + 2 + 1 + 1 + 1 = \boxed{085}.</cmath> | ||
| + | |||
| + | <br /><br />{{note|1}} Another way of stating this is to note that if <math>\frac{x}{y}</math> and <math>\frac{x+1}{y+1}</math> are integers, then <math>\frac{x}{y} - 1 = \frac{x-y}{y}</math> and <math>\frac{x+1}{y+1} - 1 = \frac{x-y}{y+1}</math> must be integers. Since <math>y</math> and <math>y+1</math> cannot share common prime factors, it follows that <math>\frac{x-y}{y(y+1)}</math> must also be an integer. | ||
== See also == | == See also == | ||
{{AIME box|year=1995|num-b=7|num-a=9}} | {{AIME box|year=1995|num-b=7|num-a=9}} | ||
| + | |||
| + | [[Category:Intermediate Number Theory Problems]] | ||
Revision as of 18:11, 29 July 2008
Problem
For how many ordered pairs of positive integers 
with 
are both 
and 
integers?
Solution
Since 
, 
, then 
(the bars indicate divisibility) and 
. By the Euclidean algorithm, these can be rewritten respectively as 
and 
, which implies that both 
. Also, as 
, it follows that 
. [1]
Thus, for a given value of 
, we need the number of multiples of 
from 
to 
(as 
). It follows that there are 
satisfactory positive integers for all integers 
. The answer is
![\[\sum_{y=1}^{99} \left\lfloor\frac{100-y}{y(y+1)} \right\rfloor = 49 + 16 + 8 + 4 + 3 + 2 + 1 + 1 + 1 = \boxed{085}.\]](http://latex.artofproblemsolving.com/0/b/0/0b08a1c5231be8c3d8b6b09431be4f2db16f701b.png)
^ Another way of stating this is to note that if 
and are integers, then 
and 
must be integers. Since and 
cannot share common prime factors, it follows that 
must also be an integer.
See also
| 1995 AIME (Problems • Answer Key • Resources) | ||
| Preceded by Problem 7 |
Followed by Problem 9 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
