https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Dearpasserby&feedformat=atomAoPS Wiki - User contributions [en]2024-03-29T07:55:36ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_1&diff=1502612021 AIME II Problems/Problem 12021-03-25T16:42:28Z<p>Dearpasserby: /* Solution 3 (Symmetry and Generalization) */</p>
<hr />
<div>==Problem==<br />
Find the arithmetic mean of all the three-digit palindromes. (Recall that a palindrome is a number that reads the same forward and backward, such as <math>777</math> or <math>383</math>.)<br />
<br />
==Solution 1==<br />
Recall* the the arithmetic mean of all the <math>n</math> digit palindromes is just the average of the largest and smallest <math>n</math> digit palindromes, and in this case the <math>2</math> palindromes are <math>101</math> and <math>999</math> and <math>\frac{101+999}{2}=550</math> and <math>\boxed{550}</math> is the final answer.<br />
<br />
~ math31415926535<br />
<br />
* This relies on the fact that whenever x is a palindrome, 1100-x is also a palindrome. Once you realize this bijective relationship you will immediately obtain the mean, although it honestly may not be easy to see it on spot.<br />
* Refer to <u><b>Solution 3 (Symmetry and Generalization)</b></u> for the note above.<br />
<br />
-Note by Ross Gao and MRENTHUSIASM<br />
<br />
==Solution 2==<br />
For any palindrome <math>\overline{ABA}</math>, note that <math>\overline{ABA}</math>, is 100A + 10B + A which is also 101A + 10B. <br />
The average for A is 5 since A can be any of 1, 2, 3, 4, 5, 6, 7, 8, or 9. The average for B is 4.5 since B is either 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9. Therefore, the answer is 505 + 45 = <math>\boxed{550}</math>.<br />
<br />
- ARCTICTURN<br />
<br />
==Solution 3 (Symmetry and Generalization)==<br />
For any three-digit palindrome <math>\overline{ABA},</math> where <math>A</math> and <math>B</math> are digits with <math>A\neq0,</math> note that <math>\overline{(10-A)(9-B)(10-A)}</math> must be another palindrome by symmetry. The mapping from 3-digit palindromes to 3-digit palindromes, <math>f: \overline{ABA} \rightarrow \overline{(10-A)(9-B)(10-A)}</math>, is a bijection. Different palindromes are mapped to different palindromes, and each palindrome has a preimage. In particular, because <math>f^2=id</math>, <math>f^{-1}(x)=f(x)</math>. Therefore, we can pair each three-digit palindrome uniquely with another three-digit palindrome so that they sum to <br />
<cmath>\begin{align*}<br />
\overline{ABA}+\overline{(10-A)(9-B)(10-A)}&=\left[100A+10B+A\right]+\left[100(10-A)+10(9-B)+(10-A)\right] \\<br />
&=\left[100A+10B+A\right]+\left[1000-100A+90-10B+10-A\right] \\<br />
&=1000+90+10 \\<br />
&=1100.<br />
\end{align*}</cmath><br />
For instances:<br />
<cmath>\begin{align*}<br />
101+999&=1100, \\<br />
262+838&=1100, \\<br />
373+727&=1100, \\<br />
414+686&=1100, \\<br />
545+555&=1100,<br />
\end{align*}</cmath><br />
and so on.<br />
<br />
From this symmetry, the arithmetic mean of all the three-digit palindromes is <math>\frac{1100}{2}=\boxed{550}.</math><br />
<br />
~MRENTHUSIASM<br />
<br />
==Solution 4==<br />
<cmath>\begin{align*}<br />
\sum_{A = 1}^9 \sum_{B = 0}^9 \overline{ABA} &= \sum_{A = 1}^9 \sum_{B = 0}^9 \left( 101 A + 10 B \right) \\<br />
&= \sum_{A = 1}^9 \sum_{B = 0}^9 101 A + \sum_{A = 1}^9 \sum_{B = 0}^9 10 B \\<br />
&= 101 \cdot 10 \sum_{A = 1}^9 A + 10 \cdot 9 \sum_{B = 0}^9 B \\<br />
&= 1010 \cdot 45 + 90 \cdot 45 \\<br />
&= <br />
\end{align*}</cmath><br />
<br />
- A bit too complicated of a solution - somebody please fix. - ARCTICTURN<br />
<br />
Doriding is the original author. I will wait for him to come back. ~MRENTHUSIASM<br />
<br />
==Video Solution==<br />
https://www.youtube.com/watch?v=jDP2PErthkg<br />
<br />
==See Also==<br />
<br />
{{AIME box|year=2021|n=II|before=First Problem|num-a=2}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_1&diff=1502602021 AIME II Problems/Problem 12021-03-25T16:42:13Z<p>Dearpasserby: /* Solution 3 (Symmetry and Generalization) */</p>
<hr />
<div>==Problem==<br />
Find the arithmetic mean of all the three-digit palindromes. (Recall that a palindrome is a number that reads the same forward and backward, such as <math>777</math> or <math>383</math>.)<br />
<br />
==Solution 1==<br />
Recall* the the arithmetic mean of all the <math>n</math> digit palindromes is just the average of the largest and smallest <math>n</math> digit palindromes, and in this case the <math>2</math> palindromes are <math>101</math> and <math>999</math> and <math>\frac{101+999}{2}=550</math> and <math>\boxed{550}</math> is the final answer.<br />
<br />
~ math31415926535<br />
<br />
* This relies on the fact that whenever x is a palindrome, 1100-x is also a palindrome. Once you realize this bijective relationship you will immediately obtain the mean, although it honestly may not be easy to see it on spot.<br />
* Refer to <u><b>Solution 3 (Symmetry and Generalization)</b></u> for the note above.<br />
<br />
-Note by Ross Gao and MRENTHUSIASM<br />
<br />
==Solution 2==<br />
For any palindrome <math>\overline{ABA}</math>, note that <math>\overline{ABA}</math>, is 100A + 10B + A which is also 101A + 10B. <br />
The average for A is 5 since A can be any of 1, 2, 3, 4, 5, 6, 7, 8, or 9. The average for B is 4.5 since B is either 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9. Therefore, the answer is 505 + 45 = <math>\boxed{550}</math>.<br />
<br />
- ARCTICTURN<br />
<br />
==Solution 3 (Symmetry and Generalization)==<br />
For any three-digit palindrome <math>\overline{ABA},</math> where <math>A</math> and <math>B</math> are digits with <math>A\neq0,</math> note that <math>\overline{(10-A)(9-B)(10-A)}</math> must be another palindrome by symmetry. The mapping from 3-digit palindromes to 3-dit palindromes, <math>f: \overline{ABA} \rightarrow \overline{(10-A)(9-B)(10-A)}</math>, is a bijection. Different palindromes are mapped to different palindromes, and each palindrome has a preimage. In particular, because <math>f^2=id</math>, <math>f^{-1}(x)=f(x)</math>. Therefore, we can pair each three-digit palindrome uniquely with another three-digit palindrome so that they sum to <br />
<cmath>\begin{align*}<br />
\overline{ABA}+\overline{(10-A)(9-B)(10-A)}&=\left[100A+10B+A\right]+\left[100(10-A)+10(9-B)+(10-A)\right] \\<br />
&=\left[100A+10B+A\right]+\left[1000-100A+90-10B+10-A\right] \\<br />
&=1000+90+10 \\<br />
&=1100.<br />
\end{align*}</cmath><br />
For instances:<br />
<cmath>\begin{align*}<br />
101+999&=1100, \\<br />
262+838&=1100, \\<br />
373+727&=1100, \\<br />
414+686&=1100, \\<br />
545+555&=1100,<br />
\end{align*}</cmath><br />
and so on.<br />
<br />
From this symmetry, the arithmetic mean of all the three-digit palindromes is <math>\frac{1100}{2}=\boxed{550}.</math><br />
<br />
~MRENTHUSIASM<br />
<br />
==Solution 4==<br />
<cmath>\begin{align*}<br />
\sum_{A = 1}^9 \sum_{B = 0}^9 \overline{ABA} &= \sum_{A = 1}^9 \sum_{B = 0}^9 \left( 101 A + 10 B \right) \\<br />
&= \sum_{A = 1}^9 \sum_{B = 0}^9 101 A + \sum_{A = 1}^9 \sum_{B = 0}^9 10 B \\<br />
&= 101 \cdot 10 \sum_{A = 1}^9 A + 10 \cdot 9 \sum_{B = 0}^9 B \\<br />
&= 1010 \cdot 45 + 90 \cdot 45 \\<br />
&= <br />
\end{align*}</cmath><br />
<br />
- A bit too complicated of a solution - somebody please fix. - ARCTICTURN<br />
<br />
Doriding is the original author. I will wait for him to come back. ~MRENTHUSIASM<br />
<br />
==Video Solution==<br />
https://www.youtube.com/watch?v=jDP2PErthkg<br />
<br />
==See Also==<br />
<br />
{{AIME box|year=2021|n=II|before=First Problem|num-a=2}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_1&diff=1502142021 AIME II Problems/Problem 12021-03-25T05:08:06Z<p>Dearpasserby: /* Solution 1 */</p>
<hr />
<div>==Problem==<br />
Find the arithmetic mean of all the three-digit palindromes. (Recall that a palindrome is a number that reads the same forward and backward, such as <math>777</math> or <math>383</math>.)<br />
<br />
==Solution 1==<br />
Recall* the the arithmetic mean of all the <math>n</math> digit palindromes is just the average of the largest and smallest <math>n</math> digit palindromes, and in this case the <math>2</math> palindromes are <math>101</math> and <math>999</math> and <math>\frac{101+999}{2}=550</math> and <math>\boxed{550}</math> is the final answer.<br />
<br />
~ math31415926535<br />
<br />
*This relies on the fact that whenever x is a palindrome, 1100-x is also a palindrome. Once you realize this bijective relationship you will immediately obtain the mean, although it honestly may not be easy to see it on spot.<br />
-Note by Ross Gao<br />
<br />
==Solution 2==<br />
For any palindrome <math>\overline{ABA}</math>, note that <math>\overline{ABA}</math>, is 100A + 10B + A which is also 101A + 10B. <br />
The average for A is 5 since A can be any of 1, 2, 3, 4, 5, 6, 7, 8, or 9. The average for B is 4.5 since B is either 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9. Therefore, the answer is 505 + 45 = <math>\boxed{550}</math>.<br />
<br />
- ARCTICTURN<br />
<br />
==Solution 3 (Symmetry and Generalization)==<br />
For any three-digit palindrome <math>\overline{ABA},</math> where <math>A</math> and <math>B</math> are digits with <math>A\neq0,</math> note that <math>\overline{(10-A)(9-B)(10-A)}</math> must be another palindrome by symmetry. Therefore, we can pair each three-digit palindrome uniquely with another three-digit palindrome so that they sum to <br />
<cmath>\begin{align*}<br />
\overline{ABA}+\overline{(10-A)(9-B)(10-A)}&=\left[100A+10B+A\right]+\left[100(10-A)+10(9-B)+(10-A)\right] \\<br />
&=\left[100A+10B+A\right]+\left[1000-100A+90-10B+10-A\right] \\<br />
&=1000+90+10 \\<br />
&=1100.<br />
\end{align*}</cmath><br />
For instances:<br />
<cmath>\begin{align*}<br />
272+828&=1100, \\<br />
414+686&=1100, \\<br />
595+505&=1100,<br />
\end{align*}</cmath><br />
and so on.<br />
<br />
From this symmetry, the arithmetic mean of all the three-digit palindromes is <math>\frac{1110}{2}=\boxed{550}.</math><br />
<br />
~MRENTHUSIASM<br />
<br />
==Solution 4==<br />
<cmath>\begin{align*}<br />
\sum_{A = 1}^9 \sum_{B = 0}^9 \overline{ABA} &= \sum_{A = 1}^9 \sum_{B = 0}^9 \left( 101 A + 10 B \right) \\<br />
&= \sum_{A = 1}^9 \sum_{B = 0}^9 101 A + \sum_{A = 1}^9 \sum_{B = 0}^9 10 B \\<br />
&= 101 \cdot 10 \sum_{A = 1}^9 A + 10 \cdot 9 \sum_{B = 0}^9 B \\<br />
&= 1010 \cdot 45 + 90 \cdot 45 \\<br />
&= <br />
\end{align*}</cmath><br />
<br />
- A bit too complicated of a solution - somebody please fix. - ARCTICTURN<br />
<br />
Doriding is the original author. I will wait for him to come back. ~MRENTHUSIASM<br />
<br />
==Video Solution==<br />
https://www.youtube.com/watch?v=jDP2PErthkg<br />
<br />
==See Also==<br />
<br />
{{AIME box|year=2021|n=II|before=First Problem|num-a=2}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_1&diff=1502132021 AIME II Problems/Problem 12021-03-25T05:07:43Z<p>Dearpasserby: /* Solution 1 */</p>
<hr />
<div>==Problem==<br />
Find the arithmetic mean of all the three-digit palindromes. (Recall that a palindrome is a number that reads the same forward and backward, such as <math>777</math> or <math>383</math>.)<br />
<br />
==Solution 1==<br />
Recall* the the arithmetic mean of all the <math>n</math> digit palindromes is just the average of the largest and smallest <math>n</math> digit palindromes, and in this case the <math>2</math> palindromes are <math>101</math> and <math>999</math> and <math>\frac{101+999}{2}=550</math> and <math>\boxed{550}</math> is the final answer.<br />
<br />
~ math31415926535<br />
<br />
*This relies on the fact that whenever a is a palindrome, 1100-a is also a palindrome. Once you realize this bijective relationship you will immediately obtain the mean, although it honestly may not be easy to see it on spot.<br />
-Note by Ross Gao<br />
<br />
==Solution 2==<br />
For any palindrome <math>\overline{ABA}</math>, note that <math>\overline{ABA}</math>, is 100A + 10B + A which is also 101A + 10B. <br />
The average for A is 5 since A can be any of 1, 2, 3, 4, 5, 6, 7, 8, or 9. The average for B is 4.5 since B is either 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9. Therefore, the answer is 505 + 45 = <math>\boxed{550}</math>.<br />
<br />
- ARCTICTURN<br />
<br />
==Solution 3 (Symmetry and Generalization)==<br />
For any three-digit palindrome <math>\overline{ABA},</math> where <math>A</math> and <math>B</math> are digits with <math>A\neq0,</math> note that <math>\overline{(10-A)(9-B)(10-A)}</math> must be another palindrome by symmetry. Therefore, we can pair each three-digit palindrome uniquely with another three-digit palindrome so that they sum to <br />
<cmath>\begin{align*}<br />
\overline{ABA}+\overline{(10-A)(9-B)(10-A)}&=\left[100A+10B+A\right]+\left[100(10-A)+10(9-B)+(10-A)\right] \\<br />
&=\left[100A+10B+A\right]+\left[1000-100A+90-10B+10-A\right] \\<br />
&=1000+90+10 \\<br />
&=1100.<br />
\end{align*}</cmath><br />
For instances:<br />
<cmath>\begin{align*}<br />
272+828&=1100, \\<br />
414+686&=1100, \\<br />
595+505&=1100,<br />
\end{align*}</cmath><br />
and so on.<br />
<br />
From this symmetry, the arithmetic mean of all the three-digit palindromes is <math>\frac{1110}{2}=\boxed{550}.</math><br />
<br />
~MRENTHUSIASM<br />
<br />
==Solution 4==<br />
<cmath>\begin{align*}<br />
\sum_{A = 1}^9 \sum_{B = 0}^9 \overline{ABA} &= \sum_{A = 1}^9 \sum_{B = 0}^9 \left( 101 A + 10 B \right) \\<br />
&= \sum_{A = 1}^9 \sum_{B = 0}^9 101 A + \sum_{A = 1}^9 \sum_{B = 0}^9 10 B \\<br />
&= 101 \cdot 10 \sum_{A = 1}^9 A + 10 \cdot 9 \sum_{B = 0}^9 B \\<br />
&= 1010 \cdot 45 + 90 \cdot 45 \\<br />
&= <br />
\end{align*}</cmath><br />
<br />
- A bit too complicated of a solution - somebody please fix. - ARCTICTURN<br />
<br />
Doriding is the original author. I will wait for him to come back. ~MRENTHUSIASM<br />
<br />
==Video Solution==<br />
https://www.youtube.com/watch?v=jDP2PErthkg<br />
<br />
==See Also==<br />
<br />
{{AIME box|year=2021|n=II|before=First Problem|num-a=2}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_10&diff=1499752021 AIME II Problems/Problem 102021-03-23T15:07:46Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Two spheres with radii <math>36</math> and one sphere with radius <math>13</math> are each externally tangent to the other two spheres and to two different planes <math>\mathcal{P}</math> and <math>\mathcal{Q}</math>. The intersection of planes <math>\mathcal{P}</math> and <math>\mathcal{Q}</math> is the line <math>\ell</math>. The distance from line <math>\ell</math> to the point where the sphere with radius <math>13</math> is tangent to plane <math>\mathcal{P}</math> is <math>\tfrac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m + n</math>.<br />
<br />
==Solution==<br />
<br />
The centers of the three spheres form a 49-49-72 triangle. Consider the points at which the plane is tangent to the two bigger spheres; the line segment connecting these two points should be parallel to the 72 side of this triangle. Take its midpoint <math>M</math>, which is 36 away from the midpoint of the 72 side <math>A</math>, and connect these two midpoints.<br />
<br />
Now consider the point at which the plane is tangent to the small sphere, and connect <math>M</math> with the small sphere's tangent point <math>B</math>. Extend <math>MB</math> through B until it hits the ray from <math>A</math> through the center of the small sphere (convince yourself that these two intersect). Call this intersection <math>D</math>, the center of the small sphere <math>C</math>, we want to find <math>BD</math>.<br />
<br />
By Pythagorus AC= <math>\sqrt{49^2-36^2}=\sqrt{1105}</math>, and we know <math>MB=36,BC=13</math>. We know that <math>MB,BC</math> must be parallel, using ratios we realize that <math>CD=\frac{13}{23}\sqrt{1105}</math>. Apply Pythagorean theorem on triangle BCD; <math>BD=\frac{312}{23}</math>, and so we're done.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=II|num-b=9|num-a=11}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_13&diff=1497372021 AIME II Problems/Problem 132021-03-22T20:47:38Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Find the least positive integer <math>n</math> for which <math>2^n + 5^n - n</math> is a multiple of <math>1000</math>.<br />
<br />
==Solution==<br />
<br />
1000 divides this expression iff 8, 125 both divide it. It should be fairly obvious that <math>n \geq 3</math>; so we may break up the initial condition into two sub-conditions.<br />
<br />
(1) <math>5^n \equiv n \pmod{8}</math>. Notice that the square of any odd integer is 1 modulo 8 (why?), so the LHS of this expression goes "5,1,5,1, ...", while the RHS goes "1,2,3,4,5,6,7,8,1, ...". The cycle length of the LHS is 2, RHS is 8, so the cycle length of the solution is <math>lcm(2,8)=8</math>. Indeed, the n that solve this equation are exactly those such that <math>n \equiv 5 \pmod{8}</math>.<br />
<br />
(2) <math>2^n \equiv n \pmod{125}</math>. This is extremely computationally intensive if you try to calculate all <math>2^1,2^2, ..., 2^{100} \pmod{125}</math>, so instead, we take a divide-and-conquer approach. In order for this expression to be true <math>2^n \equiv n \pmod{5}</math> is necessary; it shouldn't take too long for you to go through the 20 possible LHS-RHS combinations and convince yourself that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{20}</math>. <br />
<br />
With this in mind we consider <math>2^n \equiv n</math> modulo 25. By the generalized Fermat's little theorem, <math>2^{20} \equiv 1 \pmod{25}</math>, but we already have n modulo 20! Our calculation is greatly simplified. The LHS cycle length is 20, RHS cycle length is 25, the lcm is 100, in this step we need to test all the numbers between 1 to 100 that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{17}</math>. In the case that <math>n \equiv 3 \pmod{20}</math>, <math>2^n \equiv 2^3 \equiv 8</math>, and RHS goes "3,23,43,63,83"; clearly <math>n \equiv 83 \pmod{100}</math>. In the case that <math>n \equiv 17 \pmod{20}</math>, by a similar argument, <math>n \equiv 97 \pmod{100}</math>. <br />
<br />
In the final step, we need to calculate <math>2^{97}, 2^{83}</math> modulo 125. The former is simply <math>2^{-3}</math>; because <math>8*47=376=1</math> modulo 125, <math>2^{97} \equiv 47</math>. <math>2^{83}</math> is <math>2^{-17}=2^{-16}*2^{-1}</math>. <math>2^{-1}=63,2^{-2}=63^2=3969=-31,2^{-4}=(-31)^2=961=-39,2^{-8}=1521=21, 2^{-16}=441,2^{-17}=63*441=7*{-31}=-217=33</math>. This time, LHS cycle is 100, RHS cycle is 125, so we need to figure out what is n modulo 500. It should be <math>n \equiv 283,297 \pmod{500}</math>.<br />
<br />
Put everything together. By the second subcondition, the only candidates < 100 are <math>283,297,782,797</math>. Apply the first subcondition, n=797 is the desired answer.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=II|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_13&diff=1497352021 AIME II Problems/Problem 132021-03-22T20:46:47Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Find the least positive integer <math>n</math> for which <math>2^n + 5^n - n</math> is a multiple of <math>1000</math>.<br />
<br />
==Solution==<br />
<br />
1000 divides this expression iff 8, 125 both divide it. It should be fairly obvious that <math>n \geq 3</math>; so we may break up the initial condition into two sub-conditions.<br />
<br />
(1) <math>5^n \equiv n \pmod{8}</math>. Notice that the square of any odd integer is 1 modulo 8 (why?), so the LHS of this expression goes "5,1,5,1, ...", while the RHS goes "1,2,3,4,5,6,7,8,1, ...". The cycle length of the LHS is 2, RHS is 8, so the cycle length of the solution is <math>lcm(2,8)=8</math>. Indeed, the n that solve this equation are exactly those such that <math>n \equiv 5 \pmod{8}</math>.<br />
<br />
(2) <math>2^n \equiv n \pmod{125}</math>. This is extremely computationally intensive if you try to calculate all <math>2^1,2^2, ..., 2^{100} \pmod{125}</math>, so instead, we take a divide-and-conquer approach. In order for this expression to be true <math>2^n \equiv n \pmod{5}</math> is necessary; it shouldn't take too long for you to go through the 20 possible LHS-RHS combinations and convince yourself that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{20}</math>. <br />
<br />
With this in mind we consider <math>2^n \equiv n</math> modulo 25. By the generalized Fermat's little theorem, <math>2^{20} \equiv 1 \pmod{25}</math>, but we already have n modulo 20! Our calculation is greatly simplified. The LHS cycle length is 20, RHS cycle length is 25, the lcm is 100, in this step we need to test all the numbers between 1 to 100 that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{17}</math>. In the case that <math>n \equiv 3 \pmod{20}</math>, <math>2^n \equiv 2^3 \equiv 8</math>, and RHS goes "3,23,43,63,83"; clearly <math>n \equiv 83 \pmod{100}</math>. In the case that <math>n \equiv 17 \pmod{20}</math>, by a similar argument, <math>n \equiv 97 \pmod{100}</math>. <br />
<br />
In the final step, we need to calculate <math>2^{97}, 2^{83}</math> modulo 125. The former is simply <math>2^{-3}</math>; because <math>8*47=376=1</math> modulo 125, <math>2^{97} \equiv 47</math>. <math>2^{83}</math> is <math>2^{-17}=2{-16}*2^{-1}</math>. <math>2^{-1}=63,2^{-2}=63^2=3969=-31,2^{-4}=(-31)^2=961=-39,2^{-8}=1521=21, 2^{-16}=441,2^{-17}=63*441=7*{-31}=-217=33</math>. This time, LHS cycle is 100, RHS cycle is 125, so we need to figure out what is n modulo 500. It should be <math>n \equiv 283,297 \pmod{500}</math>.<br />
<br />
Put everything together. By the second subcondition, the only candidates < 100 are <math>283,297,782,797</math>. Apply the first subcondition, n=797 is the desired answer.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=II|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_13&diff=1497342021 AIME II Problems/Problem 132021-03-22T20:46:25Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Find the least positive integer <math>n</math> for which <math>2^n + 5^n - n</math> is a multiple of <math>1000</math>.<br />
<br />
==Solution==<br />
<br />
1000 divides this expression iff 8, 125 both divide it. It should be fairly obvious that <math>n \geq 3</math>; so we may break up the initial condition into two sub-conditions.<br />
<br />
(1) <math>5^n \equiv n \pmod{8}</math>. Notice that the square of any odd integer is 1 modulo 8 (why?), so the LHS of this expression goes "5,1,5,1, ...", while the RHS goes "1,2,3,4,5,6,7,8,1, ...". The cycle length of the LHS is 2, RHS is 8, so the cycle length of the solution is <math>lcm(2,8)=8</math>. Indeed, the n that solve this equation are exactly those such that <math>n \equiv 5 \pmod{8}</math>.<br />
<br />
(2) <math>2^n \equiv n \pmod{125}</math>. This is extremely computationally intensive if you try to calculate all <math>2^1,2^2, ..., 2^{100} \pmod{125}</math>, so instead, we take a divide-and-conquer approach. In order for this expression to be true <math>2^n \equiv n \pmod{5}</math> is necessary; it shouldn't take too long for you to go through the 20 possible LHS-RHS combinations and convince yourself that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{17}</math>. <br />
<br />
With this in mind we consider <math>2^n \equiv n</math> modulo 25. By the generalized Fermat's little theorem, <math>2^{20} \equiv 1 \pmod{25}</math>, but we already have n modulo 20! Our calculation is greatly simplified. The LHS cycle length is 20, RHS cycle length is 25, the lcm is 100, in this step we need to test all the numbers between 1 to 100 that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{17}</math>. In the case that <math>n \equiv 3 \pmod{20}</math>, <math>2^n \equiv 2^3 \equiv 8</math>, and RHS goes "3,23,43,63,83"; clearly <math>n \equiv 83 \pmod{100}</math>. In the case that <math>n \equiv 17 \pmod{20}</math>, by a similar argument, <math>n \equiv 97 \pmod{100}</math>. <br />
<br />
In the final step, we need to calculate <math>2^{97}, 2^{83}</math> modulo 125. The former is simply <math>2^{-3}</math>; because <math>8*47=376=1</math> modulo 125, <math>2^{97} \equiv 47</math>. <math>2^{83}</math> is <math>2^{-17}=2{-16}*2^{-1}</math>. <math>2^{-1}=63,2^{-2}=63^2=3969=-31,2^{-4}=(-31)^2=961=-39,2^{-8}=1521=21, 2^{-16}=441,2^{-17}=63*441=7*{-31}=-217=33</math>. This time, LHS cycle is 100, RHS cycle is 125, so we need to figure out what is n modulo 500. It should be <math>n \equiv 283,297 \pmod{500}</math>.<br />
<br />
Put everything together. By the second subcondition, the only candidates < 100 are <math>283,297,782,797</math>. Apply the first subcondition, n=797 is the desired answer.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=II|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_13&diff=1497322021 AIME II Problems/Problem 132021-03-22T20:46:00Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Find the least positive integer <math>n</math> for which <math>2^n + 5^n - n</math> is a multiple of <math>1000</math>.<br />
<br />
==Solution==<br />
<br />
1000 divides this expression iff 8, 125 both divide it. It should be fairly obvious that <math>n \geq 3</math>; so we may break up the initial condition into two sub-conditions.<br />
<br />
(1) <math>5^n \equiv n \pmod{8}</math>. Notice that the square of any odd integer is 1 modulo 8 (why?), so the LHS of this expression goes "5,1,5,1, ...", while the RHS goes "1,2,3,4,5,6,7,8,1, ...". The cycle length of the LHS is 2, RHS is 8, so the cycle length of the solution is <math>lcm(2,8)=8</math>. Indeed, the n that solve this equation are exactly those such that <math>n \equiv 5 \pmod{8}</math>.<br />
<br />
(2) <math>2^n \equiv n \pmod{125}</math>. This is extremely computationally intensive if you try to calculate all <math>2^1,2^2, ..., 2^{100}=1 \pmod{125}</math>, so instead, we take a divide-and-conquer approach. In order for this expression to be true <math>2^n \equiv n \pmod{5}</math> is necessary; it shouldn't take too long for you to go through the 20 possible LHS-RHS combinations and convince yourself that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{17}</math>. <br />
<br />
With this in mind we consider <math>2^n \equiv n</math> modulo 25. By the generalized Fermat's little theorem, <math>2^{20} \equiv 1 \pmod{25}</math>, but we already have n modulo 20! Our calculation is greatly simplified. The LHS cycle length is 20, RHS cycle length is 25, the lcm is 100, in this step we need to test all the numbers between 1 to 100 that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{17}</math>. In the case that <math>n \equiv 3 \pmod{20}</math>, <math>2^n \equiv 2^3 \equiv 8</math>, and RHS goes "3,23,43,63,83"; clearly <math>n \equiv 83 \pmod{100}</math>. In the case that <math>n \equiv 17 \pmod{20}</math>, by a similar argument, <math>n \equiv 97 \pmod{100}</math>. <br />
<br />
In the final step, we need to calculate <math>2^{97}, 2^{83}</math> modulo 125. The former is simply <math>2^{-3}</math>; because <math>8*47=376=1</math> modulo 125, <math>2^{97} \equiv 47</math>. <math>2^{83}</math> is <math>2^{-17}=2{-16}*2^{-1}</math>. <math>2^{-1}=63,2^{-2}=63^2=3969=-31,2^{-4}=(-31)^2=961=-39,2^{-8}=1521=21, 2^{-16}=441,2^{-17}=63*441=7*{-31}=-217=33</math>. This time, LHS cycle is 100, RHS cycle is 125, so we need to figure out what is n modulo 500. It should be <math>n \equiv 283,297 \pmod{500}</math>.<br />
<br />
Put everything together. By the second subcondition, the only candidates < 100 are <math>283,297,782,797</math>. Apply the first subcondition, n=797 is the desired answer.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=II|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_13&diff=1497312021 AIME II Problems/Problem 132021-03-22T20:45:24Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Find the least positive integer <math>n</math> for which <math>2^n + 5^n - n</math> is a multiple of <math>1000</math>.<br />
<br />
==Solution==<br />
<br />
1000 divides this expression iff 8, 125 both divide it. It should be fairly obvious that <math>n \geq 3</math>; so we may break up the initial condition into two sub-conditions.<br />
<br />
(1) <math>5^n \equiv n \pmod{8}</math>. Notice that the square of any odd integer is 1 modulo 8 (why?), so the LHS of this expression goes "5,1,5,1, ...", while the RHS goes "1,2,3,4,5,6,7,8,1, ...". The cycle length of the LHS is 2, RHS is 8, so the cycle length of the solution is <math>lcm(2,8)=8</math>. Indeed, the n that solve this equation are exactly those such that <math>n \equiv 5 \pmod{8}</math>.<br />
<br />
(2) <math>2^n \equiv n \pmod{125}</math>. This is extremely computationally intensive if you try to calculate all <math>2^1~2^100=1 \pmod{125}</math>, so instead, we take a divide-and-conquer approach. In order for this expression to be true <math>2^n \equiv n \pmod{5}</math> is necessary; it shouldn't take too long for you to go through the 20 possible LHS-RHS combinations and convince yourself that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{17}</math>. <br />
<br />
With this in mind we consider <math>2^n \equiv n</math> modulo 25. By the generalized Fermat's little theorem, <math>2^{20} \equiv 1 \pmod{25}</math>, but we already have n modulo 20! Our calculation is greatly simplified. The LHS cycle length is 20, RHS cycle length is 25, the lcm is 100, in this step we need to test all the numbers between 1 to 100 that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{17}</math>. In the case that <math>n \equiv 3 \pmod{20}</math>, <math>2^n \equiv 2^3 \equiv 8</math>, and RHS goes "3,23,43,63,83"; clearly <math>n \equiv 83 \pmod{100}</math>. In the case that <math>n \equiv 17 \pmod{20}</math>, by a similar argument, <math>n \equiv 97 \pmod{100}</math>. <br />
<br />
In the final step, we need to calculate <math>2^{97}, 2^{83}</math> modulo 125. The former is simply <math>2^{-3}</math>; because <math>8*47=376=1</math> modulo 125, <math>2^{97} \equiv 47</math>. <math>2^{83}</math> is <math>2^{-17}=2{-16}*2^{-1}</math>. <math>2^{-1}=63,2^{-2}=63^2=3969=-31,2^{-4}=(-31)^2=961=-39,2^{-8}=1521=21, 2^{-16}=441,2^{-17}=63*441=7*{-31}=-217=33</math>. This time, LHS cycle is 100, RHS cycle is 125, so we need to figure out what is n modulo 500. It should be <math>n \equiv 283,297 \pmod{500}</math>.<br />
<br />
Put everything together. By the second subcondition, the only candidates < 100 are <math>283,297,782,797</math>. Apply the first subcondition, n=797 is the desired answer.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=II|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_13&diff=1497302021 AIME II Problems/Problem 132021-03-22T20:44:53Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Find the least positive integer <math>n</math> for which <math>2^n + 5^n - n</math> is a multiple of <math>1000</math>.<br />
<br />
==Solution==<br />
<br />
1000 divides this expression iff 8, 125 both divide it. It should be fairly obvious that <math>n \geq 3</math>; so we may break up the initial condition into two sub-conditions.<br />
<br />
(1) <math>5^n \equiv n \pmod{8}</math>. Notice that the square of any odd integer is 1 modulo 8 (why?), so the LHS of this expression goes "5,1,5,1, ...", while the RHS goes "1,2,3,4,5,6,7,8,1, ...". The cycle length of the LHS is 2, RHS is 8, so the cycle length of the solution is <math>lcm(2,8)=8</math>. Indeed, the n that solve this equation are exactly those such that <math>n \equiv 5 \pmod{8}</math>.<br />
<br />
(2) <math>2^n \equiv n \pmod{125}</math>. This is extremely computationally intensive if you try to calculate all <math>2^1~2^100=1 \pmod{125}</math>, so instead, we take a divide-and-conquer approach. In order for this expression to be true <math>2^n \equiv n \pmod{5}</math> is necessary; it shouldn't take too long for you to go through the 20 possible LHS-RHS combinations and convince yourself that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{17}</math>. <br />
<br />
With this in mind we consider <math>2^n \equiv n</math> modulo 25. By the generalized Fermat's little theorem, <math>2^20 \equiv 1 \pmod{25}</math>, but we already have n modulo 20! Our calculation is greatly simplified. The LHS cycle length is 20, RHS cycle length is 25, the lcm is 100, in this step we need to test all the numbers between 1 to 100 that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{17}</math>. In the case that <math>n \equiv 3 \pmod{20}</math>, <math>2^n \equiv 2^3 \equiv 8</math>, and RHS goes "3,23,43,63,83"; clearly <math>n \equiv 83 \pmod{100}</math>. In the case that <math>n \equiv 17 \pmod{20}</math>, by a similar argument, <math>n \equiv 97 \pmod{100}</math>. <br />
<br />
In the final step, we need to calculate <math>2^{97}, 2^{83}</math> modulo 125. The former is simply <math>2^{-3}</math>; because <math>8*47=376=1</math> modulo 125, <math>2^97 \equiv 47</math>. <math>2^83</math> is <math>2^{-17}=2{-16}*2^{-1}</math>. <math>2^{-1}=63,2^{-2}=63^2=3969=-31,2^{-4}=(-31)^2=961=-39,2^{-8}=1521=21, 2^{-16}=441,2^{-17}=63*441=7*{-31}=-217=33</math>. This time, LHS cycle is 100, RHS cycle is 125, so we need to figure out what is n modulo 500. It should be <math>n \equiv 283,297 \pmod{500}</math>.<br />
<br />
Put everything together. By the second subcondition, the only candidates < 100 are <math>283,297,782,797</math>. Apply the first subcondition, n=797 is the desired answer.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=II|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_13&diff=1497292021 AIME II Problems/Problem 132021-03-22T20:44:30Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Find the least positive integer <math>n</math> for which <math>2^n + 5^n - n</math> is a multiple of <math>1000</math>.<br />
<br />
==Solution==<br />
<br />
1000 divides this expression iff 8, 125 both divide it. It should be fairly obvious that <math>n \geq 3</math>; so we may break up the initial condition into two sub-conditions.<br />
<br />
(1) <math>5^n \equiv n \pmod{8}</math>. Notice that the square of any odd integer is 1 modulo 8 (why?), so the LHS of this expression goes "5,1,5,1, ...", while the RHS goes "1,2,3,4,5,6,7,8,1, ...". The cycle length of the LHS is 2, RHS is 8, so the cycle length of the solution is <math>lcm(2,8)=8</math>. Indeed, the n that solve this equation are exactly those such that <math>n \equiv 5 \pmod{8}</math>.<br />
<br />
(2) <math>2^n \equiv n \pmod{125}</math>. This is extremely computationally intensive if you try to calculate all <math>2^1~2^100=1 \pmod{125}</math>, so instead, we take a divide-and-conquer approach. In order for this expression to be true <math>2^n \equiv n \pmod{5}</math> is necessary; it shouldn't take too long for you to go through the 20 possible LHS-RHS combinations and convince yourself that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{17}</math>. <br />
<br />
With this in mind we consider <math>2^n \equiv n</math> modulo 25. By the generalized Fermat's little theorem, <math>2^20 \equiv 1 \pmod{25}</math>, but we already have n modulo 20! Our calculation is greatly simplified. The LHS cycle length is 20, RHS cycle length is 25, the lcm is 100, in this step we need to test all the numbers between 1 to 100 that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{17}</math>. In the case that <math>n \equiv 3 \pmod{20}</math>, <math>2^n \equiv 2^3 \equiv 8</math>, and RHS goes "3,23,43,63,83"; clearly <math>n \equiv 83 \pmod{100}</math>. In the case that <math>n \equiv 17 \pmod{20}</math>, by a similar argument, <math>n \equiv 97 \pmod{100}</math>. <br />
<br />
In the final step, we need to calculate <math>2^{97}, 2^{83}</math> modulo 125. The former is simply <math>2^{-3}</math>; because <math>8*47=376=1</math> modulo 125, <math>2^97 \equiv 47</math>. <math>2^83</math> is <math>2^{-17}=2{-16}*2^{-1}</math>. <math>2^{-1}=63,2^{-2}=63^2=3969=-31,2^{-4}=(-31)^2=961=-39,2^{-8}=1521=21,<br />
2^{-16}=441,2^{-17}=63*441=7*{-31}=-217=33</math>. This time, LHS cycle is 100, RHS cycle is 125, so we need to figure out what is n modulo 500. It should be <math>n \equiv 283,297 \pmod{500}</math>.<br />
<br />
Put everything together. By the second subcondition, the only candidates < 100 are <math>283,297,782,797</math>. Apply the first subcondition, n=797 is the desired answer.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=II|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_13&diff=1497282021 AIME II Problems/Problem 132021-03-22T20:44:00Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Find the least positive integer <math>n</math> for which <math>2^n + 5^n - n</math> is a multiple of <math>1000</math>.<br />
<br />
==Solution==<br />
<br />
1000 divides this expression iff 8, 125 both divide it. It should be fairly obvious that <math>n \geq 3</math>; so we may break up the initial condition into two sub-conditions.<br />
<br />
(1) <math>5^n \equiv n \pmod{8}</math>. Notice that the square of any odd integer is 1 modulo 8 (why?), so the LHS of this expression goes "5,1,5,1, ...", while the RHS goes "1,2,3,4,5,6,7,8,1, ...". The cycle length of the LHS is 2, RHS is 8, so the cycle length of the solution is <math>lcm(2,8)=8</math>. Indeed, the n that solve this equation are exactly those such that <math>n \equiv 5 \pmod{8}</math>.<br />
<br />
(2) <math>2^n \equiv n \pmod{125}</math>. This is extremely computationally intensive if you try to calculate all <math>2^1~2^100=1 \pmod{125}</math>, so instead, we take a divide-and-conquer approach. In order for this expression to be true <math>2^n \equiv n \pmod{5}</math> is necessary; it shouldn't take too long for you to go through the 20 possible LHS-RHS combinations and convince yourself that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{17}</math>. <br />
<br />
With this in mind we consider <math>2^n \equiv n</math> modulo 25. By the generalized Fermat's little theorem, <math>2^20 \equiv 1 \pmod{25}</math>, but we already have n modulo 20! Our calculation is greatly simplified. The LHS cycle length is 20, RHS cycle length is 25, the lcm is 100, in this step we need to test all the numbers between 1 to 100 that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{17}</math>. In the case that <math>n \equiv 3 \pmod{20}</math>, <math>2^n \equiv 2^3 \equiv 8</math>, and RHS goes "3,23,43,63,83"; clearly <math>n \equiv 83 \pmod{100}</math>. In the case that <math>n \equiv 17 \pmod{20}</math>, by a similar argument, <math>n \equiv 97 \pmod{100}</math>. <br />
<br />
In the final step, we need to calculate <math>2^97, 2^83</math> modulo 125. The former is simply <math>2^{-3}</math>; because <math>8*47=376=1</math> modulo 125, <math>2^97 \equiv 47</math>. <math>2^83</math> is <math>2^{-17}=2{-16}*2^{-1}</math>. <math>2^{-1}=63,2^{-2}=63^2=3969=-31,2^{-4}=(-31)^2=961=-39,2^{-8}=1521=21,2^{-16}=441,2^{-17}=63*441=7*{-31}=-217=33</math>. This time, LHS cycle is 100, RHS cycle is 125, so we need to figure out what is n modulo 500. It should be <math>n \equiv 283,297 \pmod{500}</math>.<br />
<br />
Put everything together. By the second subcondition, the only candidates < 100 are <math>283,297,782,797</math>. Apply the first subcondition, n=797 is the desired answer.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=II|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_15&diff=1497242021 AIME II Problems/Problem 152021-03-22T20:19:57Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Let <math>f(n)</math> and <math>g(n)</math> be functions satisfying<br />
<cmath>f(n) = \begin{cases}\sqrt{n} & \text{ if } \sqrt{n} \text{ is an integer}\\<br />
1 + f(n+1) & \text{ otherwise}<br />
\end{cases}</cmath>and<br />
<cmath>g(n) = \begin{cases}\sqrt{n} & \text{ if } \sqrt{n} \text{ is an integer}\\<br />
2 + g(n+2) & \text{ otherwise}<br />
\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>.<br />
<br />
==Solution==<br />
<br />
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>.<br />
<br />
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>.<br />
<br />
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>.<br />
<br />
Indeed, <math>f(258)=48, g(258)=84</math>, so we're done.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=II|num-b=14|after=Last Question}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_15&diff=1497232021 AIME II Problems/Problem 152021-03-22T20:19:46Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Let <math>f(n)</math> and <math>g(n)</math> be functions satisfying<br />
<cmath>f(n) = \begin{cases}\sqrt{n} & \text{ if } \sqrt{n} \text{ is an integer}\\<br />
1 + f(n+1) & \text{ otherwise}<br />
\end{cases}</cmath>and<br />
<cmath>g(n) = \begin{cases}\sqrt{n} & \text{ if } \sqrt{n} \text{ is an integer}\\<br />
2 + g(n+2) & \text{ otherwise}<br />
\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>.<br />
<br />
==Solution==<br />
<br />
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>.<br />
<br />
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>.<br />
<br />
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>.<br />
<br />
Indeed, <math>f(258)=48, g(258)=84</math>, so we're done.<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=II|num-b=14|after=Last Question}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_3&diff=1496552021 AIME I Problems/Problem 32021-03-17T17:23:48Z<p>Dearpasserby: /* Solution 1 */</p>
<hr />
<div>==Problem==<br />
Find the number of positive integers less than <math>1000</math> that can be expressed as the difference of two integral powers of <math>2.</math><br />
<br />
==Solution 1==<br />
We want to find the number of positive integers <math>n<1000</math> which can be written in the form <math>n = 2^a - 2^b</math> for some non-negative integers <math>a > b \ge 0</math> (note that if <math>a=b</math>, then <math>2^a-2^b = 0</math>). We first observe <math>a</math> must be at most 10; if <math>a \ge 11</math>, then <math>2^a - 2^b \ge 2^{10} > 1000</math>. As <math>2^{10} = 1024 \approx 1000</math>, we can first choose two different numbers <math>a > b</math> from the set <math>\{0,1,2,\ldots,10\}</math> in <math>\binom{11}{2}=55</math> ways. This includes <math>(a,b) = (10,0)</math>, <math>(10,1)</math>, <math>(10,2)</math>, <math>(10,3)</math>, <math>(10,4)</math> which are invalid as <math>2^a - 2^b > 1000</math> in this case. For all other choices <math>a</math> and <math>b</math>, the value of <math>2^a - 2^b</math> is less than 1000.<br />
<br />
We claim that for all other choices of <math>a</math> and <math>b</math>, the values of <math>2^a - 2^b</math> are pairwise distinct. More specifically, if <math>(a_1,b_1) \neq (a_2,b_2)</math> where <math>10 \ge a_1 > b_1 \ge 0</math> and <math>10 \ge a_2 > b_2 \ge 0</math>, we must show that <math>2^{a_1}-2^{b_1} \neq 2^{a_2} - 2^{b_2}</math>. Suppose otherwise for sake of contradiction; rearranging yields <math>2^{a_1}+2^{b_2} = 2^{a_2}+2^{b_1}</math>. We use the fact that every positive integer has a unique binary representation:<br />
<br />
If <math>a_1 \neq b_2</math> then <math>\{a_1,b_2\} = \{a_2,b_1\}</math>; from here we can deduce either <math>a_1=a_2</math> and <math>b_1=b_2</math> (contradicting the assumption that <math>(a_1,b_1) \neq (a_2,b_2)</math>, or <math>a_1=b_1</math> and <math>a_2=b_2</math> (contradicting the assumption <math>a_1>b_1</math> and <math>a_2>b_2</math>).<br />
<br />
If <math>a_1 = b_2</math> then <math>2^{a_1}+2^{b_2} = 2 \times 2^{a_1}</math>, and it follows that <math>a_1=a_2=b_1=b_2</math>, also contradicting the assumption <math>(a_1,b_1) \neq (a_2,b_2)</math>. Hence we obtain contradiction.*<br />
<br />
Then there are <math>\binom{11}{2}-5</math> choices for <math>(a,b)</math> for which <math>2^a - 2^b</math> is a positive integer less than 1000; by the above claim, each choice of <math>(a,b)</math> results in a different positive integer <math>n</math>. Then there are <math>55-5 = \boxed{050}</math> integers which can be expressed as a difference of two powers of 2.<br />
<br />
<br />
*Note: The uniqueness of binary representation could be rather easily proven, but if you cannot convince yourself on the spot that this is the case, consider the following alternative proof. Let <math>(a_1,b_1) \neq (a_2,b_2)</math> where <math>10 \ge a_1 > b_1 \ge 0</math> and <math>10 \ge a_2 > b_2 \ge 0</math> and <math>2^{a_1}-2^{b_1} = 2^{a_2} - 2^{b_2}</math>, for the sake of contradiction. Therefore <math>\deg_{2}(2^{a_1}-2^{b_1})=\deg_{2}(2^{a_2}-2^{b_2})</math>, or <math>b_1=b_2</math>. Plugging in, we see that <math>2^{a_1}=2^{a_2}</math>, or <math>a_1=a_2</math>, contradiction.<br />
<br />
Note by Ross Gao<br />
<br />
==Solution 2 (Casework)==<br />
<b>Case 1:</b> When our answer is in the form <math>2^n-2^i</math>, where <math>i</math> is an integer such that <math>0\le i\le 4</math>. <br />
<br />
We start with the subcase where it is <math>2^n-2^0</math>, for some integer <math>n</math> where <math>n>0</math> (this is because the case where <math>n=0</math> yields <math>2^0-2^0=0</math>, which doesn't work because it must be a positive integer.) <br />
Note that <math>2^{10}=1024</math>, and <math>2^9=512</math>. Our answer needs to be less than <math>1000</math>, so the maximum possible result (in this case) is <math>2^9-2^0</math>. Our lowest result is <math>2^1-2^0</math>. All the positive powers of two less than <math>1024</math> work, so we have <math>9</math> possibilities for this subcase. For subcases <math>i=1, i=2, i=3,</math> and <math>i=4</math>, we have <math>8, 7, 6,</math> and <math>5</math> possibilities, respectively.<br />
<br />
<b>Case 2:</b> When our answer is in the form of <math>2^n-2^j</math>, where <math>j</math> is an integer such that <math>5\le j\le 9</math>.<br />
<br />
We can start with the subcase where <math>j=5</math>. We notice that <math>2^5=32</math>, and <math>2^{10}-2^5=992</math> which is less than <math>1000</math>, so the greatest result in this subcase is actually <math>2^{10}-2^5</math>, and the lowest is <math>2^6-2^5</math>. Thus, we have <math>5</math> possibilities. For the other four subcases, we have <math>4, 3, 2,</math> and <math>1</math> possibilities, respectively.<br />
<br />
<b>Answer:</b><br />
We note that these are our only cases, as numbers in the form of <math>2^n-2^{10}</math> and beyond are greater than <math>1000</math>. <br />
<br />
Thus, our result is <math>9+8+7+6+5+5+4+3+2+1=(9+8+7+6+5+4+3+2+1)+5=\boxed{50}</math>. ~jehu26<br />
<br />
==Solution 3 (Bash)==<br />
We look for all positive integers of the form <math>2^a-2^b<1000,</math> where <math>0\leq b<a.</math> Performing casework on <math>a,</math> we can enumerate all possibilities in the table below:<br />
<cmath>\begin{array}{c|c}<br />
\boldsymbol{a} & \boldsymbol{b} \\ <br />
\hline <br />
& \\ [-2ex]<br />
1 & 0 \\ <br />
2 & 0,1 \\<br />
3 & 0,1,2 \\<br />
4 & 0,1,2,3 \\<br />
5 & 0,1,2,3,4 \\<br />
6 & 0,1,2,3,4,5 \\<br />
7 & 0,1,2,3,4,5,6 \\<br />
8 & 0,1,2,3,4,5,6,7 \\<br />
9 & 0,1,2,3,4,5,6,7,8 \\<br />
10 & \xcancel{0},\xcancel{1},\xcancel{2},\xcancel{3},\xcancel{4},5,6,7,8,9<br />
\end{array}</cmath><br />
As indicated by the X-marks, the ordered pairs <math>(a,b)=(10,0),(10,1),(10,2),(10,3),(10,4)</math> generate <math>2^a-2^b>1000,</math> which are invalid.<br />
<br />
<b><i>Note that each of the remaining ordered pairs generates one unique desired positive integer.</i></b> We prove as follows:<br />
<br />
# The positive integers generated for each value of <math>a</math> are clearly different.<br />
# For all integers <math>1\leq k\leq9,</math> the largest positive integer generated for <math>a=k</math> is <math>1</math> less than the smallest positive integer generated for <math>a=k+1.</math><br />
<br />
Together, we justified our claim in bold. Our answer is <cmath>1+2+3+4+5+6+7+8+9+5=\boxed{050}.</cmath><br />
<br />
~MRENTHUSIASM<br />
<br />
==Solution 4==<br />
First, you need to notice that it is impossible to have overlapping, making the problem easier.<br />
<br />
Case 1 : <math>2^0</math><br />
There are <math>9</math> ways here, from <math>2^1</math> to <math>2^9</math><br />
<br />
It is easy to see here that this continues all the way down to one. However, when the case gets to <math>32</math>, there are 5 ways instead of 4 because <math>2^{10}-2^5</math> is smaller than 1000.<br />
<br />
Thus, <math>9+8+7+6+5+5+4+3+2+1 = 50</math><br />
<br />
So the answer is <math>\boxed{050}</math><br />
<br />
==Video Solution by Punxsutawney Phil==<br />
https://youtube.com/watch?v=H17E9n2nIyY&t=569s<br />
<br />
==Video Solution==<br />
https://youtu.be/M3DsERqhiDk?t=749<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=2|num-a=4}}<br />
<br />
[[Category:Introductory Number Theory Problems]]<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_15&diff=1496282021 AIME I Problems/Problem 152021-03-16T23:28:51Z<p>Dearpasserby: /* Solution 1 */</p>
<hr />
<div>==Problem==<br />
Let <math>S</math> be the set of positive integers <math>k</math> such that the two parabolas<cmath>y=x^2-k~~\text{and}~~x=2(y-20)^2-k</cmath>intersect in four distinct points, and these four points lie on a circle with radius at most <math>21</math>. Find the sum of the least element of <math>S</math> and the greatest element of <math>S</math>.<br />
<br />
===Solution 1===<br />
<br />
Make the translation <math>y \rightarrow y+20</math> to obtain <math>20+y=x^2-k , x=2y^2-k</math>. Multiply the first equation by 2 and sum, we see that <math>2(x^2+y^2)=3k+40+2y+x</math>. Completing the square gives us <math>(y- \frac{1}{2})^2+(x - \frac{1}{4})^2 = \frac{325+24k}{16}</math>; this explains why the two parabolas intersect at four points that lie on a circle*. For the upper bound, observe that <math>LHS \leq 21^2=441 \rightarrow 24k \leq 6731</math>, so <math>k \leq 280</math>. <br />
<br />
For the lower bound, we need to ensure there are 4 intersections to begin with. (Here I'm using the un-translated coordinates.) Draw up a graph, and realize that two intersections are guaranteed, on the so called "right branch" of <math>y=x^2-k</math>. As we increase the value of k, two more intersections appear on the "left branch." <br />
<br />
<math>k=4</math> does not work because the "leftmost" point of <math>x=2(y-20)^2-4</math> is <math>(-4,20)</math> which lies to the right of <math>(-\sqrt{24}, 20)</math>, which is on the graph <math>y=x^2-4</math>. While technically speaking this doesn't prove that there are no intersections (why?), drawing the graph should convince you that this is the case. Clearly, no k less than 4 works either.<br />
<br />
<math>k=5</math> does work because the two graphs intersect at <math>(-5,20)</math>, and by drawing the graph, you realize this is not a tangent point and there is in fact another intersection nearby, due to slope. Therefore, the answer is <math>5+280=285</math>.<br />
<br />
<br />
*In general, (Assuming four intersections exist) when two conics intersect, if one conic can be written as <math>ax^2+by^2=f(x,y)</math> and the other as <math>cx^2+dy^2=g(x,y)</math> for f,g polynomials of degree at most 1, whenever <math>(a,b),(c,d)</math> are linearly independent, we can combine the two equations and then complete the square to achieve <math>(x-p)^2+(y-q)^2=r^2</math>. We can also combine these two equations to form a parabola, or a hyperbola, or an ellipse. When <math>(a,b),(c,d)</math> are not L.I., the intersection points instead lie on a line, which is a circle of radius infinity. When the two conics only have 3,2 or 1 intersection points, the statement that all these points lie on a circle is trivially true. <br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=14|after=Last problem}}<br />
<br />
[[Category:Intermediate Algebra Problems]]<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_15&diff=1496002021 AIME I Problems/Problem 152021-03-16T15:17:02Z<p>Dearpasserby: /* Solution 1 */</p>
<hr />
<div>==Problem==<br />
Let <math>S</math> be the set of positive integers <math>k</math> such that the two parabolas<cmath>y=x^2-k~~\text{and}~~x=2(y-20)^2-k</cmath>intersect in four distinct points, and these four points lie on a circle with radius at most <math>21</math>. Find the sum of the least element of <math>S</math> and the greatest element of <math>S</math>.<br />
<br />
===Solution 1===<br />
<br />
Make the translation <math>y \rightarrow y+20</math> to obtain <math>20+y=x^2-k , x=2y^2-k</math>. Multiply the first equation by 2 and sum, we see that <math>2(x^2+y^2)=3k+40+2y+x</math>. Completing the square gives us <math>(y- \frac{1}{2})^2+(x - \frac{1}{4})^2 = \frac{325+24k}{16}</math>; this explains why the two parabolas intersect at four points that lie on a circle*. For the upper bound, observe that <math>LHS \leq 21^2=441 \rightarrow 24k \leq 6731</math>, so <math>k \leq 280</math>. <br />
<br />
For the lower bound, we need to ensure there are 4 intersections to begin with. (Here I'm using the un-translated coordinates.)<br />
<br />
<math>k=4</math> does not work because the "leftmost" point of <math>x=2(y-20)^2-k</math> is <math>(-4,20)</math> which lies to the right of <math>(-\sqrt{24}, 20)</math>, which is on the graph <math>y=x^2-k</math>. Clearly, no k less than 4 works either.<br />
<br />
<math>k=5</math> does work because the two graphs intersect at <math>(-5,20)</math>, and by drawing the graph, you realize this is not a tangent point and there is in fact another intersection, due to slope. Therefore, the answer is <math>5+280=285</math>.<br />
<br />
<br />
*In general, (Assuming four intersections exist) when two conics intersect, if one conic can be written as <math>ax^2+by^2=f(x,y)</math> and the other as <math>cx^2+dy^2=g(x,y)</math> for f,g polynomials of degree at most 1, whenever <math>(a,b),(c,d)</math> are linearly independent, we can combine the two equations and then complete the square to achieve <math>(x-p)^2+(y-q)^2=r^2</math>. We can also combine these two equations to form a parabola, or a hyperbola, or an ellipse. When <math>(a,b),(c,d)</math> are not L.I., the intersection points instead lie on a line, which is a circle of radius infinity. When the two conics only have 3,2 or 1 intersection points, the statement that all these points lie on a circle is trivially true. <br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=14|after=Last problem}}<br />
<br />
[[Category:Intermediate Algebra Problems]]<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_15&diff=1495992021 AIME I Problems/Problem 152021-03-16T15:15:55Z<p>Dearpasserby: /* Solution 1 */</p>
<hr />
<div>==Problem==<br />
Let <math>S</math> be the set of positive integers <math>k</math> such that the two parabolas<cmath>y=x^2-k~~\text{and}~~x=2(y-20)^2-k</cmath>intersect in four distinct points, and these four points lie on a circle with radius at most <math>21</math>. Find the sum of the least element of <math>S</math> and the greatest element of <math>S</math>.<br />
<br />
===Solution 1===<br />
<br />
Make the translation <math>y \rightarrow y+20</math> to obtain <math>20+y=x^2-k , x=2y^2-k</math>. Multiply the first equation by 2 and sum, we see that <math>2(x^2+y^2)=3k+40+2y+x</math>. Completing the square gives us <math>(y- \frac{1}{2})^2+(x - \frac{1}{4})^2 = \frac{325+24k}{16}</math>; this explains why the two parabolas intersect at four points that lie on a circle*. For the upper bound, observe that <math>LHS \leq 21^2=441 \rightarrow 24k \leq 6731</math>, so <math>k \leq 280</math>. <br />
<br />
For the lower bound, we need to ensure there are 4 intersections to begin with. (Here I'm using the un-translated coordinates.)<br />
<br />
<math>k=4</math> does not work because the "leftmost" point of <math>x=2(y-20)^2-k</math> is <math>(-4,20)</math> which lies to the right of <math>(-\sqrt{24}, 20)</math>, which is on the graph <math>y=x^2-k</math>. <br />
<br />
<math>k=5</math> does work because the two graphs intersect at <math>(-5,20)</math>, and by drawing the graph, you realize this is not a tangent point and there is in fact another intersection, due to slope. Therefore, the answer is <math>5+280=285</math>.<br />
<br />
<br />
*In general, (Assuming four intersections exist) when two conics intersect, if one conic can be written as <math>ax^2+by^2=f(x,y)</math> and the other as <math>cx^2+dy^2=g(x,y)</math> for f,g polynomials of degree at most 1, whenever <math>(a,b),(c,d)</math> are linearly independent, we can combine the two equations and then complete the square to achieve <math>(x-p)^2+(y-q)^2=r^2</math>. We can also combine these two equations to form a parabola, or a hyperbola, or an ellipse. When <math>(a,b),(c,d)</math> are not L.I., the intersection points instead lie on a line, which is a circle of radius infinity. When the two conics only have 3,2 or 1 intersection points, the statement that all these points lie on a circle is trivially true. <br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=14|after=Last problem}}<br />
<br />
[[Category:Intermediate Algebra Problems]]<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_15&diff=1495292021 AIME I Problems/Problem 152021-03-15T02:49:33Z<p>Dearpasserby: /* Solution 1 */</p>
<hr />
<div>==Problem==<br />
Let <math>S</math> be the set of positive integers <math>k</math> such that the two parabolas<cmath>y=x^2-k~~\text{and}~~x=2(y-20)^2-k</cmath>intersect in four distinct points, and these four points lie on a circle with radius at most <math>21</math>. Find the sum of the least element of <math>S</math> and the greatest element of <math>S</math>.<br />
<br />
===Solution 1===<br />
<br />
Make the translation <math>y \rightarrow y+20</math> to obtain <math>20+y=x^2-k , x=2y^2-k</math>. Multiply the first equation by 2 and sum, we see that <math>2(x^2+y^2)=3k+40+2y+x</math>. Completing the square gives us <math>(y- \frac{1}{2})^2+(x - \frac{1}{4})^2 = \frac{325+24k}{16}</math>; this explains why the two parabolas intersect at four points that lie on a circle*. For the upper bound, observe that <math>LHS \leq 21^2=441 \rightarrow 24k \leq 6731</math>, so <math>k \leq 280</math>. <br />
<br />
For the lower bound, we need to ensure there are 4 intersections to begin with. A quick check shows k=5 works while k=4 does not. Therefore, the answer is 5+280=285.<br />
<br />
*In general, (Assuming four intersections exist) when two conics intersect, if one conic can be written as <math>ax^2+by^2=f(x,y)</math> and the other as <math>cx^2+dy^2=g(x,y)</math> for f,g polynomials of degree at most 1, whenever <math>(a,b),(c,d)</math> are linearly independent, we can combine the two equations and then complete the square to achieve <math>(x-p)^2+(y-q)^2=r^2</math>. We can also combine these two equations to form a parabola, or a hyperbola, or an ellipse. When <math>(a,b),(c,d)</math> are not L.I., the intersection points instead lie on a line, which is a circle of radius infinity. When the two conics only have 3,2 or 1 intersection points, the statement that all these points lie on a circle is trivially true. <br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=14|after=Last problem}}<br />
<br />
[[Category:Intermediate Algebra Problems]]<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_5&diff=1492632021 AIME I Problems/Problem 52021-03-12T19:04:42Z<p>Dearpasserby: /* Solution 3 */</p>
<hr />
<div>==Problem==<br />
Call a three-term strictly increasing arithmetic sequence of integers special if the sum of the squares of the three terms equals the product of the middle term and the square of the common difference. Find the sum of the third terms of all special sequences.<br />
<br />
==Solution 1==<br />
Let the terms be <math>a-b</math>, <math>a</math>, and <math>a+b</math>. Then we want <math>(a-b)^2+a^2+(a+b)^2=ab^2</math>, or <math>3a^2+2b^2=ab^2</math>. Rearranging, we get <math>b^2=\frac{3a^2}{a-2}</math>. Simplifying further, <math>b^2=3a+6+\frac{12}{a-2}</math>. Looking at this second equation, since the right side must be an integer, <math>a-2</math> must equal <math>\pm1, 2, 3, 4, 6, 12</math>. Looking at the first equation, we see <math>a>2</math> since <math>b^2</math> is positive. This means we must test <math>a=3, 4, 5, 6, 8, 14</math>. After testing these, we see that only <math>a=5</math> and <math>a=14</math> work which give <math>b=5</math> and <math>b=7</math> respectively. Thus the answer is <math>10+21=\boxed{031}</math>.<br />
~JHawk0224<br />
<br />
==Solution 2==<br />
Let the common difference be <math> d </math> and let the middle term be <math> x </math>. Then, we have that the sequence is<br />
<cmath>x-d,~x,~x+d.</cmath><br />
This means that the sum of the sequence is <br />
<cmath> (x-d)^2+x^2+(x+d)^2=x^2-2xd+d^2+x^2+x^2+2xd+d^2=3x^2+2d^2. </cmath><br />
We know that this must be equal to <math>xd^2,</math> so we can write that<br />
<cmath>3x^2+2d^2=xd^2,</cmath><br />
and it follows that<br />
<cmath>3x^2-xd^2+2d^2=3x^2-\left(d^2\right)x+2d^2=0.</cmath><br />
<br />
Now, we can treat <math> d </math> as a constant and use the quadratic formula to get<br />
<cmath>x=\frac{d^2\pm \sqrt{d^4-4(3)(2d^2)}}{6}.</cmath><br />
We can factor pull <math> d^2 </math> out of the square root to get<br />
<cmath>x=\frac{d^2\pm d\sqrt{d^2-24}}{6}.</cmath><br />
Here, it is easy to test values of <math> d </math>. We find that <math> d=5 </math> and <math> d=7 </math> are the only positive integer values of <math> d </math> that make <math> \sqrt{d^2-24} </math> a positive integer. <math> d=5 </math> gives <math> x=5 </math> and <math> x=\frac{10}{3} </math>, but we can ignore the latter. <math> d=7 </math> gives <math> x=14 </math>, as well as a fraction which we can ignore. <br />
<br />
Since <math> d=5,~x=5 </math> and <math> d=7, x=14 </math> are the only two solutions and we want the sum of the third terms, our answer is <math> (5+5)+(7+14)=10+21=\boxed{031} </math>. -BorealBear<br />
<br />
==Solution 3==<br />
Proceed as in solution 2, until we reach <cmath>3x^2+2d^2=xd^2,</cmath> Write <br />
<br />
<math>d^2=\frac{3x^2}{x-2}</math>, it follows that <math>x-2=3k^2</math> for some (positive) integer k and <math>k \mid x</math>.<br />
<br />
Taking both sides modulo <math>k</math>, <math>-2 \equiv 0 \pmod{k}</math>, so <math>k \mid 2 \rightarrow k=1,2</math>. <br />
<br />
When <math>k=1</math>, we have <math>x=5</math> and <math>d=5</math>. When <math>k=2</math>, we have <math>x=14</math> and <math>d=7</math>.<br />
Summing the two cases, we have <math>10+21=\framebox{031}</math>.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=4|num-a=6}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_5&diff=1492622021 AIME I Problems/Problem 52021-03-12T19:04:08Z<p>Dearpasserby: /* Solution 3 */</p>
<hr />
<div>==Problem==<br />
Call a three-term strictly increasing arithmetic sequence of integers special if the sum of the squares of the three terms equals the product of the middle term and the square of the common difference. Find the sum of the third terms of all special sequences.<br />
<br />
==Solution 1==<br />
Let the terms be <math>a-b</math>, <math>a</math>, and <math>a+b</math>. Then we want <math>(a-b)^2+a^2+(a+b)^2=ab^2</math>, or <math>3a^2+2b^2=ab^2</math>. Rearranging, we get <math>b^2=\frac{3a^2}{a-2}</math>. Simplifying further, <math>b^2=3a+6+\frac{12}{a-2}</math>. Looking at this second equation, since the right side must be an integer, <math>a-2</math> must equal <math>\pm1, 2, 3, 4, 6, 12</math>. Looking at the first equation, we see <math>a>2</math> since <math>b^2</math> is positive. This means we must test <math>a=3, 4, 5, 6, 8, 14</math>. After testing these, we see that only <math>a=5</math> and <math>a=14</math> work which give <math>b=5</math> and <math>b=7</math> respectively. Thus the answer is <math>10+21=\boxed{031}</math>.<br />
~JHawk0224<br />
<br />
==Solution 2==<br />
Let the common difference be <math> d </math> and let the middle term be <math> x </math>. Then, we have that the sequence is<br />
<cmath>x-d,~x,~x+d.</cmath><br />
This means that the sum of the sequence is <br />
<cmath> (x-d)^2+x^2+(x+d)^2=x^2-2xd+d^2+x^2+x^2+2xd+d^2=3x^2+2d^2. </cmath><br />
We know that this must be equal to <math>xd^2,</math> so we can write that<br />
<cmath>3x^2+2d^2=xd^2,</cmath><br />
and it follows that<br />
<cmath>3x^2-xd^2+2d^2=3x^2-\left(d^2\right)x+2d^2=0.</cmath><br />
<br />
Now, we can treat <math> d </math> as a constant and use the quadratic formula to get<br />
<cmath>x=\frac{d^2\pm \sqrt{d^4-4(3)(2d^2)}}{6}.</cmath><br />
We can factor pull <math> d^2 </math> out of the square root to get<br />
<cmath>x=\frac{d^2\pm d\sqrt{d^2-24}}{6}.</cmath><br />
Here, it is easy to test values of <math> d </math>. We find that <math> d=5 </math> and <math> d=7 </math> are the only positive integer values of <math> d </math> that make <math> \sqrt{d^2-24} </math> a positive integer. <math> d=5 </math> gives <math> x=5 </math> and <math> x=\frac{10}{3} </math>, but we can ignore the latter. <math> d=7 </math> gives <math> x=14 </math>, as well as a fraction which we can ignore. <br />
<br />
Since <math> d=5,~x=5 </math> and <math> d=7, x=14 </math> are the only two solutions and we want the sum of the third terms, our answer is <math> (5+5)+(7+14)=10+21=\boxed{031} </math>. -BorealBear<br />
<br />
==Solution 3==<br />
Proceed as in solution 1, until we reach <cmath>3x^2+2d^2=xd^2,</cmath> Write <br />
<br />
<math>d^2=\frac{3x^2}{x-2}</math>, it follows that <math>x-2=3k^2</math> for some (positive) integer k and <math>k \mid x</math>.<br />
<br />
Taking both sides modulo <math>k</math>, <math>-2 \equiv 0 \pmod{k}</math>, so <math>k \mid 2 \rightarrow k=1,2</math>. <br />
<br />
When <math>k=1</math>, we have <math>x=5</math> and <math>d=5</math>. When <math>k=2</math>, we have <math>x=14</math> and <math>d=7</math>.<br />
Summing the two cases, we have <math>10+21=\framebox{031}</math>.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=4|num-a=6}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_15&diff=1492602021 AIME I Problems/Problem 152021-03-12T18:42:53Z<p>Dearpasserby: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
Let <math>S</math> be the set of positive integers <math>k</math> such that the two parabolas<cmath>y=x^2-k~~\text{and}~~x=2(y-20)^2-k</cmath>intersect in four distinct points, and these four points lie on a circle with radius at most <math>21</math>. Find the sum of the least element of <math>S</math> and the greatest element of <math>S</math>.<br />
<br />
==Solution==<br />
===Solution 1===<br />
With binary search you can narrow down the k value. Newton raphson method let you narrow down the x and y solution for that specific k value. With 3 (x,y) pairs you can find radius of the circle. <br />
<br />
You end up finding the bounds of 5 and 280. The sum is 285.<br />
<br />
~Lopkiloinm<br />
<br />
===Solution 2===<br />
<br />
Make the translation <math>x \rightarrow x+20</math> to obtain <math>20+x=y^2-k , y=2x^2-k</math>. Multiply the first equation by 2 and sum, we see that <math>2(x^2+y^2)=3k+40+2x+y</math>. Completing the square gives us <math>(x- \frac{1}{2})^2+(y - \frac{1}{4})^2 = \frac{325+24k}{16}</math>; this explains why the two parabolas intersect at four points that lie on a circle*. For the upper bound, observe that <math>LHS \leq 21^2=441 \rightarrow 24k \leq 6731</math>, so <math>k \leq 280</math>. <br />
<br />
For the lower bound, we need to ensure there are 4 intersections to begin with. A quick check shows k=5 works while k=4 does not. Therefore, the answer is 5+280=285.<br />
<br />
*In general, (Assuming four intersections exist) when two conics intersect, if one conic can be written as <math>ax^2+by^2=f(x,y)</math> and the other as <math>cx^2+dy^2=g(x,y)</math> for f,g polynomials of degree at most 1, whenever <math>(a,b),(c,d)</math> are linearly independent, we can combine the two equations and then complete the square to achieve <math>(x-p)^2+(y-q)^2=r^2</math>. We can also combine these two equations to form a parabola, or a hyperbola, or an ellipse. When <math>(a,b),(c,d)</math> are not L.I., the intersection points instead lie on a line, which is a circle of radius infinity. When the two conics only have 3,2 or 1 intersection points, the statement that all these points lie on a circle is trivially true. <br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=14|after=Last problem}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_15&diff=1492592021 AIME I Problems/Problem 152021-03-12T18:42:16Z<p>Dearpasserby: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
Let <math>S</math> be the set of positive integers <math>k</math> such that the two parabolas<cmath>y=x^2-k~~\text{and}~~x=2(y-20)^2-k</cmath>intersect in four distinct points, and these four points lie on a circle with radius at most <math>21</math>. Find the sum of the least element of <math>S</math> and the greatest element of <math>S</math>.<br />
<br />
==Solution==<br />
===Solution 1===<br />
With binary search you can narrow down the k value. Newton raphson method let you narrow down the x and y solution for that specific k value. With 3 (x,y) pairs you can find radius of the circle. <br />
<br />
You end up finding the bounds of 5 and 280. The sum is 285.<br />
<br />
~Lopkiloinm<br />
<br />
===Solution 2===<br />
<br />
Make the translation <math>x \rightarrow x+20</math> to obtain <math>20+x=y^2-k , y=2x^2-k</math>. Multiply the first equation by 2 and sum, we see that <math>2(x^2+y^2)=3k+40+2x+y</math>. Completing the square gives us <math>(x- \frac{1}{2})^2+(y - \frac{1}{4})^2 = \frac{325+24k}{16}</math>; this explains why the two parabolas intersect at four points that lie on a circle*. For the upper bound, observe that <math>LHS \leq 21^2=441 \rightarrow 24k \leq 6731</math>, so <math>k \leq 280</math>. <br />
<br />
For the lower bound, we need to ensure there are 4 intersections to begin with. A quick check shows k=5 works while k=4 does not. Therefore, the answer is 5+280=285.<br />
<br />
*In general, (Assuming four intersections exist) when two conics intersect, if one conic can be written as <math>ax^2+by^2=f(x,y)</math> and the other as <math>cx^2+dy^2=g(x,y)</math> for f,g polynomials of degree at most 1, whenever <math>(a,b),(c,d)</math> are linearly independent, we can combine the two equations and then complete the square. We can also combine these two equations to form a parabola, or a hyperbola, or an ellipse. When <math>(a,b),(c,d)</math> are not L.I., the intersection points instead lie on a line, which is a circle of radius infinity. When the two conics only have 3,2 or 1 intersection points, the statement that all these points lie on a circle is trivially true. <br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=14|after=Last problem}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_15&diff=1492282021 AIME I Problems/Problem 152021-03-12T15:14:26Z<p>Dearpasserby: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
Let <math>S</math> be the set of positive integers <math>k</math> such that the two parabolas<cmath>y=x^2-k~~\text{and}~~x=2(y-20)^2-k</cmath>intersect in four distinct points, and these four points lie on a circle with radius at most <math>21</math>. Find the sum of the least element of <math>S</math> and the greatest element of <math>S</math>.<br />
<br />
==Solution==<br />
===Solution 1===<br />
With binary search you can narrow down the k value. Newton raphson method let you narrow down the x and y solution for that specific k value. With 3 (x,y) pairs you can find radius of the circle. <br />
<br />
You end up finding the bounds of 5 and 280. The sum is 285.<br />
<br />
~Lopkiloinm<br />
<br />
===Solution 2===<br />
<br />
Make the translation <math>x \rightarrow x+20</math> to obtain <math>20+x=y^2-k , y=2x^2-k</math>. Multiply the first equation by 2 and sum, we see that <math>2(x^2+y^2)=3k+40+2x+y</math>. Completing the square gives us <math>(x- \frac{1}{2})^2+(y - \frac{1}{4})^2 = \frac{325+24k}{16}</math>; this explains why the two parabolas intersect at four points that lie on a circle*. For the upper bound, observe that <math>LHS \leq 21^2=441 \rightarrow 24k \leq 6731</math>, so <math>k \leq 280</math>. <br />
<br />
For the lower bound, we need to ensure there are 4 intersections to begin with. A quick check shows k=5 works while k=4 does not. Therefore, the answer is 5+280=285.<br />
<br />
*In general, this problem tells us that the intersection points of two conics without xy terms usually lie on a circle. When is this true/false will be left to the reader.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=14|after=Last problem}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_15&diff=1492262021 AIME I Problems/Problem 152021-03-12T15:04:13Z<p>Dearpasserby: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
Let <math>S</math> be the set of positive integers <math>k</math> such that the two parabolas<cmath>y=x^2-k~~\text{and}~~x=2(y-20)^2-k</cmath>intersect in four distinct points, and these four points lie on a circle with radius at most <math>21</math>. Find the sum of the least element of <math>S</math> and the greatest element of <math>S</math>.<br />
<br />
==Solution==<br />
===Solution 1===<br />
With binary search you can narrow down the k value. Newton raphson method let you narrow down the x and y solution for that specific k value. With 3 (x,y) pairs you can find radius of the circle. <br />
<br />
You end up finding the bounds of 5 and 280. The sum is 285.<br />
<br />
~Lopkiloinm<br />
<br />
===Solution 2===<br />
<br />
Make the translation <math>x \rightarrow x+20</math> to obtain <math>20+x=y^2-k , y=2x^2-k</math>. Multiply the second equation by 2 and sum, we see that <math>2(x^2+y^2)=3k+40+2x+y</math>. Completing the square gives us <math>(x- \frac{1}{2})^2+(y - \frac{1}{4})^2 = \frac{325+24k}{16}</math>; this explains why the two parabolas intersect at four points that lie on a circle*. For the upper bound, observe that <math>LHS \leq 21^2=441 \rightarrow 24k \leq 6731</math>, so <math>k \leq 280</math>. <br />
<br />
For the lower bound, we need to ensure there are 4 intersections to begin with. A quick check shows k=5 works while k=4 does not. Therefore, the answer is 5+280=285.<br />
<br />
*In general, this problem tells us that the intersection points of two conics without xy terms usually lie on a circle. When is this true/false will be left to the reader.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=14|after=Last problem}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_5&diff=1492252021 AIME I Problems/Problem 52021-03-12T14:56:53Z<p>Dearpasserby: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
Call a three-term strictly increasing arithmetic sequence of integers special if the sum of the squares of the three terms equals the product of the middle term and the square of the common difference. Find the sum of the third terms of all special sequences.<br />
<br />
==Solution==<br />
Let the terms be <math>a-b</math>, <math>a</math>, and <math>a+b</math>. Then we want <math>(a-b)^2+a^2+(a+b)^2=ab^2</math>, or <math>3a^2+2b^2=ab^2</math>. Rearranging, we get <math>b^2=\frac{3a^2}{a-2}</math>. Simplifying further, <math>b^2=3a+6+\frac{12}{a-2}</math>. Looking at this second equation, since the right side must be an integer, <math>a-2</math> must equal <math>\pm1, 2, 3, 4, 6, 12</math>. Looking at the first equation, we see <math>a>2</math> since <math>b^2</math> is positive. This means we must test <math>a=3, 4, 5, 6, 8, 14</math>. After testing these, we see that only <math>a=5</math> and <math>a=14</math> work which give <math>b=5</math> and <math>b=7</math> respectively. Thus the answer is <math>10+21=\boxed{031}</math>.<br />
~JHawk0224<br />
<br />
===Solution 1===<br />
Let the common difference be <math> d </math> and let the middle term be <math> x </math>. Then, we have that the sequence is<br />
<cmath>x-d,~x,~x+d.</cmath><br />
This means that the sum of the sequence is <br />
<cmath> (x-d)^2+x^2+(x+d)^2=x^2-2xd+d^2+x^2+x^2+2xd+d^2=3x^2+2d^2. </cmath><br />
We know that this must be equal to <math>xd^2,</math> so we can write that<br />
<cmath>3x^2+2d^2=xd^2,</cmath><br />
and it follows that<br />
<cmath>3x^2-xd^2+2d^2=3x^2-\left(d^2\right)x+2d^2=0.</cmath><br />
<br />
Now, we can treat <math> d </math> as a constant and use the quadratic formula to get<br />
<cmath>x=\frac{d^2\pm \sqrt{d^4-4(3)(2d^2)}}{6}.</cmath><br />
We can factor pull <math> d^2 </math> out of the square root to get<br />
<cmath>x=\frac{d^2\pm d\sqrt{d^2-24}}{6}.</cmath><br />
Here, it is easy to test values of <math> d </math>. We find that <math> d=5 </math> and <math> d=7 </math> are the only positive integer values of <math> d </math> that make <math> \sqrt{d^2-24} </math> a positive integer. <math> d=5 </math> gives <math> x=5 </math> and <math> x=\frac{10}{3} </math>, but we can ignore the latter. <math> d=7 </math> gives <math> x=14 </math>, as well as a fraction which we can ignore. <br />
<br />
Since <math> d=5,~x=5 </math> and <math> d=7, x=14 </math> are the only two solutions and we want the sum of the third terms, our answer is <math> (5+5)+(7+14)=10+21=\boxed{031} </math>. -BorealBear<br />
<br />
===Solution 2===<br />
Proceed as in solution 1, until we reach <cmath>3a^2+2d^2=ad^2,</cmath> Write <br />
<br />
<math>d^2=\frac{3a^2}{a-2}</math>, it follows that <math>a-2=3k^2</math> for some (positive) integer k and <math>k \mid a</math>.<br />
<br />
Taking both sides modulo <math>k</math>, <math>-2 \equiv 0 \pmod{k}</math>, so <math>k \mid 2 \rightarrow k=1,2</math>. <br />
<br />
When <math>k=1</math>, we have <math>x=5</math> and <math>d=5</math>. When <math>k=2</math>, we have <math>x=14</math> and <math>d=7</math>.<br />
Summing the two cases, we have <math>10+21=\framebox{031}</math>.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=4|num-a=6}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_5&diff=1492232021 AIME I Problems/Problem 52021-03-12T14:56:29Z<p>Dearpasserby: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
Call a three-term strictly increasing arithmetic sequence of integers special if the sum of the squares of the three terms equals the product of the middle term and the square of the common difference. Find the sum of the third terms of all special sequences.<br />
<br />
==Solution==<br />
Let the terms be <math>a-b</math>, <math>a</math>, and <math>a+b</math>. Then we want <math>(a-b)^2+a^2+(a+b)^2=ab^2</math>, or <math>3a^2+2b^2=ab^2</math>. Rearranging, we get <math>b^2=\frac{3a^2}{a-2}</math>. Simplifying further, <math>b^2=3a+6+\frac{12}{a-2}</math>. Looking at this second equation, since the right side must be an integer, <math>a-2</math> must equal <math>\pm1, 2, 3, 4, 6, 12</math>. Looking at the first equation, we see <math>a>2</math> since <math>b^2</math> is positive. This means we must test <math>a=3, 4, 5, 6, 8, 14</math>. After testing these, we see that only <math>a=5</math> and <math>a=14</math> work which give <math>b=5</math> and <math>b=7</math> respectively. Thus the answer is <math>10+21=\boxed{031}</math>.<br />
~JHawk0224<br />
<br />
===Solution 1===<br />
Let the common difference be <math> d </math> and let the middle term be <math> x </math>. Then, we have that the sequence is<br />
<cmath>x-d,~x,~x+d.</cmath><br />
This means that the sum of the sequence is <br />
<cmath> (x-d)^2+x^2+(x+d)^2=x^2-2xd+d^2+x^2+x^2+2xd+d^2=3x^2+2d^2. </cmath><br />
We know that this must be equal to <math>xd^2,</math> so we can write that<br />
<cmath>3x^2+2d^2=xd^2,</cmath><br />
and it follows that<br />
<cmath>3x^2-xd^2+2d^2=3x^2-\left(d^2\right)x+2d^2=0.</cmath><br />
<br />
Now, we can treat <math> d </math> as a constant and use the quadratic formula to get<br />
<cmath>x=\frac{d^2\pm \sqrt{d^4-4(3)(2d^2)}}{6}.</cmath><br />
We can factor pull <math> d^2 </math> out of the square root to get<br />
<cmath>x=\frac{d^2\pm d\sqrt{d^2-24}}{6}.</cmath><br />
Here, it is easy to test values of <math> d </math>. We find that <math> d=5 </math> and <math> d=7 </math> are the only positive integer values of <math> d </math> that make <math> \sqrt{d^2-24} </math> a positive integer. <math> d=5 </math> gives <math> x=5 </math> and <math> x=\frac{10}{3} </math>, but we can ignore the latter. <math> d=7 </math> gives <math> x=14 </math>, as well as a fraction which we can ignore. <br />
<br />
Since <math> d=5,~x=5 </math> and <math> d=7, x=14 </math> are the only two solutions and we want the sum of the third terms, our answer is <math> (5+5)+(7+14)=10+21=\boxed{031} </math>. -BorealBear<br />
<br />
===Solution 2===<br />
Proceed as in solution 1, until we reach <cmath>3a^2+2d^2=ad^2,</cmath> Write <br />
<br />
<math>d^2=\frac{3a^2}{a-2}</math>, it follows that <math>a-2=3k^2</math> for some (positive) integer k and <math>k \mid a</math>.<br />
<br />
Taking both sides modulo <math>k</math>, <math>-2 \equiv 0 \pmod{k}</math>, so <math>k \mid 2 \rightarrow k=1,2</math>. <br />
<br />
When <math>k=1</math>, we have <math>x=5</math> and <math>d=5</math>. When <math>k=2</math>, we have <math>x=14</math> and <math>d=7</math>.<br />
Summing the two cases, we have <math>10+21=\framebox{031}</math>.<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=4|num-a=6}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_12&diff=1492222021 AIME I Problems/Problem 122021-03-12T14:55:34Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Let <math>A_1A_2A_3...A_{12}</math> be a dodecagon (12-gon). Three frogs initially sit at <math>A_4,A_8,</math> and <math>A_{12}</math>. At the end of each minute, simultaneously, each of the three frogs jumps to one of the two vertices adjacent to its current position, chosen randomly and independently with both choices being equally likely. All three frogs stop jumping as soon as two frogs arrive at the same vertex at the same time. The expected number of minutes until the frogs stop jumping is <math>\frac mn</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
==Solution==<br />
<br />
The expected number of steps depends on the distance between the frogs, not on the order in which these distances appear. Let E(a,b,c) where a+b+c=9 denote the expected number of steps that it takes for two frogs to meet if traversing in clockwise or counterclockwise order, the frogs are a, b and c vertices apart. Then<br />
<br />
<math>E(3,3,3)=1+\frac{1}{4} E(3,3,3)+\frac{3}{4} E(1,3,5)</math>, giving <math>E(3,3,3)=\frac{4}{3}+E(1,3,5)</math>; (1)<br />
<br />
<math>E(1,3,5)=1+\frac{1}{8}E(1,1,7)+\frac{1}{2}E(1,3,5)+\frac{1}{8}E(3,3,3)</math>, giving <math>E(1,3,5)=2+\frac{1}{4}E(1,1,7)+\frac{1}{4}E(3,3,3)</math>; (2)<br />
<br />
<math>E(1,1,7)=1+\frac{1}{4}E(1,1,7)+\frac{1}{4}E(1,3,5)</math>, giving <math>E(1,1,7)=\frac{4}{3}+\frac{1}{3}E(1,3,5)</math>; (3)<br />
<br />
Plug in (1) and (3) into (2), we see that <math>E(1,3,5)=4</math>. <math>E(3,3,3)=\frac{4}{3}+4=\frac{16}{3}</math>. Each step is one minute. The answer is <math>16+3=\boxed{19}</math>.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=11|num-a=13}}<br />
<br />
[[Category:Intermediate Combinatorics Problems]]<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_15&diff=1492212021 AIME I Problems/Problem 152021-03-12T14:54:46Z<p>Dearpasserby: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
Let <math>S</math> be the set of positive integers <math>k</math> such that the two parabolas<cmath>y=x^2-k~~\text{and}~~x=2(y-20)^2-k</cmath>intersect in four distinct points, and these four points lie on a circle with radius at most <math>21</math>. Find the sum of the least element of <math>S</math> and the greatest element of <math>S</math>.<br />
<br />
==Solution==<br />
===Solution 1===<br />
With binary search you can narrow down the k value. Newton raphson method let you narrow down the x and y solution for that specific k value. With 3 (x,y) pairs you can find radius of the circle. <br />
<br />
You end up finding the bounds of 5 and 280. The sum is 285.<br />
<br />
~Lopkiloinm<br />
<br />
===Solution 2===<br />
<br />
Make the translation <math>x \rightarrow x+20</math> to obtain <math>20+x=y^2-k , y=2x^2-k</math>. Multiply the second equation by 2 and sum, we see that <math>2(x^2+y^2)=3k+40+2x+y</math>. Completing the square gives us <math>(x- \frac{1}{2})^2+(y - \frac{1}{4})^2 = \frac{325+24k}{16}</math>; this explains why the two parabolas intersect at four points that lie on a circle*. For the upper bound, observe that <math>LHS \leq 21^2=441 \rightarrow 24k \leq 6731</math>, so <math>k \leq 280</math>. <br />
<br />
For the lower bound, we need to ensure there are 4 intersections to begin with. A quick check shows k=5 works while k=4 does not. Therefore, the answer is 5+280=285.<br />
<br />
*In general, this problem tells us that the intersection points of two conics without xy terms lie on a circle.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=14|after=Last problem}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_15&diff=1492202021 AIME I Problems/Problem 152021-03-12T14:54:21Z<p>Dearpasserby: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
Let <math>S</math> be the set of positive integers <math>k</math> such that the two parabolas<cmath>y=x^2-k~~\text{and}~~x=2(y-20)^2-k</cmath>intersect in four distinct points, and these four points lie on a circle with radius at most <math>21</math>. Find the sum of the least element of <math>S</math> and the greatest element of <math>S</math>.<br />
<br />
==Solution==<br />
===Solution 1===<br />
With binary search you can narrow down the k value. Newton raphson method let you narrow down the x and y solution for that specific k value. With 3 (x,y) pairs you can find radius of the circle. <br />
<br />
You end up finding the bounds of 5 and 280. The sum is 285.<br />
<br />
~Lopkiloinm<br />
<br />
===Solution 2===<br />
<br />
Make the translation <math>x \rightarrow x+20</math> to obtain <math>20+x=y^2-k , y=2x^2-k</math>. Multiply the second equation by 2 and sum, we see that <math>2(x^2+y^2)=3k+40+2x+y</math>. Completing the square gives us <math>(x- \frac{1}{2})^2+(y - \frac{1}{4})^2 = \frac{325+24k}{16}</math>; this explains why the two parabolas intersect at four points that lie on a circle*. For the upper bound, observe that <math>LHS \leq 21 \rightarrow 24k \leq 6731</math>, so <math>k \leq 280</math>. <br />
<br />
For the lower bound, we need to ensure there are 4 intersections to begin with. A quick check shows k=5 works while k=4 does not. Therefore, the answer is 5+280=285.<br />
<br />
*In general, this problem tells us that the intersection points of two conics without xy terms lie on a circle.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=14|after=Last problem}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_15&diff=1492192021 AIME I Problems/Problem 152021-03-12T14:52:59Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Let <math>S</math> be the set of positive integers <math>k</math> such that the two parabolas<cmath>y=x^2-k~~\text{and}~~x=2(y-20)^2-k</cmath>intersect in four distinct points, and these four points lie on a circle with radius at most <math>21</math>. Find the sum of the least element of <math>S</math> and the greatest element of <math>S</math>.<br />
<br />
==Solution==<br />
===Solution 1===<br />
With binary search you can narrow down the k value. Newton raphson method let you narrow down the x and y solution for that specific k value. With 3 (x,y) pairs you can find radius of the circle. <br />
<br />
You end up finding the bounds of 5 and 280. The sum is 285.<br />
<br />
~Lopkiloinm<br />
<br />
===Solution 2===<br />
<br />
Make the translation <math>x \rightarrow x+20</math> to obtain <math>20+x=y^2-k , y=2x^2-k</math>. Multiply the second equation by 2 and sum, we see that <math>2(x^2+y^2)=3k+40+2x+y</math>. Completing the square gives us <math>(x- \frac{1}{2})^2+(y - \frac{1}{4})^2 = \frac{325+24k}{16}</math>; this explains why the two parabolas intersect at four points that lie on a circle. For the upper bound, observe that <math>LHS \leq 21 \rightarrow 24k \leq 6731</math>, so <math>k \leq 280</math>. <br />
<br />
For the lower bound, we need to ensure there are 4 intersections to begin with. A quick check shows k=5 works while k=4 does not. Therefore, the answer is 5+280=285.<br />
<br />
-Ross Gao<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=14|after=Last problem}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_12&diff=1491672021 AIME I Problems/Problem 122021-03-12T03:45:16Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Let <math>A_1A_2A_3...A_{12}</math> be a dodecagon (12-gon). Three frogs initially sit at <math>A_4,A_8,</math> and <math>A_{12}</math>. At the end of each minute, simultaneously, each of the three frogs jumps to one of the two vertices adjacent to its current position, chosen randomly and independently with both choices being equally likely. All three frogs stop jumping as soon as two frogs arrive at the same vertex at the same time. The expected number of minutes until the frogs stop jumping is <math>\frac mn</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
==Solution==<br />
<br />
The expected number of steps depends on the distance between the frogs, not on the order in which these distances appear. Let E(a,b,c) where a+b+c=9 denote the expected number of steps that it takes for two frogs to meet if traversing in clockwise or counterclockwise order, the frogs are a, b and c vertices apart. Then<br />
<br />
<math>E(3,3,3)=1+\frac{1}{4} E(3,3,3)+\frac{3}{4} E(1,3,5)</math>, giving <math>E(3,3,3)=\frac{4}{3}+E(1,3,5)</math>; (1)<br />
<br />
<math>E(1,3,5)=1+\frac{1}{8}E(1,1,7)+\frac{1}{2}E(1,3,5)+\frac{1}{8}E(3,3,3)</math>, giving <math>E(1,3,5)=2+\frac{1}{4}E(1,1,7)+\frac{1}{4}E(3,3,3)</math>; (2)<br />
<br />
<math>E(1,1,7)=1+\frac{1}{4}E(1,1,7)+\frac{1}{4}E(1,3,5)</math>, giving <math>E(1,1,7)=\frac{4}{3}+\frac{1}{3}E(1,3,5)</math>; (3)<br />
<br />
Plug in (1) and (3) into (2), we see that <math>E(1,3,5)=4</math>. <math>E(3,3,3)=\frac{4}{3}+4=\frac{16}{3}</math>. Each step is one minute. The answer is 16+3=19.<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=11|num-a=13}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_12&diff=1491662021 AIME I Problems/Problem 122021-03-12T03:44:14Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Let <math>A_1A_2A_3...A_{12}</math> be a dodecagon (12-gon). Three frogs initially sit at <math>A_4,A_8,</math> and <math>A_{12}</math>. At the end of each minute, simultaneously, each of the three frogs jumps to one of the two vertices adjacent to its current position, chosen randomly and independently with both choices being equally likely. All three frogs stop jumping as soon as two frogs arrive at the same vertex at the same time. The expected number of minutes until the frogs stop jumping is <math>\frac mn</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
==Solution==<br />
<br />
The expected number of steps depends on the distance between the frogs, not on the order in which these distances appear. Let E(a,b,c) where a+b+c=9 denote the expected number of steps that it takes for two frogs to meet if traversing in clockwise or counterclockwise order, the frogs are a, b and c vertices apart. Then<br />
<br />
<math>E(3,3,3)=1+\frac{1}{4} E(3,3,3)+\frac{3}{4} E(1,3,5)</math>, giving <math>E(3,3,3)=\frac{4}{3}+E(1,3,5)</math>; (1)<br />
<br />
<math>E(1,3,5)=1+\frac{1}{8}E(1,1,1)+\frac{1}{2}E(1,3,5)+\frac{1}{8}E(3,3,3)</math>, giving <math>E(1,3,5)=2+\frac{1}{4}E(1,1,1)+\frac{1}{4}E(3,3,3)</math>; (2)<br />
<br />
<math>E(1,1,1)=1+\frac{1}{4}E(1,1,1)+\frac{1}{4}E(1,3,5)</math>, giving <math>E(1,1,1)=\frac{4}{3}+\frac{1}{3}E(1,3,5)</math>; (3)<br />
<br />
Plug in (1) and (3) into (2), we see that <math>E(1,3,5)=4</math>. <math>E(3,3,3)=\frac{4}{3}+4=\frac{16}{3}</math>. Each step is one minute. The answer is 16+3=19.<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=11|num-a=13}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_12&diff=1491642021 AIME I Problems/Problem 122021-03-12T03:43:12Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Let <math>A_1A_2A_3...A_{12}</math> be a dodecagon (12-gon). Three frogs initially sit at <math>A_4,A_8,</math> and <math>A_{12}</math>. At the end of each minute, simultaneously, each of the three frogs jumps to one of the two vertices adjacent to its current position, chosen randomly and independently with both choices being equally likely. All three frogs stop jumping as soon as two frogs arrive at the same vertex at the same time. The expected number of minutes until the frogs stop jumping is <math>\frac mn</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
==Solution==<br />
<br />
The expected number of steps depends on the distance between the frogs, not on the order in which these distances appear. Let E(a,b,c) where a+b+c=9 denote the expected number of steps that it takes for two frogs to meet if traversing in clockwise or counterclockwise order, the frogs are a, b and c vertices apart. Then<br />
<br />
<math>E(3,3,3)=1+\frac{1}{4} E(3,3,3)+\frac{3}{4} E(1,3,5)</math>, giving <math>E(3,3,3)=\frac{4}{3}+E(1,3,5)</math>; (1)<br />
<br />
<math>E(1,3,5)=1+\frac{1}{8}E(1,1,1)+\frac{1}{2}E(1,3,5)+\frac{1}{8}E(3,3,3)</math>, giving <math>E(1,3,5)=2+\frac{1}{4}E(1,1,1)+\frac{1}{4}E(3,3,3)</math>; (2)<br />
<br />
<math>E(1,1,1)=1+\frac{1}{4}E(1,1,1)+\frac{1}{4}E(1,3,5)</math>, giving <math>E(1,1,1)=\frac{4}{3}+\frac{1}{3}E(1,3,5)</math>; (3)<br />
<br />
Plug in (1) and (3) into (2), we see that <math>E(1,3,5)=4</math>. <math>E(3,3,3)=\frac{4}{3}+4=\frac{16}{3}</math>. The answer is 16+3=19.<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=11|num-a=13}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_5&diff=1491632021 AIME I Problems/Problem 52021-03-12T03:42:22Z<p>Dearpasserby: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
Call a three-term strictly increasing arithmetic sequence of integers special if the sum of the squares of the three terms equals the product of the middle term and the square of the common difference. Find the sum of the third terms of all special sequences.<br />
<br />
==Solution==<br />
Let the terms be <math>a-b</math>, <math>a</math>, and <math>a+b</math>. Then we want <math>(a-b)^2+a^2+(a+b)^2=ab^2</math>, or <math>3a^2+2b^2=ab^2</math>. Rearranging, we get <math>b^2=\frac{3a^2}{a-2}</math>. Simplifying further, <math>b^2=3a+6+\frac{12}{a-2}</math>. Looking at this second equation, since the right side must be an integer, <math>a-2</math> must equal <math>\pm1, 2, 3, 4, 6, 12</math>. Looking at the first equation, we see <math>a>2</math> since <math>b^2</math> is positive. This means we must test <math>a=3, 4, 5, 6, 8, 14</math>. After testing these, we see that only <math>a=5</math> and <math>a=14</math> work which give <math>b=5</math> and <math>b=7</math> respectively. Thus the answer is <math>10+21=\boxed{31}</math>.<br />
~JHawk0224<br />
<br />
===Solution 1===<br />
Let the common difference be <math> d </math> and let the middle term be <math> x </math>. Then, we have that the sequence is<br />
<cmath>x-d,~x,~x+d.</cmath><br />
This means that the sum of the sequence is <br />
<cmath> (x-d)^2+x^2+(x+d)^2=x^2-2xd+d^2+x^2+x^2+2xd+d^2=3x^2+2d^2. </cmath><br />
We know that this must be equal to <math>xd^2,</math> so we can write that<br />
<cmath>3x^2+2d^2=xd^2,</cmath><br />
and it follows that<br />
<cmath>3x^2-xd^2+2d^2=3x^2-\left(d^2\right)x+2d^2=0.</cmath><br />
<br />
Now, we can treat <math> d </math> as a constant and use the quadratic formula to get<br />
<cmath>x=\frac{d^2\pm \sqrt{d^4-4(3)(2d^2)}}{6}.</cmath><br />
We can factor pull <math> d^2 </math> out of the square root to get<br />
<cmath>x=\frac{d^2\pm d\sqrt{d^2-24}}{6}.</cmath><br />
Here, it is easy to test values of <math> d </math>. We find that <math> d=5 </math> and <math> d=7 </math> are the only positive integer values of <math> d </math> that make <math> \sqrt{d^2-24} </math> a positive integer. <math> d=5 </math> gives <math> x=5 </math> and <math> x=\frac{10}{3} </math>, but we can ignore the latter. <math> d=7 </math> gives <math> x=14 </math>, as well as a fraction which we can ignore. <br />
<br />
Since <math> d=5,~x=5 </math> and <math> d=7, x=14 </math> are the only two solutions and we want the sum of the third terms, our answer is <math> (5+5)+(7+14)=10+21=\boxed{031} </math>. -BorealBear<br />
<br />
===Solution 2===<br />
Proceed as in solution 1, until we reach <cmath>3a^2+2d^2=ad^2,</cmath>. Write <br />
<br />
<math>d^2=\frac{3a^2}{a-2}</math>, it follows that <math>a-2=3k^2</math> for some (positive) integer k and <math>k \mid a</math>.<br />
<br />
Taking both sides modulo <math>k</math>, <math>-2 \equiv 0 \pmod{k}</math>, so <math>k \mid 2 \rightarrow k=1,2</math>. <br />
<br />
When k=1, x=5 and d=5. When k=2, x=14 and d=7.<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=4|num-a=6}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_5&diff=1491622021 AIME I Problems/Problem 52021-03-12T03:41:56Z<p>Dearpasserby: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
Call a three-term strictly increasing arithmetic sequence of integers special if the sum of the squares of the three terms equals the product of the middle term and the square of the common difference. Find the sum of the third terms of all special sequences.<br />
<br />
==Solution==<br />
Let the terms be <math>a-b</math>, <math>a</math>, and <math>a+b</math>. Then we want <math>(a-b)^2+a^2+(a+b)^2=ab^2</math>, or <math>3a^2+2b^2=ab^2</math>. Rearranging, we get <math>b^2=\frac{3a^2}{a-2}</math>. Simplifying further, <math>b^2=3a+6+\frac{12}{a-2}</math>. Looking at this second equation, since the right side must be an integer, <math>a-2</math> must equal <math>\pm1, 2, 3, 4, 6, 12</math>. Looking at the first equation, we see <math>a>2</math> since <math>b^2</math> is positive. This means we must test <math>a=3, 4, 5, 6, 8, 14</math>. After testing these, we see that only <math>a=5</math> and <math>a=14</math> work which give <math>b=5</math> and <math>b=7</math> respectively. Thus the answer is <math>10+21=\boxed{31}</math>.<br />
~JHawk0224<br />
<br />
===Solution 1===<br />
Let the common difference be <math> d </math> and let the middle term be <math> x </math>. Then, we have that the sequence is<br />
<cmath>x-d,~x,~x+d.</cmath><br />
This means that the sum of the sequence is <br />
<cmath> (x-d)^2+x^2+(x+d)^2=x^2-2xd+d^2+x^2+x^2+2xd+d^2=3x^2+2d^2. </cmath><br />
We know that this must be equal to <math>xd^2,</math> so we can write that<br />
<cmath>3x^2+2d^2=xd^2,</cmath><br />
and it follows that<br />
<cmath>3x^2-xd^2+2d^2=3x^2-\left(d^2\right)x+2d^2=0.</cmath><br />
<br />
Now, we can treat <math> d </math> as a constant and use the quadratic formula to get<br />
<cmath>x=\frac{d^2\pm \sqrt{d^4-4(3)(2d^2)}}{6}.</cmath><br />
We can factor pull <math> d^2 </math> out of the square root to get<br />
<cmath>x=\frac{d^2\pm d\sqrt{d^2-24}}{6}.</cmath><br />
Here, it is easy to test values of <math> d </math>. We find that <math> d=5 </math> and <math> d=7 </math> are the only positive integer values of <math> d </math> that make <math> \sqrt{d^2-24} </math> a positive integer. <math> d=5 </math> gives <math> x=5 </math> and <math> x=\frac{10}{3} </math>, but we can ignore the latter. <math> d=7 </math> gives <math> x=14 </math>, as well as a fraction which we can ignore. <br />
<br />
Since <math> d=5,~x=5 </math> and <math> d=7, x=14 </math> are the only two solutions and we want the sum of the third terms, our answer is <math> (5+5)+(7+14)=10+21=\boxed{031} </math>. -BorealBear<br />
<br />
===Solution 2===<br />
Proceed as in solution 1, until we reach <cmath>3x^2+2d^2=xd^2,</cmath>. Write <br />
<br />
<math>d^2=\frac{3a^2}{a-2}</math>, it follows that <math>a-2=3k^2</math> for some (positive) integer k and <math>k \mid a</math>.<br />
<br />
Taking both sides modulo <math>k</math>, <math>-2 \equiv 0 \pmod{k}</math>, so <math>k \mid 2 \rightarrow k=1,2</math>. <br />
<br />
When k=1, x=5 and d=5. When k=2, x=14 and d=7.<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=4|num-a=6}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_5&diff=1491612021 AIME I Problems/Problem 52021-03-12T03:41:20Z<p>Dearpasserby: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
Call a three-term strictly increasing arithmetic sequence of integers special if the sum of the squares of the three terms equals the product of the middle term and the square of the common difference. Find the sum of the third terms of all special sequences.<br />
<br />
==Solution==<br />
Let the terms be <math>a-b</math>, <math>a</math>, and <math>a+b</math>. Then we want <math>(a-b)^2+a^2+(a+b)^2=ab^2</math>, or <math>3a^2+2b^2=ab^2</math>. Rearranging, we get <math>b^2=\frac{3a^2}{a-2}</math>. Simplifying further, <math>b^2=3a+6+\frac{12}{a-2}</math>. Looking at this second equation, since the right side must be an integer, <math>a-2</math> must equal <math>\pm1, 2, 3, 4, 6, 12</math>. Looking at the first equation, we see <math>a>2</math> since <math>b^2</math> is positive. This means we must test <math>a=3, 4, 5, 6, 8, 14</math>. After testing these, we see that only <math>a=5</math> and <math>a=14</math> work which give <math>b=5</math> and <math>b=7</math> respectively. Thus the answer is <math>10+21=\boxed{31}</math>.<br />
~JHawk0224<br />
<br />
===Solution 1===<br />
Let the common difference be <math> d </math> and let the middle term be <math> x </math>. Then, we have that the sequence is<br />
<cmath>x-d,~x,~x+d.</cmath><br />
This means that the sum of the sequence is <br />
<cmath> (x-d)^2+x^2+(x+d)^2=x^2-2xd+d^2+x^2+x^2+2xd+d^2=3x^2+2d^2. </cmath><br />
We know that this must be equal to <math>xd^2,</math> so we can write that<br />
<cmath>3x^2+2d^2=xd^2,</cmath><br />
and it follows that<br />
<cmath>3x^2-xd^2+2d^2=3x^2-\left(d^2\right)x+2d^2=0.</cmath><br />
<br />
Now, we can treat <math> d </math> as a constant and use the quadratic formula to get<br />
<cmath>x=\frac{d^2\pm \sqrt{d^4-4(3)(2d^2)}}{6}.</cmath><br />
We can factor pull <math> d^2 </math> out of the square root to get<br />
<cmath>x=\frac{d^2\pm d\sqrt{d^2-24}}{6}.</cmath><br />
Here, it is easy to test values of <math> d </math>. We find that <math> d=5 </math> and <math> d=7 </math> are the only positive integer values of <math> d </math> that make <math> \sqrt{d^2-24} </math> a positive integer. <math> d=5 </math> gives <math> x=5 </math> and <math> x=\frac{10}{3} </math>, but we can ignore the latter. <math> d=7 </math> gives <math> x=14 </math>, as well as a fraction which we can ignore. <br />
<br />
Since <math> d=5,~x=5 </math> and <math> d=7, x=14 </math> are the only two solutions and we want the sum of the third terms, our answer is <math> (5+5)+(7+14)=10+21=\boxed{031} </math>. -BorealBear<br />
<br />
===Solution 2===<br />
Proceed as in solution 1, until we reach <cmath>3x^2+2d^2=xd^2,</cmath>. Write <br />
<math>d^2=\frac{3a^2}{a-2}</math>, it follows that <math>a-2=3k^2</math> for some (positive) integer k and <math>k \mid a</math>. \par<br />
Taking both sides modulo <math>k</math>, <math>-2 \equiv 0 \pmod{k}</math>, so <math>k \mid 2 \rightarrow k=1,2</math>. \par<br />
When k=1, x=5 and d=5. When k=2, x=14 and d=7.<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=4|num-a=6}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_5&diff=1491602021 AIME I Problems/Problem 52021-03-12T03:41:02Z<p>Dearpasserby: /* Solution 1 */</p>
<hr />
<div>==Problem==<br />
Call a three-term strictly increasing arithmetic sequence of integers special if the sum of the squares of the three terms equals the product of the middle term and the square of the common difference. Find the sum of the third terms of all special sequences.<br />
<br />
==Solution==<br />
Let the terms be <math>a-b</math>, <math>a</math>, and <math>a+b</math>. Then we want <math>(a-b)^2+a^2+(a+b)^2=ab^2</math>, or <math>3a^2+2b^2=ab^2</math>. Rearranging, we get <math>b^2=\frac{3a^2}{a-2}</math>. Simplifying further, <math>b^2=3a+6+\frac{12}{a-2}</math>. Looking at this second equation, since the right side must be an integer, <math>a-2</math> must equal <math>\pm1, 2, 3, 4, 6, 12</math>. Looking at the first equation, we see <math>a>2</math> since <math>b^2</math> is positive. This means we must test <math>a=3, 4, 5, 6, 8, 14</math>. After testing these, we see that only <math>a=5</math> and <math>a=14</math> work which give <math>b=5</math> and <math>b=7</math> respectively. Thus the answer is <math>10+21=\boxed{31}</math>.<br />
~JHawk0224<br />
<br />
===Solution 1===<br />
Let the common difference be <math> d </math> and let the middle term be <math> x </math>. Then, we have that the sequence is<br />
<cmath>x-d,~x,~x+d.</cmath><br />
This means that the sum of the sequence is <br />
<cmath> (x-d)^2+x^2+(x+d)^2=x^2-2xd+d^2+x^2+x^2+2xd+d^2=3x^2+2d^2. </cmath><br />
We know that this must be equal to <math>xd^2,</math> so we can write that<br />
<cmath>3x^2+2d^2=xd^2,</cmath><br />
and it follows that<br />
<cmath>3x^2-xd^2+2d^2=3x^2-\left(d^2\right)x+2d^2=0.</cmath><br />
<br />
Now, we can treat <math> d </math> as a constant and use the quadratic formula to get<br />
<cmath>x=\frac{d^2\pm \sqrt{d^4-4(3)(2d^2)}}{6}.</cmath><br />
We can factor pull <math> d^2 </math> out of the square root to get<br />
<cmath>x=\frac{d^2\pm d\sqrt{d^2-24}}{6}.</cmath><br />
Here, it is easy to test values of <math> d </math>. We find that <math> d=5 </math> and <math> d=7 </math> are the only positive integer values of <math> d </math> that make <math> \sqrt{d^2-24} </math> a positive integer. <math> d=5 </math> gives <math> x=5 </math> and <math> x=\frac{10}{3} </math>, but we can ignore the latter. <math> d=7 </math> gives <math> x=14 </math>, as well as a fraction which we can ignore. <br />
<br />
Since <math> d=5,~x=5 </math> and <math> d=7, x=14 </math> are the only two solutions and we want the sum of the third terms, our answer is <math> (5+5)+(7+14)=10+21=\boxed{031} </math>. -BorealBear<br />
<br />
===Solution 2===<br />
Proceed as in solution 1, until we reach <cmath>3x^2+2d^2=xd^2,</cmath>. Write <br />
<math>d^2=\frac{3a^2}{a-2}</math>, it follows that <math>a-2=3k^2</math> for some (positive) integer k and <math>k \mid a</math>. \\<br />
Taking both sides modulo <math>k</math>, <math>-2 \equiv 0 \pmod{k}</math>, so <math>k \mid 2 \rightarrow k=1,2</math>. <br />
When k=1, x=5 and d=5. When k=2, x=14 and d=7.<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=4|num-a=6}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_5&diff=1491592021 AIME I Problems/Problem 52021-03-12T03:40:01Z<p>Dearpasserby: /* Solution 1 */</p>
<hr />
<div>==Problem==<br />
Call a three-term strictly increasing arithmetic sequence of integers special if the sum of the squares of the three terms equals the product of the middle term and the square of the common difference. Find the sum of the third terms of all special sequences.<br />
<br />
==Solution==<br />
Let the terms be <math>a-b</math>, <math>a</math>, and <math>a+b</math>. Then we want <math>(a-b)^2+a^2+(a+b)^2=ab^2</math>, or <math>3a^2+2b^2=ab^2</math>. Rearranging, we get <math>b^2=\frac{3a^2}{a-2}</math>. Simplifying further, <math>b^2=3a+6+\frac{12}{a-2}</math>. Looking at this second equation, since the right side must be an integer, <math>a-2</math> must equal <math>\pm1, 2, 3, 4, 6, 12</math>. Looking at the first equation, we see <math>a>2</math> since <math>b^2</math> is positive. This means we must test <math>a=3, 4, 5, 6, 8, 14</math>. After testing these, we see that only <math>a=5</math> and <math>a=14</math> work which give <math>b=5</math> and <math>b=7</math> respectively. Thus the answer is <math>10+21=\boxed{31}</math>.<br />
~JHawk0224<br />
<br />
===Solution 1===<br />
Let the common difference be <math> d </math> and let the middle term be <math> x </math>. Then, we have that the sequence is<br />
<cmath>x-d,~x,~x+d.</cmath><br />
This means that the sum of the sequence is <br />
<cmath> (x-d)^2+x^2+(x+d)^2=x^2-2xd+d^2+x^2+x^2+2xd+d^2=3x^2+2d^2. </cmath><br />
We know that this must be equal to <math>xd^2,</math> so we can write that<br />
<cmath>3x^2+2d^2=xd^2,</cmath><br />
and it follows that<br />
<cmath>3x^2-xd^2+2d^2=3x^2-\left(d^2\right)x+2d^2=0.</cmath><br />
<br />
Now, we can treat <math> d </math> as a constant and use the quadratic formula to get<br />
<cmath>x=\frac{d^2\pm \sqrt{d^4-4(3)(2d^2)}}{6}.</cmath><br />
We can factor pull <math> d^2 </math> out of the square root to get<br />
<cmath>x=\frac{d^2\pm d\sqrt{d^2-24}}{6}.</cmath><br />
Here, it is easy to test values of <math> d </math>. We find that <math> d=5 </math> and <math> d=7 </math> are the only positive integer values of <math> d </math> that make <math> \sqrt{d^2-24} </math> a positive integer. <math> d=5 </math> gives <math> x=5 </math> and <math> x=\frac{10}{3} </math>, but we can ignore the latter. <math> d=7 </math> gives <math> x=14 </math>, as well as a fraction which we can ignore. <br />
<br />
Since <math> d=5,~x=5 </math> and <math> d=7, x=14 </math> are the only two solutions and we want the sum of the third terms, our answer is <math> (5+5)+(7+14)=10+21=\boxed{031} </math>. -BorealBear<br />
<br />
===Solution 1===<br />
Proceed as in solution 1, until we reach <cmath>3x^2+2d^2=xd^2,</cmath>. Write <br />
<math>d^2=\frac{3a^2}{a-2}</math>, it follows that <math>a-2=3k^2</math> for some (positive) integer k and <math>k \div a</math>. <br />
Taking both sides modulo k, <math>-2 \equiv 0 \pmod{k}</math>, so <math>k \div 2 \rightarrow k=1,2</math>. When k=1, x=5 and d=5. When k=2, x=14 and d=7.<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=4|num-a=6}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_12&diff=1491582021 AIME I Problems/Problem 122021-03-12T03:36:52Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Let <math>A_1A_2A_3...A_{12}</math> be a dodecagon (12-gon). Three frogs initially sit at <math>A_4,A_8,</math> and <math>A_{12}</math>. At the end of each minute, simultaneously, each of the three frogs jumps to one of the two vertices adjacent to its current position, chosen randomly and independently with both choices being equally likely. All three frogs stop jumping as soon as two frogs arrive at the same vertex at the same time. The expected number of minutes until the frogs stop jumping is <math>\frac mn</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
==Solution==<br />
<br />
The expected number of steps depends on the distance between the frogs, not on the order in which these distances appear. Let E(a,b,c) where a+b+c=9 denote the expected number of steps that it takes for two frogs to meet if traversing in clockwise or counterclockwise order, the frogs are a, b and c vertices apart. Then<br />
<br />
E(3,3,3)=1+\frac{1}{4} E(3,3,3)+\frac{3}{4} E(1,3,5), giving E(3,3,3)=\frac{4}{3}+E(1,3,5); (1)<br />
<br />
E(1,3,5)=1+\frac{1}{8}E(1,1,1)+\frac{1}{2}E(1,3,5)+\frac{1}{8}E(3,3,3), giving E(1,3,5)=2+\frac{1}{4}E(1,1,1)+\frac{1}{4}E(3,3,3); (2)<br />
<br />
E(1,1,1)=1+\frac{1}{4}E(1,1,1)+\frac{1}{4}E(1,3,5), giving E(1,1,1)=\frac{4}{3}+\frac{1}{3}E(1,3,5); (3)<br />
<br />
Plug in (1) and (3) into (2), we see that E(1,3,5)=4. E(3,3,3)=\frac{4}{3}+4=\frac{16}{3}. The answer is 16+3=19.<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=11|num-a=13}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_12&diff=1491572021 AIME I Problems/Problem 122021-03-12T03:36:02Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Let <math>A_1A_2A_3...A_{12}</math> be a dodecagon (12-gon). Three frogs initially sit at <math>A_4,A_8,</math> and <math>A_{12}</math>. At the end of each minute, simultaneously, each of the three frogs jumps to one of the two vertices adjacent to its current position, chosen randomly and independently with both choices being equally likely. All three frogs stop jumping as soon as two frogs arrive at the same vertex at the same time. The expected number of minutes until the frogs stop jumping is <math>\frac mn</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
==Solution==<br />
<br />
The expected number of steps depends on the distance between the frogs, not on the order in which these distances appear. Let E(a,b,c) where a+b+c=9 denote the expected number of steps that it takes for two frogs to meet if traversing in clockwise or counterclockwise order, the frogs are a, b and c vertices apart. Then<br />
<br />
E(3,3,3)=1+\frac{1}{4} E(3,3,3)+\frac{3}{4} E(1,3,5), giving E(3,3,3)=\frac{4}{3}+E(1,3,5); (1)<br />
<br />
E(1,3,5)=1+\frac{1}{8}E(1,1,1)+\frac{1}{2}E(1,3,5)+\frac{1}{8}E(3,3,3), giving E(1,3,5)=2+\frac{1}{4}E(1,1,1)+\frac{1}{4}E(3,3,3); (2)<br />
<br />
E(1,1,1)=1+\frac{1}{4}E(1,1,1)+\frac{1}{4}E(1,3,5), giving E(1,1,1)=\frac{4}{3}+\frac{1}{3}E(1,3,5); (3)<br />
<br />
Plug in (1) and (3) into (2), we see that E(1,3,5)=4. E(3,3,3)=\frac{4}{3}+4=\frac{16}{3}.<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=11|num-a=13}}<br />
{{MAA Notice}}</div>Dearpasserbyhttps://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_12&diff=1491562021 AIME I Problems/Problem 122021-03-12T03:34:29Z<p>Dearpasserby: /* Solution */</p>
<hr />
<div>==Problem==<br />
Let <math>A_1A_2A_3...A_{12}</math> be a dodecagon (12-gon). Three frogs initially sit at <math>A_4,A_8,</math> and <math>A_{12}</math>. At the end of each minute, simultaneously, each of the three frogs jumps to one of the two vertices adjacent to its current position, chosen randomly and independently with both choices being equally likely. All three frogs stop jumping as soon as two frogs arrive at the same vertex at the same time. The expected number of minutes until the frogs stop jumping is <math>\frac mn</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
==Solution==<br />
<br />
The expected number of steps depends on the distance between the frogs, not on the order in which these distances appear. Let E(a,b,c) where a+b+c=9 denote the expected number of steps that it takes for two frogs to meet if traversing in clockwise or counterclockwise order, the frogs are a, b and c vertices apart. Then<br />
<br />
E(3,3,3)=1+1/4E(3,3,3)+3/4E(1,3,5), giving E(3,3,3)=4/3+E(1,3,5); (1)<br />
<br />
E(1,3,5)=1+1/8E(1,1,1)+1/2E(1,3,5)+1/8E(3,3,3), giving E(1,3,5)=2+1/4E(1,1,1)+1/4E(3,3,3); (2)<br />
<br />
E(1,1,1)=1+1/4E(1,1,1)+1/4E(1,3,5), giving E(1,1,1)=4/3+1/3E(1,3,5); (3)<br />
<br />
Plug in (1) and (3) into (2), we see that E(1,3,5)=4. E(3,3,3)=4/3+4=16/3.<br />
<br />
==See also==<br />
{{AIME box|year=2021|n=I|num-b=11|num-a=13}}<br />
{{MAA Notice}}</div>Dearpasserby