Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2021 AIME II Problems/Problem 15"

m (→‎Solution 2 (Four Variables))
(→‎Solution 2 (Four Variables): Changed format.)
Line 21: Line 21:
  
 
==Solution 2 (Four Variables)==
 
==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
 
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*}
 
<cmath>\begin{align*}
Line 28: Line 31:
 
&\cdots \\
 
&\cdots \\
 
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>
+
\end{align*}</cmath></li><p>
−
If <math>n</math> and <math>(k+1)^2</math> have the same parity, then starting from <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.
+
  <li><math>\boldsymbol{g(n)}</math><p>
−
 
+
If <math>n</math> and <math>(k+1)^2</math> have the same parity, then starting from <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. <p>
 
Similar to the earlier restriction, we obtain <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
 
Similar to the earlier restriction, we obtain <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*}
 
<cmath>\begin{align*}
Line 38: Line 41:
 
&\cdots \\
 
&\cdots \\
 
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>
+
\end{align*}</cmath></li><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>
+
</ul>
−
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>
+
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{32.125mm}(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{46.25mm}(6)</cmath>
 
We substitute <math>(6)</math> into <math>(5),</math> then simplify, cross-multiply, and rearrange:
 
We substitute <math>(6)</math> into <math>(5),</math> then simplify, cross-multiply, and rearrange:
 
<cmath>\begin{align*}
 
<cmath>\begin{align*}
Line 47: Line 51:
 
7p+14q-7&=-4p+24q+4 \\
 
7p+14q-7&=-4p+24q+4 \\
 
11p-11&=10q \\
 
11p-11&=10q \\
−
11(p-1)&=10q. \hspace{29mm}(7)
+
11(p-1)&=10q. \hspace{34mm}(7)
 
\end{align*}</cmath>
 
\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>  
 
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>  
  
−
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>
+
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{33mm}(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:
 
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:
Line 68: Line 72:
 
<u><b>Remark</b></u>
 
<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>
+
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{f(324)}_{18}}=\frac{48}{84}=\frac47.</cmath>
  
 
~MRENTHUSIASM
 
~MRENTHUSIASM

Revision as of 20:32, 12 May 2021

Problem

Let $f(n)$ and $g(n)$ be functions satisfying \[f(n) = \begin{cases}\sqrt{n} & \text{ if } \sqrt{n} \text{ is an integer}\\ 1 + f(n+1) & \text{ otherwise} \end{cases}\]and \[g(n) = \begin{cases}\sqrt{n} & \text{ if } \sqrt{n} \text{ is an integer}\\ 2 + g(n+2) & \text{ otherwise} \end{cases}\]for positive integers $n$. Find the least positive integer $n$ such that $\tfrac{f(n)}{g(n)} = \tfrac{4}{7}$.

Solution 1

Consider what happens when we try to calculate $f(n)$ where n is not a square. If $k^2<n<(k+1)^2$ for (positive) integer k, recursively calculating the value of the function gives us $f(n)=(k+1)^2-n+f((k+1)^2)=k^2+3k+2-n$. Note that this formula also returns the correct value when $n=(k+1)^2$, but not when $n=k^2$. Thus $f(n)=k^2+3k+2-n$ for $k^2<n \leq (k+1)^2$.

If $2 \mid (k+1)^2-n$, $g(n)$ returns the same value as $f(n)$. This is because the recursion once again stops at $(k+1)^2$. We seek a case in which $f(n)<g(n)$, so obviously this is not what we want. We want $(k+1)^2,n$ to have a different parity, or $n, k$ have the same parity. When this is the case, $g(n)$ instead returns $(k+2)^2-n+g((k+2)^2)=k^2+5k+6-n$.

Write $7f(n)=4g(n)$, which simplifies to $3k^2+k-10=3n$. Notice that we want the $LHS$ expression to be divisible by 3; as a result, $k \equiv 1 \pmod{3}$. We also want n to be strictly greater than $k^2$, so $k-10>0, k>10$. 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 $k=16$, giving $n=258$.

Indeed - if we check our answer, it works. Therefore, the answer is $\boxed{258}$.

-Ross Gao

Solution 2 (Four Variables)

We consider $f(n)$ and $g(n)$ separately:

  • $\boldsymbol{f(n)}$

    We restrict $n$ in which $k^2<n\leq(k+1)^2$ for some positive integer $k,$ or \[n=(k+1)^2-p\hspace{40mm}(1)\] for some integer $p$ such that $0\leq p<2k+1.$ By recursion, we get \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{19mm}(2) \\ \end{align*}

  • $\boldsymbol{g(n)}$

    If $n$ and $(k+1)^2$ have the same parity, then starting from $g\left((k+1)^2\right)=k+1,$ we get $g(n)=f(n)$ by a similar process. This contradicts the precondition $\frac{f(n)}{g(n)} = \frac{4}{7}.$ Therefore, $n$ and $(k+1)^2$ must have different parities, from which $n$ and $(k+2)^2$ must have the same parity.

    Similar to the earlier restriction, we obtain $k^2<n<(k+2)^2,$ or \[n=(k+2)^2-2q\hspace{38.25mm}(3)\] for some integer $q$ such that $0<q<2k+2.$ By recursion, we get \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{15.5mm}(4) \\ \end{align*}

By $(2)$ and $(4),$ we have \[\frac{f(n)}{g(n)}=\frac{k+p+1}{k+2q+2}=\frac{4}{7}. \hspace{32.125mm}(5)\] From $(1)$ and $(3),$ equating the expressions for $n$ gives $(k+1)^2-p=(k+2)^2-2q.$ Solving for $k$ produces \[k=\frac{2q-p-3}{2}. \hspace{46.25mm}(6)\] We substitute $(6)$ into $(5),$ then simplify, cross-multiply, and rearrange: \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{34mm}(7) \end{align*} Since $\gcd(11,10)=1,$ we know that $p-1$ must be divisible by $10,$ and $q$ must be divisible by $11.$

Recall that the restrictions on $(1)$ and $(2)$ are $0\leq p<2k+1$ and $0<q<2k+2,$ respectively. Substituting $(6)$ into either inequality gives $p+1<q.$ Combining all these results produces \[0<p+1<q<2k+2. \hspace{33mm}(8)\]

To minimize $n$ in either $(1)$ or $(3),$ we minimize $k,$ so we minimize $p$ and $q$ in $(8).$ From $(6)$ and $(7),$ we construct the following table: \[\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}\] Finally, we have $(p,q,k)=(31,33,16).$ Substituting this result into either $(1)$ or $(3)$ generates $n=\boxed{258}.$

Remark

We can verify that \[\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{f(324)}_{18}}=\frac{48}{84}=\frac47.\]

~MRENTHUSIASM

Video Solution

https://youtu.be/tRVe2bKwIY8

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_15&oldid=153643"