Difference between revisions of "2021 AIME II Problems/Problem 15"
Etmetalakret (talk | contribs) |
Mathislife52 (talk | contribs) (→Solution 4 (Quadratics With Two Variables)) |
||
(75 intermediate revisions by 7 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | + | Let <math>f(n)</math> and <math>g(n)</math> be functions satisfying | |
− | == | + | <cmath>f(n) = \begin{cases}\sqrt{n} & \text{ if } \sqrt{n} \text{ is an integer}\\ |
− | + | 1 + f(n+1) & \text{ otherwise} | |
+ | \end{cases}</cmath>and | ||
+ | <cmath>g(n) = \begin{cases}\sqrt{n} & \text{ if } \sqrt{n} \text{ is an integer}\\ | ||
+ | 2 + g(n+2) & \text{ otherwise} | ||
+ | \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>. | ||
− | ==See | + | ==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>. | ||
+ | |||
+ | 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 <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>. | ||
+ | |||
+ | -Ross Gao | ||
+ | |||
+ | ==Solution 2 (Four Variables)== | ||
+ | We consider <math>f(n)</math> and <math>g(n)</math> separately: | ||
+ | <ul style="list-style-type:square;"> | ||
+ | <li><math>\boldsymbol{f(n)}</math><p> | ||
+ | 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{40mm}(1)</cmath> for some integer <math>p</math> such that <math>0\leq p<2k+1.</math> By recursion, 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, \\ | ||
+ | & \ \vdots \\ | ||
+ | f\bigl(\phantom{ }\underbrace{(k+1)^2-p}_{n}\phantom{ }\bigr)&=k+p+1. \hspace{19mm}(2) \\ | ||
+ | \end{align*}</cmath></li><p> | ||
+ | <li><math>\boldsymbol{g(n)}</math><p> | ||
+ | If <math>n</math> and <math>(k+1)^2</math> have the same parity, then we get <math>g(n)=f(n)</math> by a similar process from <math>g\left((k+1)^2\right)=k+1.</math> 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. <p> | ||
+ | It follows that <math>k^2<n<(k+2)^2,</math> or <cmath>n=(k+2)^2-2q\hspace{38.25mm}(3)</cmath> for some integer <math>q</math> such that <math>0<q<2k+2.</math> By recursion, 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, \\ | ||
+ | & \ \vdots \\ | ||
+ | g\bigl(\phantom{ }\underbrace{(k+2)^2-2q}_{n}\phantom{ }\bigr)&=k+2q+2. \hspace{15.5mm}(4) \\ | ||
+ | \end{align*}</cmath></li><p> | ||
+ | <li><b>Answer</b><p> | ||
+ | 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{27mm}(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{41.25mm}(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{29mm}(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> <p> Recall that the restrictions on <math>(1)</math> and <math>(2)</math> are <math>0\leq p<2k+1</math> and <math>0<q<2k+2,</math> respectively. Substituting <math>(6)</math> into either inequality gives <math>p+1<q.</math> Combining all these results produces <cmath>0<p+1<q<2k+2. \hspace{28mm}(8)</cmath> | ||
+ | |||
+ | To minimize <math>n</math> in either <math>(1)</math> or <math>(3),</math> we minimize <math>k,</math> so we minimize <math>p</math> and <math>q</math> in <math>(8).</math> From <math>(6)</math> and <math>(7),</math> we construct the following table: | ||
+ | <cmath>\begin{array}{c|c|c|c} | ||
+ | & & & \\ [-2.5ex] | ||
+ | \boldsymbol{p} & \boldsymbol{q} & \boldsymbol{k} & \textbf{Satisfies }\boldsymbol{(8)?} \\ [0.5ex] | ||
+ | \hline | ||
+ | & & & \\ [-2ex] | ||
+ | 11 & 11 & 4 & \\ | ||
+ | 21 & 22 & 10 & \\ | ||
+ | 31 & 33 & 16 & \checkmark \\ | ||
+ | \geq41 & \geq44 & \geq22 & \checkmark \\ | ||
+ | \end{array}</cmath> | ||
+ | Finally, we have <math>(p,q,k)=(31,33,16).</math> Substituting this result into either <math>(1)</math> or <math>(3)</math> generates <math>n=\boxed{258}.</math></li><p> | ||
+ | <li><b>Remark</b><p> | ||
+ | We can verify that <cmath>\frac{f(258)}{g(258)}=\frac{1\cdot31+f(258+1\cdot31)}{2\cdot33+g(258+2\cdot33)}=\frac{31+\overbrace{f(289)}^{17}}{66+\underbrace{g(324)}_{18}}=\frac{48}{84}=\frac47.</cmath></li><p> | ||
+ | </ul> | ||
+ | ~MRENTHUSIASM | ||
+ | |||
+ | ==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>m</math> is odd, then <math>f(n)=g(n)</math>. If <math>m</math> is even, then | ||
+ | <cmath>\begin{align*} | ||
+ | f(n)&=(m+1)^2-(m^2+k)+(m+1)=3m+2-k, \\ | ||
+ | g(n)&=(m+2)^2-(m^2+k)+(m+2)=5m+6-k, | ||
+ | \end{align*}</cmath> | ||
+ | from which | ||
+ | <cmath>\begin{align*} | ||
+ | 7(3m+2-k)&=4(5m+6-k) \\ | ||
+ | m&=3k+10. | ||
+ | \end{align*}</cmath> | ||
+ | Since <math>m</math> is even, <math>k</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 | ||
+ | |||
+ | ==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 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>. | ||
+ | |||
+ | Expanding <math>(z+1)^2</math> and substituting in the fact that <math>z=\sqrt{n+k}</math> yields: | ||
+ | |||
+ | <cmath>(z+1)^2=z^2+2z+1=n+k+2\sqrt{n+k}+1</cmath> | ||
+ | |||
+ | Thus, we must add the quantity <math>k+2z+1</math> to <math>n</math> to achieve a integral value in the function <math>g(n)</math>. Thus. | ||
+ | |||
+ | <cmath>g(n)=(k+2z+1)+\sqrt{n+k+2\sqrt{n+k}+1}</cmath> | ||
+ | |||
+ | However, note that the quantity within the square root is just <math>(z+1)^2</math>, and so: | ||
+ | |||
+ | <cmath>g(n)=k+3z+2</cmath> | ||
+ | |||
+ | Thus, | ||
+ | <cmath>\frac{f(n)}{g(n)}=\frac{k+z}{k+3z+2}</cmath> | ||
+ | |||
+ | Since we want this quantity to equal <math>\frac{4}{7}</math>, we can set the above equation equal to this number and collect all the variables to one side to achieve | ||
+ | |||
+ | <cmath>3k-5z=8</cmath> | ||
+ | |||
+ | Substituting back in that <math>z=\sqrt{n+k}</math>, and then separating variables and squaring yields that | ||
+ | |||
+ | <cmath>9k^2-73k+64=25n</cmath> | ||
+ | |||
+ | Now, if we treat <math>n</math> as a constant, we can use the quadratic formula in respect to <math>k</math> to get an equation for <math>k</math> in terms of <math>n</math> (without all the squares). Doing so yields | ||
+ | |||
+ | <cmath>\frac{73\pm\sqrt{3025+900n}}{18}=k</cmath> | ||
+ | |||
+ | Now, since <math>n</math> and <math>k</math> are integers, we want the quantity within the square root to be a perfect square. Note that <math>55^2=3025</math>. Thus, assume that the quantity within the root is equal to the perfect square, <math>m^2</math>. Thus, after using a difference of squares, we have | ||
+ | <cmath>(m-55)(m+55)=900n</cmath> | ||
+ | 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 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. | ||
+ | |||
+ | 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 <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> | ||
+ | |||
+ | 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. | ||
+ | |||
+ | Case 1: <math>n</math> is odd and <math>a</math> is even | ||
+ | |||
+ | Here, we get <math>a=2k</math> for some positive integer <math>k.</math> Then, <math>b = 2k+1.</math> We let <math>n = a^2-(2m+1)</math> for some positive integer <math>m</math> so <math>f(n) = 2k+2m+1</math> and <math>g(n) = 2k+1+2m+1+4k+1 = 6k+2m+3.</math> | ||
+ | |||
+ | We set <math>\frac{2k+2m+1}{6k+2m+3}=\frac{4}{7},</math> cross multiply, and rearrange to get <math>6m-10k=5.</math> Since <math>k</math> and <math>m</math> are integers, the LHS will always be even and the RHS will always be odd, and thus, this case yields no solutions. | ||
+ | |||
+ | Case 2: <math>n</math> is even and <math>a</math> is odd | ||
+ | |||
+ | Here, we get <math>a=2k+1</math> for some positive ineger <math>k.</math> Then, <math>b=2k+2.</math> We let <math>n = a^2-(2m+1)</math> for some positive integer <math>m</math> so <math>f(n)=2k+1+2m+1=2k+2m+2</math> and <math>g(n)=2k+2+2m+1+4k+3 = 6k+2m+6.</math> | ||
+ | |||
+ | We set <math>\frac{2k+2m+2}{6k+2m+6} = \frac{4}{7},</math> cross multiply, and rearrange to get <math>5k=3m-5,</math> or <math>k=\frac{3}{5}m-1.</math> Since <math>k</math> and <math>m</math> are integers, <math>m</math> must be a multiple of <math>5.</math> Some possible solutions for <math>(k,m)</math> with the least <math>k</math> and <math>m</math> are <math>(2,5), (5,10), (8,15),</math> and <math>(11,20).</math> | ||
+ | |||
+ | We wish to minimize <math>k</math> since <math>a=2k+1.</math> One thing to keep in mind is the initial assumption <math>(a-1)^2 < n < a^2.</math> | ||
+ | |||
+ | 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>(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. | ||
+ | |||
+ | ~mc21s | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/tRVe2bKwIY8 | ||
+ | ~Mathematical Dexterity | ||
+ | |||
+ | ==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 21:35, 15 October 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 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
Video Solution
https://youtu.be/tRVe2bKwIY8 ~Mathematical Dexterity
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.