Difference between revisions of "2021 AIME II Problems/Problem 15"
Mathislife52 (talk | contribs) (→Solution 4) |
Mathislife52 (talk | contribs) (→Solution 4) |
||
Line 88: | Line 88: | ||
==Solution 4== | ==Solution 4== | ||
− | 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 than <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 | + | 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 than <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. |
==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}} |
Revision as of 18:29, 3 June 2021
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
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 (why?), so to ensure that k and n share the same parity, k should be even. Then the least k 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 starting from
we get
by a similar process. 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,
Since
is even,
is even. Since
, the smallest
is
which produces the smallest
.
~Afo
Video Solution
Solution 4
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 than
, 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.
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.