Difference between revisions of "2021 AIME II Problems/Problem 15"
MRENTHUSIASM (talk | contribs) m (→Solution 5 (Basic substitution)) |
Markma2010 (talk | contribs) (→Solution 7) |
||
(28 intermediate revisions by 7 users not shown) | |||
Line 14: | Line 14: | ||
If <math>2 \mid (k+1)^2-n</math>, <math>g(n)</math> returns the same value as <math>f(n)</math>. This is because the recursion once again stops at <math>(k+1)^2</math>. We seek a case in which <math>f(n)<g(n)</math>, so obviously this is not what we want. We want <math>(k+1)^2,n</math> to have a different parity, or <math>n, k</math> have the same parity. When this is the case, <math>g(n)</math> instead returns <math>(k+2)^2-n+g((k+2)^2)=k^2+5k+6-n</math>. | If <math>2 \mid (k+1)^2-n</math>, <math>g(n)</math> returns the same value as <math>f(n)</math>. This is because the recursion once again stops at <math>(k+1)^2</math>. We seek a case in which <math>f(n)<g(n)</math>, so obviously this is not what we want. We want <math>(k+1)^2,n</math> to have a different parity, or <math>n, k</math> have the same parity. When this is the case, <math>g(n)</math> instead returns <math>(k+2)^2-n+g((k+2)^2)=k^2+5k+6-n</math>. | ||
− | Write <math>7f(n)=4g(n)</math>, which simplifies to <math>3k^2+k-10=3n</math>. Notice that we want the | + | Write <math>7f(n)=4g(n)</math>, which simplifies to <math>3k^2+k-10=3n</math>. Notice that we want the LHS expression to be divisible by 3; as a result, <math>k \equiv 1 \pmod{3}</math>. We also want n to be strictly greater than <math>k^2</math>, so <math>k-10>0, k>10</math>. The LHS expression is always even (since <math>3k^2+k-10</math> factors to <math>k(3k+1)-10</math>, and one of <math>k</math> and <math>3k+1</math> will be even), so to ensure that <math>k</math> and <math>n</math> share the same parity, <math>k</math> should be even. Then the least <math>k</math> that satisfies these requirements is <math>k=16</math>, giving <math>n=258</math>. |
Indeed - if we check our answer, it works. Therefore, the answer is <math>\boxed{258}</math>. | Indeed - if we check our answer, it works. Therefore, the answer is <math>\boxed{258}</math>. | ||
Line 29: | Line 29: | ||
f\left((k+1)^2-1\right)&=k+2, \\ | f\left((k+1)^2-1\right)&=k+2, \\ | ||
f\left((k+1)^2-2\right)&=k+3, \\ | f\left((k+1)^2-2\right)&=k+3, \\ | ||
− | &\ | + | & \ \vdots \\ |
f\bigl(\phantom{ }\underbrace{(k+1)^2-p}_{n}\phantom{ }\bigr)&=k+p+1. \hspace{19mm}(2) \\ | f\bigl(\phantom{ }\underbrace{(k+1)^2-p}_{n}\phantom{ }\bigr)&=k+p+1. \hspace{19mm}(2) \\ | ||
\end{align*}</cmath></li><p> | \end{align*}</cmath></li><p> | ||
Line 39: | Line 39: | ||
g\left((k+2)^2-2\right)&=k+4, \\ | g\left((k+2)^2-2\right)&=k+4, \\ | ||
g\left((k+2)^2-4\right)&=k+6, \\ | g\left((k+2)^2-4\right)&=k+6, \\ | ||
− | &\ | + | & \ \vdots \\ |
g\bigl(\phantom{ }\underbrace{(k+2)^2-2q}_{n}\phantom{ }\bigr)&=k+2q+2. \hspace{15.5mm}(4) \\ | g\bigl(\phantom{ }\underbrace{(k+2)^2-2q}_{n}\phantom{ }\bigr)&=k+2q+2. \hspace{15.5mm}(4) \\ | ||
\end{align*}</cmath></li><p> | \end{align*}</cmath></li><p> | ||
Line 73: | Line 73: | ||
==Solution 3== | ==Solution 3== | ||
− | Since <math>n</math> isn't a perfect square, let <math>n=m^2+k</math> with <math>0<k<2m+1</math>. If <math> | + | Since <math>n</math> isn't a perfect square, let <math>n=m^2+k</math> with <math>0<k<2m+1</math>. If <math>k</math> is odd, then <math>f(n)=g(n)</math>. If <math>k</math> is even, then |
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
f(n)&=(m+1)^2-(m^2+k)+(m+1)=3m+2-k, \\ | f(n)&=(m+1)^2-(m^2+k)+(m+1)=3m+2-k, \\ | ||
Line 83: | Line 83: | ||
m&=3k+10. | m&=3k+10. | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | Since <math> | + | Since <math>k</math> is even, <math>m</math> is even. Since <math>k\neq 0</math>, the smallest <math>k</math> is <math>2</math> which produces the smallest <math>n</math>: <cmath>k=2 \implies m=16 \implies n=16^2+2=\boxed{258}.</cmath> |
~Afo | ~Afo | ||
==Solution 4 (Quadratics With Two Variables)== | ==Solution 4 (Quadratics With Two Variables)== | ||
− | To begin, note that if <math>n</math> is a perfect square, <math>f(n)=g(n)</math>, so <math>f(n)/g(n)=1</math>, so we must look at values of <math>n</math> that are not perfect squares (what a surprise). First, let the distance between <math>n</math> and the first perfect square greater than or equal to it be <math>k</math>, making the values of <math>f(n+k)</math> and <math>g(n+k)</math> integers. Using this notation, we see | + | To begin, note that if <math>n</math> is a perfect square, <math>f(n)=g(n)</math>, so <math>f(n)/g(n)=1</math>, so we must look at values of <math>n</math> that are not perfect squares (what a surprise). First, let the distance between <math>n</math> and the first perfect square greater than or equal to it be <math>k</math>, making the values of <math>f(n+k)</math> and <math>g(n+k)</math> integers. Using this notation, we see that <math>f(n)=k+f(n+k)</math>, giving us a formula for the numerator of our ratio. However, since the function of <math>g(n)</math> does not add one to the previous inputs in the function until a perfect square is achieved, but adds values of two, we can not achieve the value of <math>\sqrt{n+k}</math> in <math>g(n)</math> unless <math>k</math> is an even number. However, this is impossible, since if <math>k</math> was an even number, <math>f(n)=g(n)</math>, giving a ratio of one. Thus, <math>k</math> must be an odd number. |
Thus, since <math>k</math> must be an odd number, regardless of whether <math>n</math> is even or odd, to get an integral value in <math>g(n)</math>, we must get to the next perfect square after <math>n+k</math>. To make matters easier, let <math>z^2=n+k</math>. Thus, in <math>g(n)</math>, we want to achieve <math>(z+1)^2</math>. | Thus, since <math>k</math> must be an odd number, regardless of whether <math>n</math> is even or odd, to get an integral value in <math>g(n)</math>, we must get to the next perfect square after <math>n+k</math>. To make matters easier, let <math>z^2=n+k</math>. Thus, in <math>g(n)</math>, we want to achieve <math>(z+1)^2</math>. | ||
Line 122: | Line 122: | ||
Since we want <math>n</math> to be an integer, we know that the <math>LHS</math> should be divisible by five, so, let's assume that we should have <math>m</math> divisible by five. If so, the quantity <math>18k-73</math> must be divisible by five, meaning that <math>k</math> leaves a remainder of one when divided by 5 (if the reader knows LaTeX well enough to write this as a modulo argument, please go ahead and do so!). | Since we want <math>n</math> to be an integer, we know that the <math>LHS</math> should be divisible by five, so, let's assume that we should have <math>m</math> divisible by five. If so, the quantity <math>18k-73</math> must be divisible by five, meaning that <math>k</math> leaves a remainder of one when divided by 5 (if the reader knows LaTeX well enough to write this as a modulo argument, please go ahead and do so!). | ||
− | Thus, we see that to achieve integers <math>n</math> and <math>k</math> that could potentially satisfy the problem statement, we must try the values of <math>k</math> congruent to one modulo five. However, if we recall a statement made earlier in the | + | Thus, we see that to achieve integers <math>n</math> and <math>k</math> that could potentially satisfy the problem statement, we must try the values of <math>k</math> congruent to one modulo five. However, if we recall a statement made earlier in the solution, we see that we can skip all even values of <math>k</math> produced by this modulo argument. |
Also, note that <math>k=1,6</math> won't work, as they are too small, and will give an erroneous value for <math>n</math>. After trying <math>k=11,21,31</math>, we see that <math>k=31</math> will give a value of <math>m=485</math>, which yields <math>n=\boxed{258}</math>, which, if plugged in to for our equations of <math>f(n)</math> and <math>g(n)</math>, will yield the desired ratio, and we're done. | Also, note that <math>k=1,6</math> won't work, as they are too small, and will give an erroneous value for <math>n</math>. After trying <math>k=11,21,31</math>, we see that <math>k=31</math> will give a value of <math>m=485</math>, which yields <math>n=\boxed{258}</math>, which, if plugged in to for our equations of <math>f(n)</math> and <math>g(n)</math>, will yield the desired ratio, and we're done. | ||
Line 128: | Line 128: | ||
Side Note: If any part of this solution is not rigorous, or too vague, please label it in the margin with "needs proof". If you can prove it, please add a lemma to the solution doing so :) | Side Note: If any part of this solution is not rigorous, or too vague, please label it in the margin with "needs proof". If you can prove it, please add a lemma to the solution doing so :) | ||
− | -mathislife52 | + | -Azeem H. (mathislife52) |
==Solution 5 (Basic Substitutions)== | ==Solution 5 (Basic Substitutions)== | ||
− | First of all, if <math>n</math> is a perfect square, <math>f(n)=g(n)=\sqrt{n}</math> and their quotient is <math>1.</math> So for the rest of this solution, assume <math>n</math> is not a perfect square. | + | First of all, if <math>n</math> is a perfect square, <math>f(n)=g(n)=\sqrt{n}</math> and their quotient is <math>1.</math> So, for the rest of this solution, assume <math>n</math> is not a perfect square. |
Let <math>a^2</math> be the smallest perfect square greater than <math>n</math> and let <math>b^2</math> be the smallest perfect square greater than <math>n</math> with the same parity as <math>n,</math> and note that either <math>b=a</math> or <math>b=a+1.</math> Notice that <math>(a-1)^2 < n < a^2.</math> | Let <math>a^2</math> be the smallest perfect square greater than <math>n</math> and let <math>b^2</math> be the smallest perfect square greater than <math>n</math> with the same parity as <math>n,</math> and note that either <math>b=a</math> or <math>b=a+1.</math> Notice that <math>(a-1)^2 < n < a^2.</math> | ||
Line 137: | Line 137: | ||
With a bit of inspection, it becomes clear that <math>f(n) = a+(a^2-n)</math> and <math>g(n) = b+(b^2-n).</math> | With a bit of inspection, it becomes clear that <math>f(n) = a+(a^2-n)</math> and <math>g(n) = b+(b^2-n).</math> | ||
− | If <math>a</math> and <math>n</math> have the same parity, we get <math>a=b</math> so <math>f(n) = g(n)</math> and their quotient is <math>1.</math> So for the rest of this solution, we let <math>a</math> and <math>n</math> have opposite parity. We have two cases to consider. | + | If <math>a</math> and <math>n</math> have the same parity, we get <math>a=b</math> so <math>f(n) = g(n)</math> and their quotient is <math>1.</math> So, for the rest of this solution, we let <math>a</math> and <math>n</math> have opposite parity. We have two cases to consider. |
Case 1: <math>n</math> is odd and <math>a</math> is even | Case 1: <math>n</math> is odd and <math>a</math> is even | ||
Line 155: | Line 155: | ||
The pair <math>(2,5)</math> gives <math>a=2(2)+1=5</math> and <math>n=5^2-(2(5)+1)=14.</math> But <math>4^2<14<5^2</math> is clearly false, so we discard this case. | The pair <math>(2,5)</math> gives <math>a=2(2)+1=5</math> and <math>n=5^2-(2(5)+1)=14.</math> But <math>4^2<14<5^2</math> is clearly false, so we discard this case. | ||
− | The pair <math>(5,10)</math> gives <math>a=2(5)+1=11</math> and <math>n=11^2-(2(10)+1)=100</math> which is a perfect square and therefore can be discarded. | + | The pair <math>(5,10)</math> gives <math>a=2(5)+1=11</math> and <math>n=11^2-(2(10)+1)=100,</math> which is a perfect square and therefore can be discarded. |
− | The pair <math>(8,15)</math> gives <math>a=2(8)+1=17</math> and <math>n=17^2-(2(15)+1)=258</math> which is between <math>16^2</math> and <math>17^2</math> so it is our smallest solution. | + | The pair <math>(8,15)</math> gives <math>a=2(8)+1=17</math> and <math>n=17^2-(2(15)+1)=258,</math> which is between <math>16^2</math> and <math>17^2</math> so it is our smallest solution. |
− | So <math>\boxed{258}</math> is the correct answer. | + | So, <math>\boxed{258}</math> is the correct answer. |
~mc21s | ~mc21s | ||
+ | |||
+ | ==Solution 6 (Short) == | ||
+ | |||
+ | Say the answer is in the form n^2-x, then x must be odd or else f(x) = g(x). Say y = n^2-x. f(y) = x+n, g(y) = 3n+2+x. Because f(y)/g(y) = 4*(an integer)/7*(an integer), f(y) is 4*(an integer) so n must be odd or else f(y) would be odd. Solving for x in terms of n gives integer x = (5/3)n+8/3 which means n is 2 mod 3, because n is also odd, n is 5 mod 6. x must be less than 2n-1 or else the minimum square above y would be (n-1)^2. We set an inequality | ||
+ | (5/3)n+8/3<2n-1 => 5n+8<6n-3 => n>11. | ||
+ | Since n is 5 mod 6, n = 17 and x = 31 giving 17^2-31 = <math>\boxed{258}</math>. | ||
+ | |||
+ | ~mathophobia | ||
+ | |||
+ | ==Solution 7== | ||
+ | |||
+ | Define a nonnegative integer <math>k</math> such that <math>g(n)-f(n)</math> = <math>k</math>. Since <math>\frac{f(n)}{g(n)} = \frac{4}{7},</math> <math>k</math> is a positive integer. Now, suppose 3 consecutive integers <math>a-1</math>, <math>a</math>, and <math>a+1</math>, and <math>(a-1)^2 < n < a^2</math>. When <math>g(n) > f(n)</math>, <math>g(n)</math> must have a different parity than <math>a</math>, so that <math>f(n)</math>'s recursive sequence ends on <math>a^2</math>, while <math>g(n)</math> continues to <math>(a+1)^2</math>. If this condition is satisfied, we can figure out the value of <math>k</math> based on <math>a</math>. According to the definitions of <math>f(n)</math> and <math>g(n)</math>, <math>f(n) = a+a^2-n,</math> and <math>g(n) = (a+1)+(a+1)^2-n,</math> which gives <math>k = 2a+2</math>. And because of <math>f(n) + k = g(n)</math>, <math>\frac{k}{g(n)} = \frac{3}{7},</math> so cross multiplying gives <math>3g(n) = 14a+14</math>. This means that <math>14a+14</math> is divisible by 3, and thus <math>a \equiv 2 \pmod{3}</math>. The final thing left is to find the smallest <math>a</math> such that the corresponding value of <math>g(n)</math> exist. Simple guess and check should give that the smallest value of <math>a</math> is <math>a = 17</math>, which yields an answer of <math> n = \boxed{258}</math>. | ||
+ | |||
+ | ~ Marchk26 | ||
==Video Solution== | ==Video Solution== | ||
https://youtu.be/tRVe2bKwIY8 | https://youtu.be/tRVe2bKwIY8 | ||
~Mathematical Dexterity | ~Mathematical Dexterity | ||
+ | |||
+ | ==Video Solution by Interstigation== | ||
+ | https://youtu.be/WmEmwt3xwoo | ||
+ | |||
+ | ~Interstigation | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2021|n=II|num-b=14|after=Last Question}} | {{AIME box|year=2021|n=II|num-b=14|after=Last Question}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 13:23, 16 August 2024
Contents
Problem
Let and
be functions satisfying
and
for positive integers
. Find the least positive integer
such that
.
Solution 1
Consider what happens when we try to calculate where n is not a square. If
for (positive) integer k, recursively calculating the value of the function gives us
. Note that this formula also returns the correct value when
, but not when
. Thus
for
.
If ,
returns the same value as
. This is because the recursion once again stops at
. We seek a case in which
, so obviously this is not what we want. We want
to have a different parity, or
have the same parity. When this is the case,
instead returns
.
Write , which simplifies to
. Notice that we want the LHS expression to be divisible by 3; as a result,
. We also want n to be strictly greater than
, so
. The LHS expression is always even (since
factors to
, and one of
and
will be even), so to ensure that
and
share the same parity,
should be even. Then the least
that satisfies these requirements is
, giving
.
Indeed - if we check our answer, it works. Therefore, the answer is .
-Ross Gao
Solution 2 (Four Variables)
We consider and
separately:
We restrict
in which
for some positive integer
or
for some integer
such that
By recursion, we get
If
and
have the same parity, then we get
by a similar process from
This contradicts the precondition
Therefore,
and
must have different parities, from which
and
must have the same parity.
It follows that
or
for some integer
such that
By recursion, we get
- Answer
By
and
we have
From
and
equating the expressions for
gives
Solving for
produces
We substitute
into
then simplify, cross-multiply, and rearrange:
Since
we know that
must be divisible by
and
must be divisible by
Recall that the restrictions on
and
are
and
respectively. Substituting
into either inequality gives
Combining all these results produces
To minimize
in either
or
we minimize
so we minimize
and
in
From
and
we construct the following table:
Finally, we have
Substituting this result into either
or
generates
- Remark
We can verify that
~MRENTHUSIASM
Solution 3
Since isn't a perfect square, let
with
. If
is odd, then
. If
is even, then
from which
Since
is even,
is even. Since
, the smallest
is
which produces the smallest
:
~Afo
Solution 4 (Quadratics With Two Variables)
To begin, note that if is a perfect square,
, so
, so we must look at values of
that are not perfect squares (what a surprise). First, let the distance between
and the first perfect square greater than or equal to it be
, making the values of
and
integers. Using this notation, we see that
, giving us a formula for the numerator of our ratio. However, since the function of
does not add one to the previous inputs in the function until a perfect square is achieved, but adds values of two, we can not achieve the value of
in
unless
is an even number. However, this is impossible, since if
was an even number,
, giving a ratio of one. Thus,
must be an odd number.
Thus, since must be an odd number, regardless of whether
is even or odd, to get an integral value in
, we must get to the next perfect square after
. To make matters easier, let
. Thus, in
, we want to achieve
.
Expanding and substituting in the fact that
yields:
Thus, we must add the quantity to
to achieve a integral value in the function
. Thus.
However, note that the quantity within the square root is just , and so:
Thus,
Since we want this quantity to equal , we can set the above equation equal to this number and collect all the variables to one side to achieve
Substituting back in that , and then separating variables and squaring yields that
Now, if we treat as a constant, we can use the quadratic formula in respect to
to get an equation for
in terms of
(without all the squares). Doing so yields
Now, since and
are integers, we want the quantity within the square root to be a perfect square. Note that
. Thus, assume that the quantity within the root is equal to the perfect square,
. Thus, after using a difference of squares, we have
Since we want
to be an integer, we know that the
should be divisible by five, so, let's assume that we should have
divisible by five. If so, the quantity
must be divisible by five, meaning that
leaves a remainder of one when divided by 5 (if the reader knows LaTeX well enough to write this as a modulo argument, please go ahead and do so!).
Thus, we see that to achieve integers and
that could potentially satisfy the problem statement, we must try the values of
congruent to one modulo five. However, if we recall a statement made earlier in the solution, we see that we can skip all even values of
produced by this modulo argument.
Also, note that won't work, as they are too small, and will give an erroneous value for
. After trying
, we see that
will give a value of
, which yields
, which, if plugged in to for our equations of
and
, will yield the desired ratio, and we're done.
Side Note: If any part of this solution is not rigorous, or too vague, please label it in the margin with "needs proof". If you can prove it, please add a lemma to the solution doing so :)
-Azeem H. (mathislife52)
Solution 5 (Basic Substitutions)
First of all, if is a perfect square,
and their quotient is
So, for the rest of this solution, assume
is not a perfect square.
Let be the smallest perfect square greater than
and let
be the smallest perfect square greater than
with the same parity as
and note that either
or
Notice that
With a bit of inspection, it becomes clear that and
If and
have the same parity, we get
so
and their quotient is
So, for the rest of this solution, we let
and
have opposite parity. We have two cases to consider.
Case 1: is odd and
is even
Here, we get for some positive integer
Then,
We let
for some positive integer
so
and
We set cross multiply, and rearrange to get
Since
and
are integers, the LHS will always be even and the RHS will always be odd, and thus, this case yields no solutions.
Case 2: is even and
is odd
Here, we get for some positive ineger
Then,
We let
for some positive integer
so
and
We set cross multiply, and rearrange to get
or
Since
and
are integers,
must be a multiple of
Some possible solutions for
with the least
and
are
and
We wish to minimize since
One thing to keep in mind is the initial assumption
The pair gives
and
But
is clearly false, so we discard this case.
The pair gives
and
which is a perfect square and therefore can be discarded.
The pair gives
and
which is between
and
so it is our smallest solution.
So, is the correct answer.
~mc21s
Solution 6 (Short)
Say the answer is in the form n^2-x, then x must be odd or else f(x) = g(x). Say y = n^2-x. f(y) = x+n, g(y) = 3n+2+x. Because f(y)/g(y) = 4*(an integer)/7*(an integer), f(y) is 4*(an integer) so n must be odd or else f(y) would be odd. Solving for x in terms of n gives integer x = (5/3)n+8/3 which means n is 2 mod 3, because n is also odd, n is 5 mod 6. x must be less than 2n-1 or else the minimum square above y would be (n-1)^2. We set an inequality
(5/3)n+8/3<2n-1 => 5n+8<6n-3 => n>11.
Since n is 5 mod 6, n = 17 and x = 31 giving 17^2-31 = .
~mathophobia
Solution 7
Define a nonnegative integer such that
=
. Since
is a positive integer. Now, suppose 3 consecutive integers
,
, and
, and
. When
,
must have a different parity than
, so that
's recursive sequence ends on
, while
continues to
. If this condition is satisfied, we can figure out the value of
based on
. According to the definitions of
and
,
and
which gives
. And because of
,
so cross multiplying gives
. This means that
is divisible by 3, and thus
. The final thing left is to find the smallest
such that the corresponding value of
exist. Simple guess and check should give that the smallest value of
is
, which yields an answer of
.
~ Marchk26
Video Solution
https://youtu.be/tRVe2bKwIY8 ~Mathematical Dexterity
Video Solution by Interstigation
~Interstigation
See Also
2021 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 14 |
Followed by Last Question | |
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.