Difference between revisions of "1985 AIME Problems/Problem 13"
m |
Adam zheng (talk | contribs) m (→Solution 4: - typo fix) |
||
(20 intermediate revisions by 16 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | The numbers in the sequence <math>101</math>, <math>104</math>, <math>109</math>, <math>116</math>,<math>\ldots</math> are of the form <math>a_n=100+n^2</math>, where <math>n=1,2,3,\ldots</math> For each <math>n</math>, let <math>d_n</math> be the greatest common divisor of <math>a_n</math> and <math>a_{n+1}</math>. Find the maximum value of <math>d_n</math> as <math>n</math> ranges through the positive | + | The numbers in the [[sequence]] <math>101</math>, <math>104</math>, <math>109</math>, <math>116</math>,<math>\ldots</math> are of the form <math>a_n=100+n^2</math>, where <math>n=1,2,3,\ldots</math> For each <math>n</math>, let <math>d_n</math> be the greatest common divisor of <math>a_n</math> and <math>a_{n+1}</math>. Find the maximum value of <math>d_n</math> as <math>n</math> ranges through the [[positive integer]]s. |
− | == Solution == | + | == Solution 1== |
− | If <math>(x,y)</math> denotes the greatest common divisor of <math>x</math> and <math>y</math>, then we have <math>d_n=(a_n,a_{n+1})=(100+n^2,100+n^2+2n+1)</math>. Now assuming that <math>d_n</math> divides <math>100+n^2</math>, it must divide <math>2n+1</math> if it is going to divide the entire expression <math>100+n^2+2n+1</math>. | + | If <math>(x,y)</math> denotes the [[greatest common divisor]] of <math>x</math> and <math>y</math>, then we have <math>d_n=(a_n,a_{n+1})=(100+n^2,100+n^2+2n+1)</math>. Now assuming that <math>d_n</math> [[divisor | divides]] <math>100+n^2</math>, it must divide <math>2n+1</math> if it is going to divide the entire [[expression]] <math>100+n^2+2n+1</math>. |
− | Thus the equation turns into <math>d_n=(100+n^2,2n+1)</math>. Now note that since <math>2n+1</math> is odd for integral <math>n</math>, we can multiply the left integer, <math>100+n^2</math>, by a | + | Thus the [[equation]] turns into <math>d_n=(100+n^2,2n+1)</math>. Now note that since <math>2n+1</math> is [[odd integer | odd]] for [[integer | integral]] <math>n</math>, we can multiply the left integer, <math>100+n^2</math>, by a power of two without affecting the greatest common divisor. Since the <math>n^2</math> term is quite restrictive, let's multiply by <math>4</math> so that we can get a <math>(2n+1)^2</math> in there. |
So <math>d_n=(4n^2+400,2n+1)=((2n+1)^2-4n+399,2n+1)=(-4n+399,2n+1)</math>. It simplified the way we wanted it to! | So <math>d_n=(4n^2+400,2n+1)=((2n+1)^2-4n+399,2n+1)=(-4n+399,2n+1)</math>. It simplified the way we wanted it to! | ||
− | Now using similar techniques we can write <math>d_n=(-2(2n+1)+401,2n+1)=(401,2n+1)</math>. Thus the | + | Now using similar techniques we can write <math>d_n=(-2(2n+1)+401,2n+1)=(401,2n+1)</math>. Thus <math>d_n</math> must divide <math>\boxed{401}</math> for every single <math>n</math>. This means the largest possible value for <math>d_n</math> is <math>401</math>, and we see that it can be achieved when <math>n = 200</math>. |
+ | == Solution 2 == | ||
+ | We know that <math>a_n = 100+n^2</math> and <math>a_{n+1} = 100+(n+1)^2 = 100+ n^2+2n+1</math>. Since we want to find the GCD of <math>a_n</math> and <math>a_{n+1}</math>, we can use the [[Euclidean algorithm]]: | ||
+ | <math>a_{n+1}-a_n = 2n+1</math> | ||
+ | |||
+ | Now, the question is to find the GCD of <math>2n+1</math> and <math>100+n^2</math>. | ||
+ | We subtract <math>2n+1</math> <math>100</math> times from <math>100+n^2</math>. | ||
+ | <cmath>(100+n^2)-100(2n+1)</cmath> | ||
+ | <cmath>=n^2+100-200n-100</cmath> | ||
+ | This leaves us with <cmath>n^2-200n.</cmath> | ||
+ | Factoring, we get <cmath>n(n-200)</cmath> | ||
+ | Because <math>n</math> and <math>2n+1</math> will be coprime, the only thing stopping the GCD from being <math>1</math> is <math>n-200.</math> | ||
+ | We want this to equal 0, because that will maximize our GCD. | ||
+ | Solving for <math>n</math> gives us <math>n=200</math>. The last remainder is 0, thus <math>200*2+1 = \boxed{401}</math> is our GCD. | ||
+ | |||
+ | == Solution 3== | ||
+ | If Solution 2 is not entirely obvious, our answer is the max possible range of <math>\frac{x(x-200)}{2x+1}</math>. Using the Euclidean Algorithm on <math>x</math> and <math>2x+1</math> yields that they are relatively prime. Thus, the only way the GCD will not be 1 is if the<math> x-200</math> term share factors with the <math>2x+1</math>. Using the Euclidean Algorithm, <math>\gcd(x-200,2x+1)=\gcd(x-200,2x+1-2(x-200))=\gcd(x-200,401)</math>. Thus, the max GCD is 401. | ||
+ | |||
+ | ==Solution 4== | ||
+ | We can just plug in Euclidean algorithm, to go from <math>\gcd(n^2 + 100, n^2 + 2n + 101)</math> to <math>\gcd(n^2 + 100, 2n + 1)</math> to <math>\gcd(n^2 + 100 - 100(2n + 1), 2n + 1)</math> to get <math>\gcd(n^2 - 200n, 2n + 1)</math>. Now we know that no matter what, <math>n</math> is relatively prime to <math>2n + 1</math>. Therefore the equation can be simplified to: <math>\gcd(n - 200, 2n + 1)</math>. Subtracting <math>2n - 400</math> from <math>2n + 1</math> results in <math>\gcd(n - 200,401)</math>. The greatest possible value of this is <math>\boxed{401}</math>, and happens when <math>n \equiv 200 \pmod{401}</math>. | ||
+ | |||
+ | == Video Solution by OmegaLearn == | ||
+ | https://youtu.be/yh70NBCxQzg?t=752 | ||
+ | |||
+ | ~ pi_is_3.14 | ||
== See also == | == See also == | ||
− | * [[ | + | {{AIME box|year=1985|num-b=12|num-a=14}} |
+ | * [[AIME Problems and Solutions]] | ||
+ | * [[American Invitational Mathematics Examination]] | ||
+ | * [[Mathematics competition resources]] | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] |
Latest revision as of 20:04, 6 March 2024
Contents
Problem
The numbers in the sequence ,
,
,
,
are of the form
, where
For each
, let
be the greatest common divisor of
and
. Find the maximum value of
as
ranges through the positive integers.
Solution 1
If denotes the greatest common divisor of
and
, then we have
. Now assuming that
divides
, it must divide
if it is going to divide the entire expression
.
Thus the equation turns into . Now note that since
is odd for integral
, we can multiply the left integer,
, by a power of two without affecting the greatest common divisor. Since the
term is quite restrictive, let's multiply by
so that we can get a
in there.
So . It simplified the way we wanted it to!
Now using similar techniques we can write
. Thus
must divide
for every single
. This means the largest possible value for
is
, and we see that it can be achieved when
.
Solution 2
We know that and
. Since we want to find the GCD of
and
, we can use the Euclidean algorithm:
Now, the question is to find the GCD of and
.
We subtract
times from
.
This leaves us with
Factoring, we get
Because
and
will be coprime, the only thing stopping the GCD from being
is
We want this to equal 0, because that will maximize our GCD.
Solving for
gives us
. The last remainder is 0, thus
is our GCD.
Solution 3
If Solution 2 is not entirely obvious, our answer is the max possible range of . Using the Euclidean Algorithm on
and
yields that they are relatively prime. Thus, the only way the GCD will not be 1 is if the
term share factors with the
. Using the Euclidean Algorithm,
. Thus, the max GCD is 401.
Solution 4
We can just plug in Euclidean algorithm, to go from to
to
to get
. Now we know that no matter what,
is relatively prime to
. Therefore the equation can be simplified to:
. Subtracting
from
results in
. The greatest possible value of this is
, and happens when
.
Video Solution by OmegaLearn
https://youtu.be/yh70NBCxQzg?t=752
~ pi_is_3.14
See also
1985 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |