Difference between revisions of "2021 AIME II Problems/Problem 15"
MRENTHUSIASM (talk | contribs) (→Solution 2 (More Variables)) |
|||
(8 intermediate revisions by the same user not shown) | |||
Line 8: | Line 8: | ||
\end{cases}</cmath>for positive integers <math>n</math>. Find the least positive integer <math>n</math> such that <math>\tfrac{f(n)}{g(n)} = \tfrac{4}{7}</math>. | \end{cases}</cmath>for positive integers <math>n</math>. Find the least positive integer <math>n</math> such that <math>\tfrac{f(n)}{g(n)} = \tfrac{4}{7}</math>. | ||
− | ==Solution== | + | ==Solution 1== |
Consider what happens when we try to calculate <math>f(n)</math> where n is not a square. If <math>k^2<n<(k+1)^2</math> for (positive) integer k, recursively calculating the value of the function gives us <math>f(n)=(k+1)^2-n+f((k+1)^2)=k^2+3k+2-n</math>. Note that this formula also returns the correct value when <math>n=(k+1)^2</math>, but not when <math>n=k^2</math>. Thus <math>f(n)=k^2+3k+2-n</math> for <math>k^2<n \leq (k+1)^2</math>. | Consider what happens when we try to calculate <math>f(n)</math> where n is not a square. If <math>k^2<n<(k+1)^2</math> for (positive) integer k, recursively calculating the value of the function gives us <math>f(n)=(k+1)^2-n+f((k+1)^2)=k^2+3k+2-n</math>. Note that this formula also returns the correct value when <math>n=(k+1)^2</math>, but not when <math>n=k^2</math>. Thus <math>f(n)=k^2+3k+2-n</math> for <math>k^2<n \leq (k+1)^2</math>. | ||
Line 16: | Line 16: | ||
Write <math>7f(n)=4g(n)</math>, which simplifies to <math>3k^2+k-10=3n</math>. Notice that we want the <math>LHS</math> 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 (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 <math>k=16</math>, giving <math>n=258</math>. | Write <math>7f(n)=4g(n)</math>, which simplifies to <math>3k^2+k-10=3n</math>. Notice that we want the <math>LHS</math> 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 (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 <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>. |
-Ross Gao | -Ross Gao | ||
+ | |||
+ | ==Solution 2 (More Variables)== | ||
+ | We restrict <math>n</math> in which <math>k^2<n\leq(k+1)^2</math> for some positive integer <math>k,</math> or <cmath>n=(k+1)^2-p\hspace{15mm}(1)</cmath> for some nonnegative integer <math>p.</math> By observations, we get | ||
+ | <cmath>\begin{align*} | ||
+ | f\left((k+1)^2\right)&=k+1, \\ | ||
+ | f\left((k+1)^2-1\right)&=k+2, \\ | ||
+ | f\left((k+1)^2-2\right)&=k+3, \\ | ||
+ | &\cdots \\ | ||
+ | f\bigl(\phantom{ }\underbrace{(k+1)^2-p}_{n}\phantom{ }\bigr)&=k+p+1. \hspace{15mm}(2) \\ | ||
+ | \end{align*}</cmath> | ||
+ | If <math>n</math> and <math>(k+1)^2</math> have the same parity, then starting with <math>g\left((k+1)^2\right)=k+1,</math> we get <math>g(n)=f(n)</math> by a similar process. This contradicts the precondition <math>\frac{f(n)}{g(n)} = \frac{4}{7}.</math> Therefore, <math>n</math> and <math>(k+1)^2</math> must have different parities, from which <math>n</math> and <math>(k+2)^2</math> must have the same parity. | ||
+ | |||
+ | Along with the earlier restriction, note that <math>k^2<n\leq(k+1)^2<(k+2)^2,</math> or <cmath>n=(k+2)^2-2q\hspace{15mm}(3)</cmath> for some positive integer <math>q.</math> By observations, we get | ||
+ | <cmath>\begin{align*} | ||
+ | g\left((k+2)^2\right)&=k+2, \\ | ||
+ | g\left((k+2)^2-2\right)&=k+4, \\ | ||
+ | g\left((k+2)^2-4\right)&=k+6, \\ | ||
+ | &\cdots \\ | ||
+ | g\bigl(\phantom{ }\underbrace{(k+2)^2-2q}_{n}\phantom{ }\bigr)&=k+2q+2. \hspace{15mm}(4) \\ | ||
+ | \end{align*}</cmath> | ||
+ | By <math>(2)</math> and <math>(4),</math> we have <cmath>\frac{f(n)}{g(n)}=\frac{k+p+1}{k+2q+2}=\frac{4}{7}. \hspace{15mm}(5)</cmath> | ||
+ | From <math>(1)</math> and <math>(3),</math> equating the expressions for <math>n</math> gives <math>(k+1)^2-p=(k+2)^2-2q.</math> Solving for <math>k</math> produces <cmath>k=\frac{2q-p-3}{2}. \hspace{15mm}(6)</cmath> | ||
+ | We substitute <math>(6)</math> into <math>(5),</math> then simplify, cross-multiply, and rearrange: | ||
+ | <cmath>\begin{align*} | ||
+ | \frac{\tfrac{2q-p-3}{2}+p+1}{\tfrac{2q-p-3}{2}+2q+2}&=\frac{4}{7} \\ | ||
+ | \frac{p+2q-1}{-p+6q+1}&=\frac{4}{7} \\ | ||
+ | 7p+14q-7&=-4p+24q+4 \\ | ||
+ | 11p-11&=10q \\ | ||
+ | 11(p-1)&=10q. \hspace{15mm}(7) | ||
+ | \end{align*}</cmath> | ||
+ | Since <math>\gcd(11,10)=1,</math> we know that <math>p-1</math> must be divisible by <math>10,</math> and <math>q</math> must be divisible by <math>11.</math> Furthermore, rewriting the restriction <math>k^2<n</math> in terms of <math>p</math> and <math>q</math> gives | ||
+ | <cmath>\begin{align*} | ||
+ | k^2&<\underbrace{(k+1)^2-p}_{\text{by }(1)} \\ | ||
+ | p&<2k+1 &(8)\\ | ||
+ | p&<2\biggl(\phantom{ }\underbrace{\frac{2q-p-3}{2}}_{\text{by }(6)}\phantom{ }\biggr)+1 \\ | ||
+ | p&<(2q-p-3)+1 \\ | ||
+ | p&<q-1. &(9) | ||
+ | \end{align*}</cmath> | ||
+ | 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} | ||
+ | & & \\ [-2.5ex] | ||
+ | \boldsymbol{p} & \boldsymbol{q} & \textbf{Satisfies }\boldsymbol{(9)?} \\ [0.5ex] | ||
+ | \hline | ||
+ | & & \\ [-2ex] | ||
+ | 11 & 11 & \\ | ||
+ | 21 & 22 & \\ | ||
+ | 31 & 33 & \checkmark \\ | ||
+ | \geq41 & \geq44 & \checkmark \\ | ||
+ | \end{array}</cmath> | ||
+ | We have <math>(p,q)=(31,33).</math> Substituting this result into <math>(6)</math> produces <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> | ||
+ | |||
+ | We can verify that <cmath>\frac{f(258)}{g(258)}=\frac{31+\overbrace{f(289)}^{17}}{2\cdot33+\underbrace{f(324)}_{18}}=\frac{48}{84}=\frac47.</cmath> | ||
+ | |||
+ | ~MRENTHUSIASM | ||
==Video Solution== | ==Video Solution== |
Revision as of 06:27, 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 To minimize we should minimize By and we should minimize and From we construct the following table: We have Substituting this result into produces 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.