Difference between revisions of "1995 AIME Problems/Problem 8"
m |
m (outline) |
||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | For how many ordered pairs of positive integers <math> | + | For how many ordered pairs of positive integers <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 Algorithm]], these can be rewritten as <math>\text{gcd}\,(y,x-y)=y</math> and <math>\text{gcd}\, (y+1,x-y)=y+1</math>, which implies that <math>y,y+1 | x-y</math>. Also, <math>\text{gcd}\,(y,y+1) = 1</math>, so <math>\frac{x-y}{y(y+1)}</math> must be an integer. Substituting the upper bound of <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. The answer is | ||
| + | <cmath>\sum_{y=1}^{99} \left\lfloor\frac{100-y}{y(y+1)} \right\rfloor = \boxed{085}</cmath> | ||
== See also == | == See also == | ||
| − | + | {{AIME box|year=1995|num-b=7|num-a=9}} | |
| − | |||
| − | |||
Revision as of 14:26, 15 March 2008
Problem
For how many ordered pairs of positive integers 
with 
are both 
and 
integers?
Solution
Since 
, 
, then 
and 
. By the Euclidean Algorithm, these can be rewritten as 
and 
, which implies that 
. Also, 
, so 
must be an integer. Substituting the upper bound of 
, it follows that there are 
satisfactory positive integers. The answer is
![\[\sum_{y=1}^{99} \left\lfloor\frac{100-y}{y(y+1)} \right\rfloor = \boxed{085}\]](http://latex.artofproblemsolving.com/8/0/1/8017c33b6f9d84ec52dff31f7ee8a73a4433822c.png)
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 | ||
