Difference between revisions of "1995 AIME Problems/Problem 8"
(→Solution 3 (Rigorous, but straightforward)) |
|||
(11 intermediate revisions by 7 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
+ | 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 1== |
+ | 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}} | ||
+ | |||
+ | 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. | ||
+ | |||
+ | == Solution 2== | ||
+ | We know that <math>x \equiv 0 \mod y</math> and <math>x+1 \equiv 0 \mod y+1</math>. | ||
+ | |||
+ | Write <math>x</math> as <math>ky</math> for some integer <math>k</math>. Then, <math>ky+1 \equiv 0\mod y+1</math>. We can add <math>k</math> to each side in order to factor out a <math>y+1</math>. So, <math>ky+k+1 \equiv k \mod y+1</math> or <math>k(y+1)+1 \equiv k \mod y+1</math>. We know that <math>k(y+1) \equiv 0 \mod y+1</math>. We finally achieve the congruence <math>1-k \equiv 0 \mod y+1</math>. | ||
+ | |||
+ | We can now write <math>k</math> as <math>(y+1)a+1</math>. Plugging this back in, if we have a value for <math>y</math>, then <math>x = ky = ((y+1)a+1)y = y(y+1)a+y</math>. We only have to check values of <math>y</math> when <math>y(y+1)<100</math>. This yields the equations <math>x = 2a+1, 6a+2, 12a+3, 20a+4, 30a+5, 42a+6, 56a+7, 72a+8, 90a+9</math>. | ||
+ | |||
+ | Finding all possible values of <math>a</math> such that <math>y<x<100</math>, we get <math>49 + 16 + 8 + 4 + 3 + 2 + 1 + 1 + 1 = \boxed{085}.</math> | ||
+ | |||
+ | ==Solution 3 (Rigorous, but straightforward)== | ||
+ | We use casework: | ||
+ | |||
+ | For <math>y=1</math>, we have <math>3,5,\cdots ,99</math>, or <math>49</math> cases. | ||
+ | |||
+ | For <math>y=2</math>, we have <math>8,14,\cdots ,98</math>, or <math>16</math> cases. | ||
+ | |||
+ | For <math>y=3</math>, we have <math>15,27,\cdots ,99</math>, or <math>8</math> cases. | ||
+ | |||
+ | For <math>y=4</math>, we have <math>24,44\cdots ,84</math>, or <math>4</math> cases. | ||
+ | |||
+ | For <math>y=5</math>, we have <math>35,65,95</math>, or <math>3</math> cases. | ||
+ | |||
+ | For <math>y=6</math>, we have <math>48,90</math>, or <math>2</math> cases. | ||
+ | |||
+ | For <math>y=7</math>, we have <math>63</math>, or <math>1</math> case. | ||
+ | |||
+ | For <math>y=8</math>, we have <math>80</math>, or <math>1</math> case. | ||
+ | |||
+ | For <math>y=9</math>, we have <math>99</math>, or <math>1</math> case. | ||
+ | |||
+ | Adding, we get our final result of <math>\boxed{085}.</math> | ||
+ | |||
+ | Note: In general, all of the solutions for all <math>y</math> are <math>y+by(y+1)</math>, for any <math>b</math> such that <math>y+by(y+1)=x<100</math> | ||
+ | |||
+ | ~SirAppel | ||
+ | |||
+ | Also, note that <math>n+1</math> just starts with <math>(y+1)^2</math>, and adds <math>y(y+1)</math> until it is greater than <math>100</math>. | ||
+ | |||
+ | ~Yiyj1 | ||
== See also == | == See also == | ||
− | + | {{AIME box|year=1995|num-b=7|num-a=9}} | |
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 17:37, 1 January 2024
Contents
Problem
For how many ordered pairs of positive integers with
are both
and
integers?
Solution 1
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
^ 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.
Solution 2
We know that and
.
Write as
for some integer
. Then,
. We can add
to each side in order to factor out a
. So,
or
. We know that
. We finally achieve the congruence
.
We can now write as
. Plugging this back in, if we have a value for
, then
. We only have to check values of
when
. This yields the equations
.
Finding all possible values of such that
, we get
Solution 3 (Rigorous, but straightforward)
We use casework:
For , we have
, or
cases.
For , we have
, or
cases.
For , we have
, or
cases.
For , we have
, or
cases.
For , we have
, or
cases.
For , we have
, or
cases.
For , we have
, or
case.
For , we have
, or
case.
For , we have
, or
case.
Adding, we get our final result of
Note: In general, all of the solutions for all are
, for any
such that
~SirAppel
Also, note that just starts with
, and adds
until it is greater than
.
~Yiyj1
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.