Difference between revisions of "2021 AIME II Problems/Problem 15"
MRENTHUSIASM (talk | contribs) (→Solution 2 (More Variables)) |
MRENTHUSIASM (talk | contribs) m (→Solution 2 (More Variables)) |
||
Line 57: | Line 57: | ||
p&<q-1. &(9) | p&<q-1. &(9) | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
+ | Alternatively, starting with <math>k^2=\underbrace{(k+2)^2-2q}_{\text{by }(3)}</math> also produces the same result. | ||
To minimize <math>n,</math> we should minimize <math>k.</math> By <math>(6),(8),</math> and <math>(9),</math> we should minimize <math>p</math> and <math>q.</math> From <math>(7),</math> we construct the following table: | To minimize <math>n,</math> we should minimize <math>k.</math> By <math>(6),(8),</math> and <math>(9),</math> we should minimize <math>p</math> and <math>q.</math> From <math>(7),</math> we construct the following table: | ||
<cmath>\begin{array}{c|c|c} | <cmath>\begin{array}{c|c|c} | ||
Line 68: | Line 69: | ||
\geq41 & \geq44 & \checkmark \\ | \geq41 & \geq44 & \checkmark \\ | ||
\end{array}</cmath> | \end{array}</cmath> | ||
− | We have <math>(p,q)=(31,33).</math> Substituting this result into <math>(6)</math> | + | We have <math>(p,q)=(31,33).</math> Substituting this result into <math>(6)</math> gives <math>k=16.</math> Finally, substituting everything into either <math>(1)</math> or <math>(3)</math> generates <math>n=\boxed{258}.</math> |
<u><b>Remark</b></u> | <u><b>Remark</b></u> |
Revision as of 06:44, 12 May 2021
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 (More Variables)
We restrict in which
for some positive integer
or
for some nonnegative integer
By observations, we get
If
and
have the same parity, then starting with
we get
by a similar process. This contradicts the precondition
Therefore,
and
must have different parities, from which
and
must have the same parity.
Along with the earlier restriction, note that or
for some positive integer
By observations, we get
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
Furthermore, rewriting the restriction
in terms of
and
gives
Alternatively, starting with
also produces the same result.
To minimize
we should minimize
By
and
we should minimize
and
From
we construct the following table:
We have
Substituting this result into
gives
Finally, substituting everything into either
or
generates
Remark
We can verify that
~MRENTHUSIASM
Video Solution
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.