https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Bradleyguo&feedformat=atomAoPS Wiki - User contributions [en]2024-03-29T00:14:37ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_11&diff=1092292018 AIME I Problems/Problem 112019-08-22T21:27:21Z<p>Bradleyguo: /* Solution 6(LTE) */</p>
<hr />
<div><br />
==Problem==<br />
Find the least positive integer <math>n</math> such that when <math>3^n</math> is written in base <math>143</math>, its two right-most digits in base <math>143</math> are <math>01</math>.<br />
<br />
==Solutions==<br />
<br />
==Modular Arithmetic Solution- Strange (MASS)==<br />
Note that the given condition is equivalent to <math>3^n \equiv 1 \pmod{143^2}</math> and <math>143=11\cdot 13</math>. Because <math>gcd(11^2, 13^2) = 1</math>, the desired condition is equivalent to <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>.<br />
<br />
If <math>3^n \equiv 1 \pmod{121}</math>, one can see the sequence <math>1, 3, 9, 27, 81, 1, 3, 9...</math> so <math>5|n</math>.<br />
<br />
Now if <math>3^n \equiv 1 \pmod{169}</math>, it is harder. But we do observe that <math>3^3 \equiv 1 \pmod{13}</math>, therefore <math>3^3 = 13a + 1</math> for some integer <math>a</math>. So our goal is to find the first number <math>p_1</math> such that <math>(13a+1)^ {p_1} \equiv 1 \pmod{169}</math>. In other words, the <math>p_1 \equiv 0 \pmod{13}</math>. It is not difficult to see that the smallest <math>p_1=13</math>, so ultimately <math>3^{39} \equiv 1 \pmod{169}</math>. Therefore, <math>39|n</math>.<br />
<br />
The first <math>n</math> satisfying both criteria is thus <math>5\cdot 39=\boxed{195}</math>.<br />
<br />
-expiLnCalc<br />
<br />
==Solution 2==<br />
Note that Euler's Totient Theorem would not necessarily lead to the smallest <math>n</math> and that in this case that <math>n</math> is greater than <math>1000</math>. <br />
<br />
We wish to find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{143^2}</math>. This factors as <math>143^2=11^{2}*13^{2}</math>. Because <math>gcd(121, 169) = 1</math>, we can simply find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>.<br />
<br />
Quick inspection yields <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^3 \equiv 1 \pmod{13}</math>. Now we must find the smallest <math>k</math> such that <math>3^{3k} \equiv 1 \pmod{13}</math>. Euler's gives <math>3^{156} \equiv 1 \pmod{169}</math>. So <math>3k</math> is a factor of <math>156</math>. This gives <math>k=1,2, 4, 13, 26, 52</math>. Some more inspection yields <math>k=13</math> is the smallest valid <math>k</math>. So <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^{39} \equiv 1 \pmod{169}</math>. The least <math>n</math> satisfying both is <math>lcm(5, 39)=\boxed{195}</math>. (RegularHexagon)<br />
<br />
==Solution 3 (Big Bash)==<br />
Listing out the powers of <math>3</math>, modulo <math>169</math> and modulo <math>121</math>, we have:<br />
<cmath>\begin{array}{c|c|c}<br />
n & 3^n\mod{169} & 3^n\mod{121}\\ \hline<br />
0 & 1 & 1\\<br />
1 & 3 & 3\\<br />
2 & 9 & 9\\<br />
3 & 27 & 27\\<br />
4 & 81 & 81\\<br />
5 & 74 & 1\\<br />
6 & 53\\<br />
7 & 159\\<br />
8 & 139\\<br />
9 & 79\\<br />
10 & 68\\<br />
11 & 35\\<br />
12 & 105\\<br />
13 & 146\\<br />
14 & 100\\<br />
15 & 131\\<br />
16 & 55\\<br />
17 & 165\\<br />
18 & 157\\<br />
19 & 133\\<br />
20 & 61\\<br />
21 & 14\\<br />
22 & 42\\<br />
23 & 126\\<br />
24 & 40\\<br />
25 & 120\\<br />
26 & 22\\<br />
27 & 66\\<br />
28 & 29\\<br />
29 & 87\\<br />
30 & 92\\<br />
31 & 107\\<br />
32 & 152\\<br />
33 & 118\\<br />
34 & 16\\<br />
35 & 48\\<br />
36 & 144\\<br />
37 & 94\\<br />
38 & 113\\<br />
39 & 1\\<br />
\end{array}</cmath><br />
<br />
The powers of <math>3</math> repeat in cycles of <math>5</math> an <math>39</math> in modulo <math>121</math> and modulo <math>169</math>, respectively. The answer is <math>\text{lcm}(5, 39) = \boxed{195}</math>.<br />
<br />
==Solution 4(Order+Bash)==<br />
We have that <cmath>3^n \equiv 1 \pmod{143^2}.</cmath>Now, <math>3^{110} \equiv 1 \pmod{11^2}</math> so by the Fundamental Theorem of Orders, <math>\text{ord}_{11^2}(3)|110</math> and with some bashing, we get that it is <math>5</math>. Similarly, we get that <math>\text{ord}_{13^2}(3)=39</math>. Now, <math>\text{lcm}(39,5)=\boxed{195}</math> which is our desired solution.<br />
<br />
==Solution 5 (Easy Binomial Theorem)==<br />
We wish to find the smallest <math>n</math> such that <math>3^n\equiv 1\pmod{143^2}</math>, so we want <math>n\equiv 1\pmod{121}</math> and <math>n\equiv 1\pmod{169}</math>. Note that <math>3^5\equiv 1\pmod{121}</math>, so <math>3^n</math> repeats <math>121</math> with a period of <math>5</math>, so <math>5|n</math>. Now, in order for <math>n\equiv 1\pmod{169}</math>, then <math>n\equiv 1\pmod{13}</math>. Because <math>3^3\equiv 1\pmod{13}</math>, <math>3^n</math> repeats with a period of <math>3</math>, so <math>3|n</math>. <br />
Hence, we have that for some positive integer <math>p</math>, <math>3^n\equiv (3^3)^p\equiv (26+1)^p\equiv \binom{p}{0}26^p+\binom{p}{1}26^{p-1}....+\binom{p}{p-2}26^2+\binom{p}{p-1}26+\binom{p}{p}\equiv 26p+1\equiv 1\pmod{169}</math>, so <math>26p\equiv 0\pmod{169}</math> and <math>p\equiv 0\pmod{13}</math>. Thus, we have that <math>5|n</math>, <math>3|n</math>, and <math>13|n</math>, so the smallest possible value of <math>n</math> is <math>3\times5\times13=\boxed{195}</math>.<br />
-Stormersyle<br />
<br />
==Solution 6(LTE)==<br />
We can see that <math>3^n-1 = 143^2*x</math>, which means that <math>v_{11}(3^n-1) \geq 2</math>, <math>v_{13}(3^n-1) \geq 2</math>. <math>v_{11}(3^n-1) = v_{11}(242) + v_{11}(\frac{n}{5})</math>, <math>v_{13}(3^n-1) = v_{13}(26) + v_{13}(\frac{n}{3})</math> by the Lifting the Exponent lemma. From the first equation we gather that 5 divides n, while from the second equation we gather that both 13 and 3 divide n as <math>v_{13}(3^n-1) \geq 2</math>. Therefore the minimum possible value of n is <math>3\times5\times13=\boxed{195}</math>.<br />
<br />
-bradleyguo<br />
<br />
==See Also==<br />
{{AIME box|year=2018|n=I|num-b=10|num-a=12}}<br />
{{MAA Notice}}</div>Bradleyguohttps://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_11&diff=1092282018 AIME I Problems/Problem 112019-08-22T21:24:33Z<p>Bradleyguo: /* Solution 6(LTE) */</p>
<hr />
<div><br />
==Problem==<br />
Find the least positive integer <math>n</math> such that when <math>3^n</math> is written in base <math>143</math>, its two right-most digits in base <math>143</math> are <math>01</math>.<br />
<br />
==Solutions==<br />
<br />
==Modular Arithmetic Solution- Strange (MASS)==<br />
Note that the given condition is equivalent to <math>3^n \equiv 1 \pmod{143^2}</math> and <math>143=11\cdot 13</math>. Because <math>gcd(11^2, 13^2) = 1</math>, the desired condition is equivalent to <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>.<br />
<br />
If <math>3^n \equiv 1 \pmod{121}</math>, one can see the sequence <math>1, 3, 9, 27, 81, 1, 3, 9...</math> so <math>5|n</math>.<br />
<br />
Now if <math>3^n \equiv 1 \pmod{169}</math>, it is harder. But we do observe that <math>3^3 \equiv 1 \pmod{13}</math>, therefore <math>3^3 = 13a + 1</math> for some integer <math>a</math>. So our goal is to find the first number <math>p_1</math> such that <math>(13a+1)^ {p_1} \equiv 1 \pmod{169}</math>. In other words, the <math>p_1 \equiv 0 \pmod{13}</math>. It is not difficult to see that the smallest <math>p_1=13</math>, so ultimately <math>3^{39} \equiv 1 \pmod{169}</math>. Therefore, <math>39|n</math>.<br />
<br />
The first <math>n</math> satisfying both criteria is thus <math>5\cdot 39=\boxed{195}</math>.<br />
<br />
-expiLnCalc<br />
<br />
==Solution 2==<br />
Note that Euler's Totient Theorem would not necessarily lead to the smallest <math>n</math> and that in this case that <math>n</math> is greater than <math>1000</math>. <br />
<br />
We wish to find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{143^2}</math>. This factors as <math>143^2=11^{2}*13^{2}</math>. Because <math>gcd(121, 169) = 1</math>, we can simply find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>.<br />
<br />
Quick inspection yields <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^3 \equiv 1 \pmod{13}</math>. Now we must find the smallest <math>k</math> such that <math>3^{3k} \equiv 1 \pmod{13}</math>. Euler's gives <math>3^{156} \equiv 1 \pmod{169}</math>. So <math>3k</math> is a factor of <math>156</math>. This gives <math>k=1,2, 4, 13, 26, 52</math>. Some more inspection yields <math>k=13</math> is the smallest valid <math>k</math>. So <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^{39} \equiv 1 \pmod{169}</math>. The least <math>n</math> satisfying both is <math>lcm(5, 39)=\boxed{195}</math>. (RegularHexagon)<br />
<br />
==Solution 3 (Big Bash)==<br />
Listing out the powers of <math>3</math>, modulo <math>169</math> and modulo <math>121</math>, we have:<br />
<cmath>\begin{array}{c|c|c}<br />
n & 3^n\mod{169} & 3^n\mod{121}\\ \hline<br />
0 & 1 & 1\\<br />
1 & 3 & 3\\<br />
2 & 9 & 9\\<br />
3 & 27 & 27\\<br />
4 & 81 & 81\\<br />
5 & 74 & 1\\<br />
6 & 53\\<br />
7 & 159\\<br />
8 & 139\\<br />
9 & 79\\<br />
10 & 68\\<br />
11 & 35\\<br />
12 & 105\\<br />
13 & 146\\<br />
14 & 100\\<br />
15 & 131\\<br />
16 & 55\\<br />
17 & 165\\<br />
18 & 157\\<br />
19 & 133\\<br />
20 & 61\\<br />
21 & 14\\<br />
22 & 42\\<br />
23 & 126\\<br />
24 & 40\\<br />
25 & 120\\<br />
26 & 22\\<br />
27 & 66\\<br />
28 & 29\\<br />
29 & 87\\<br />
30 & 92\\<br />
31 & 107\\<br />
32 & 152\\<br />
33 & 118\\<br />
34 & 16\\<br />
35 & 48\\<br />
36 & 144\\<br />
37 & 94\\<br />
38 & 113\\<br />
39 & 1\\<br />
\end{array}</cmath><br />
<br />
The powers of <math>3</math> repeat in cycles of <math>5</math> an <math>39</math> in modulo <math>121</math> and modulo <math>169</math>, respectively. The answer is <math>\text{lcm}(5, 39) = \boxed{195}</math>.<br />
<br />
==Solution 4(Order+Bash)==<br />
We have that <cmath>3^n \equiv 1 \pmod{143^2}.</cmath>Now, <math>3^{110} \equiv 1 \pmod{11^2}</math> so by the Fundamental Theorem of Orders, <math>\text{ord}_{11^2}(3)|110</math> and with some bashing, we get that it is <math>5</math>. Similarly, we get that <math>\text{ord}_{13^2}(3)=39</math>. Now, <math>\text{lcm}(39,5)=\boxed{195}</math> which is our desired solution.<br />
<br />
==Solution 5 (Easy Binomial Theorem)==<br />
We wish to find the smallest <math>n</math> such that <math>3^n\equiv 1\pmod{143^2}</math>, so we want <math>n\equiv 1\pmod{121}</math> and <math>n\equiv 1\pmod{169}</math>. Note that <math>3^5\equiv 1\pmod{121}</math>, so <math>3^n</math> repeats <math>121</math> with a period of <math>5</math>, so <math>5|n</math>. Now, in order for <math>n\equiv 1\pmod{169}</math>, then <math>n\equiv 1\pmod{13}</math>. Because <math>3^3\equiv 1\pmod{13}</math>, <math>3^n</math> repeats with a period of <math>3</math>, so <math>3|n</math>. <br />
Hence, we have that for some positive integer <math>p</math>, <math>3^n\equiv (3^3)^p\equiv (26+1)^p\equiv \binom{p}{0}26^p+\binom{p}{1}26^{p-1}....+\binom{p}{p-2}26^2+\binom{p}{p-1}26+\binom{p}{p}\equiv 26p+1\equiv 1\pmod{169}</math>, so <math>26p\equiv 0\pmod{169}</math> and <math>p\equiv 0\pmod{13}</math>. Thus, we have that <math>5|n</math>, <math>3|n</math>, and <math>13|n</math>, so the smallest possible value of <math>n</math> is <math>3\times5\times13=\boxed{195}</math>.<br />
-Stormersyle<br />
<br />
==Solution 6(LTE)==<br />
We can see that <math>3^n-1 = 143^2*x</math>, which means that <math>v_{11}(3^n-1) \geq 2</math>, <math>v_{13}(3^n-1) \geq 2</math>. <math>v_{11}(3^n-1) = v_{11}(242) + v_{11}(\frac{n}{5})</math>, <math>v_{13}(3^n-1) = v_{13}(26) + v_{13}(\frac{n}{3})</math> by the Lifting the Exponent lemma. From the first equation we gather that 5 divides n, while from the second equation we gather that both 13 and 3 divide n as <math>v_{13}(3^n-1)>=2</math>. Therefore the minimum possible value of n is <math>3\times5\times13=\boxed{195}</math>.<br />
<br />
-bradleyguo<br />
<br />
==See Also==<br />
{{AIME box|year=2018|n=I|num-b=10|num-a=12}}<br />
{{MAA Notice}}</div>Bradleyguohttps://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_11&diff=1092272018 AIME I Problems/Problem 112019-08-22T21:24:14Z<p>Bradleyguo: /* Solution 6(LTE) */</p>
<hr />
<div><br />
==Problem==<br />
Find the least positive integer <math>n</math> such that when <math>3^n</math> is written in base <math>143</math>, its two right-most digits in base <math>143</math> are <math>01</math>.<br />
<br />
==Solutions==<br />
<br />
==Modular Arithmetic Solution- Strange (MASS)==<br />
Note that the given condition is equivalent to <math>3^n \equiv 1 \pmod{143^2}</math> and <math>143=11\cdot 13</math>. Because <math>gcd(11^2, 13^2) = 1</math>, the desired condition is equivalent to <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>.<br />
<br />
If <math>3^n \equiv 1 \pmod{121}</math>, one can see the sequence <math>1, 3, 9, 27, 81, 1, 3, 9...</math> so <math>5|n</math>.<br />
<br />
Now if <math>3^n \equiv 1 \pmod{169}</math>, it is harder. But we do observe that <math>3^3 \equiv 1 \pmod{13}</math>, therefore <math>3^3 = 13a + 1</math> for some integer <math>a</math>. So our goal is to find the first number <math>p_1</math> such that <math>(13a+1)^ {p_1} \equiv 1 \pmod{169}</math>. In other words, the <math>p_1 \equiv 0 \pmod{13}</math>. It is not difficult to see that the smallest <math>p_1=13</math>, so ultimately <math>3^{39} \equiv 1 \pmod{169}</math>. Therefore, <math>39|n</math>.<br />
<br />
The first <math>n</math> satisfying both criteria is thus <math>5\cdot 39=\boxed{195}</math>.<br />
<br />
-expiLnCalc<br />
<br />
==Solution 2==<br />
Note that Euler's Totient Theorem would not necessarily lead to the smallest <math>n</math> and that in this case that <math>n</math> is greater than <math>1000</math>. <br />
<br />
We wish to find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{143^2}</math>. This factors as <math>143^2=11^{2}*13^{2}</math>. Because <math>gcd(121, 169) = 1</math>, we can simply find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>.<br />
<br />
Quick inspection yields <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^3 \equiv 1 \pmod{13}</math>. Now we must find the smallest <math>k</math> such that <math>3^{3k} \equiv 1 \pmod{13}</math>. Euler's gives <math>3^{156} \equiv 1 \pmod{169}</math>. So <math>3k</math> is a factor of <math>156</math>. This gives <math>k=1,2, 4, 13, 26, 52</math>. Some more inspection yields <math>k=13</math> is the smallest valid <math>k</math>. So <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^{39} \equiv 1 \pmod{169}</math>. The least <math>n</math> satisfying both is <math>lcm(5, 39)=\boxed{195}</math>. (RegularHexagon)<br />
<br />
==Solution 3 (Big Bash)==<br />
Listing out the powers of <math>3</math>, modulo <math>169</math> and modulo <math>121</math>, we have:<br />
<cmath>\begin{array}{c|c|c}<br />
n & 3^n\mod{169} & 3^n\mod{121}\\ \hline<br />
0 & 1 & 1\\<br />
1 & 3 & 3\\<br />
2 & 9 & 9\\<br />
3 & 27 & 27\\<br />
4 & 81 & 81\\<br />
5 & 74 & 1\\<br />
6 & 53\\<br />
7 & 159\\<br />
8 & 139\\<br />
9 & 79\\<br />
10 & 68\\<br />
11 & 35\\<br />
12 & 105\\<br />
13 & 146\\<br />
14 & 100\\<br />
15 & 131\\<br />
16 & 55\\<br />
17 & 165\\<br />
18 & 157\\<br />
19 & 133\\<br />
20 & 61\\<br />
21 & 14\\<br />
22 & 42\\<br />
23 & 126\\<br />
24 & 40\\<br />
25 & 120\\<br />
26 & 22\\<br />
27 & 66\\<br />
28 & 29\\<br />
29 & 87\\<br />
30 & 92\\<br />
31 & 107\\<br />
32 & 152\\<br />
33 & 118\\<br />
34 & 16\\<br />
35 & 48\\<br />
36 & 144\\<br />
37 & 94\\<br />
38 & 113\\<br />
39 & 1\\<br />
\end{array}</cmath><br />
<br />
The powers of <math>3</math> repeat in cycles of <math>5</math> an <math>39</math> in modulo <math>121</math> and modulo <math>169</math>, respectively. The answer is <math>\text{lcm}(5, 39) = \boxed{195}</math>.<br />
<br />
==Solution 4(Order+Bash)==<br />
We have that <cmath>3^n \equiv 1 \pmod{143^2}.</cmath>Now, <math>3^{110} \equiv 1 \pmod{11^2}</math> so by the Fundamental Theorem of Orders, <math>\text{ord}_{11^2}(3)|110</math> and with some bashing, we get that it is <math>5</math>. Similarly, we get that <math>\text{ord}_{13^2}(3)=39</math>. Now, <math>\text{lcm}(39,5)=\boxed{195}</math> which is our desired solution.<br />
<br />
==Solution 5 (Easy Binomial Theorem)==<br />
We wish to find the smallest <math>n</math> such that <math>3^n\equiv 1\pmod{143^2}</math>, so we want <math>n\equiv 1\pmod{121}</math> and <math>n\equiv 1\pmod{169}</math>. Note that <math>3^5\equiv 1\pmod{121}</math>, so <math>3^n</math> repeats <math>121</math> with a period of <math>5</math>, so <math>5|n</math>. Now, in order for <math>n\equiv 1\pmod{169}</math>, then <math>n\equiv 1\pmod{13}</math>. Because <math>3^3\equiv 1\pmod{13}</math>, <math>3^n</math> repeats with a period of <math>3</math>, so <math>3|n</math>. <br />
Hence, we have that for some positive integer <math>p</math>, <math>3^n\equiv (3^3)^p\equiv (26+1)^p\equiv \binom{p}{0}26^p+\binom{p}{1}26^{p-1}....+\binom{p}{p-2}26^2+\binom{p}{p-1}26+\binom{p}{p}\equiv 26p+1\equiv 1\pmod{169}</math>, so <math>26p\equiv 0\pmod{169}</math> and <math>p\equiv 0\pmod{13}</math>. Thus, we have that <math>5|n</math>, <math>3|n</math>, and <math>13|n</math>, so the smallest possible value of <math>n</math> is <math>3\times5\times13=\boxed{195}</math>.<br />
-Stormersyle<br />
<br />
==Solution 6(LTE)==<br />
We can see that <math>3^n-1 = 143^2*x</math>, which means that <math>v_{11}(3^n-1) \geq 2</math>, <math>v_{13}(3^n-1) >= 2</math>. <math>v_{11}(3^n-1) = v_{11}(242) + v_{11}(\frac{n}{5})</math>, <math>v_{13}(3^n-1) = v_{13}(26) + v_{13}(\frac{n}{3})</math> by the Lifting the Exponent lemma. From the first equation we gather that 5 divides n, while from the second equation we gather that both 13 and 3 divide n as <math>v_{13}(3^n-1)>=2</math>. Therefore the minimum possible value of n is <math>3\times5\times13=\boxed{195}</math>.<br />
-bradleyguo<br />
<br />
==See Also==<br />
{{AIME box|year=2018|n=I|num-b=10|num-a=12}}<br />
{{MAA Notice}}</div>Bradleyguohttps://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_11&diff=1092262018 AIME I Problems/Problem 112019-08-22T21:23:05Z<p>Bradleyguo: /* Solution 6(LTE) */</p>
<hr />
<div><br />
==Problem==<br />
Find the least positive integer <math>n</math> such that when <math>3^n</math> is written in base <math>143</math>, its two right-most digits in base <math>143</math> are <math>01</math>.<br />
<br />
==Solutions==<br />
<br />
==Modular Arithmetic Solution- Strange (MASS)==<br />
Note that the given condition is equivalent to <math>3^n \equiv 1 \pmod{143^2}</math> and <math>143=11\cdot 13</math>. Because <math>gcd(11^2, 13^2) = 1</math>, the desired condition is equivalent to <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>.<br />
<br />
If <math>3^n \equiv 1 \pmod{121}</math>, one can see the sequence <math>1, 3, 9, 27, 81, 1, 3, 9...</math> so <math>5|n</math>.<br />
<br />
Now if <math>3^n \equiv 1 \pmod{169}</math>, it is harder. But we do observe that <math>3^3 \equiv 1 \pmod{13}</math>, therefore <math>3^3 = 13a + 1</math> for some integer <math>a</math>. So our goal is to find the first number <math>p_1</math> such that <math>(13a+1)^ {p_1} \equiv 1 \pmod{169}</math>. In other words, the <math>p_1 \equiv 0 \pmod{13}</math>. It is not difficult to see that the smallest <math>p_1=13</math>, so ultimately <math>3^{39} \equiv 1 \pmod{169}</math>. Therefore, <math>39|n</math>.<br />
<br />
The first <math>n</math> satisfying both criteria is thus <math>5\cdot 39=\boxed{195}</math>.<br />
<br />
-expiLnCalc<br />
<br />
==Solution 2==<br />
Note that Euler's Totient Theorem would not necessarily lead to the smallest <math>n</math> and that in this case that <math>n</math> is greater than <math>1000</math>. <br />
<br />
We wish to find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{143^2}</math>. This factors as <math>143^2=11^{2}*13^{2}</math>. Because <math>gcd(121, 169) = 1</math>, we can simply find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>.<br />
<br />
Quick inspection yields <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^3 \equiv 1 \pmod{13}</math>. Now we must find the smallest <math>k</math> such that <math>3^{3k} \equiv 1 \pmod{13}</math>. Euler's gives <math>3^{156} \equiv 1 \pmod{169}</math>. So <math>3k</math> is a factor of <math>156</math>. This gives <math>k=1,2, 4, 13, 26, 52</math>. Some more inspection yields <math>k=13</math> is the smallest valid <math>k</math>. So <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^{39} \equiv 1 \pmod{169}</math>. The least <math>n</math> satisfying both is <math>lcm(5, 39)=\boxed{195}</math>. (RegularHexagon)<br />
<br />
==Solution 3 (Big Bash)==<br />
Listing out the powers of <math>3</math>, modulo <math>169</math> and modulo <math>121</math>, we have:<br />
<cmath>\begin{array}{c|c|c}<br />
n & 3^n\mod{169} & 3^n\mod{121}\\ \hline<br />
0 & 1 & 1\\<br />
1 & 3 & 3\\<br />
2 & 9 & 9\\<br />
3 & 27 & 27\\<br />
4 & 81 & 81\\<br />
5 & 74 & 1\\<br />
6 & 53\\<br />
7 & 159\\<br />
8 & 139\\<br />
9 & 79\\<br />
10 & 68\\<br />
11 & 35\\<br />
12 & 105\\<br />
13 & 146\\<br />
14 & 100\\<br />
15 & 131\\<br />
16 & 55\\<br />
17 & 165\\<br />
18 & 157\\<br />
19 & 133\\<br />
20 & 61\\<br />
21 & 14\\<br />
22 & 42\\<br />
23 & 126\\<br />
24 & 40\\<br />
25 & 120\\<br />
26 & 22\\<br />
27 & 66\\<br />
28 & 29\\<br />
29 & 87\\<br />
30 & 92\\<br />
31 & 107\\<br />
32 & 152\\<br />
33 & 118\\<br />
34 & 16\\<br />
35 & 48\\<br />
36 & 144\\<br />
37 & 94\\<br />
38 & 113\\<br />
39 & 1\\<br />
\end{array}</cmath><br />
<br />
The powers of <math>3</math> repeat in cycles of <math>5</math> an <math>39</math> in modulo <math>121</math> and modulo <math>169</math>, respectively. The answer is <math>\text{lcm}(5, 39) = \boxed{195}</math>.<br />
<br />
==Solution 4(Order+Bash)==<br />
We have that <cmath>3^n \equiv 1 \pmod{143^2}.</cmath>Now, <math>3^{110} \equiv 1 \pmod{11^2}</math> so by the Fundamental Theorem of Orders, <math>\text{ord}_{11^2}(3)|110</math> and with some bashing, we get that it is <math>5</math>. Similarly, we get that <math>\text{ord}_{13^2}(3)=39</math>. Now, <math>\text{lcm}(39,5)=\boxed{195}</math> which is our desired solution.<br />
<br />
==Solution 5 (Easy Binomial Theorem)==<br />
We wish to find the smallest <math>n</math> such that <math>3^n\equiv 1\pmod{143^2}</math>, so we want <math>n\equiv 1\pmod{121}</math> and <math>n\equiv 1\pmod{169}</math>. Note that <math>3^5\equiv 1\pmod{121}</math>, so <math>3^n</math> repeats <math>121</math> with a period of <math>5</math>, so <math>5|n</math>. Now, in order for <math>n\equiv 1\pmod{169}</math>, then <math>n\equiv 1\pmod{13}</math>. Because <math>3^3\equiv 1\pmod{13}</math>, <math>3^n</math> repeats with a period of <math>3</math>, so <math>3|n</math>. <br />
Hence, we have that for some positive integer <math>p</math>, <math>3^n\equiv (3^3)^p\equiv (26+1)^p\equiv \binom{p}{0}26^p+\binom{p}{1}26^{p-1}....+\binom{p}{p-2}26^2+\binom{p}{p-1}26+\binom{p}{p}\equiv 26p+1\equiv 1\pmod{169}</math>, so <math>26p\equiv 0\pmod{169}</math> and <math>p\equiv 0\pmod{13}</math>. Thus, we have that <math>5|n</math>, <math>3|n</math>, and <math>13|n</math>, so the smallest possible value of <math>n</math> is <math>3\times5\times13=\boxed{195}</math>.<br />
-Stormersyle<br />
<br />
==Solution 6(LTE)==<br />
We can see that <math>3^n-1 = 143^2*x</math>, which means that <math>v_{11}(3^n-1) >= 2</math>, <math>v_{13}(3^n-1) >= 2</math>. <math>v_{11}(3^n-1) = v_{11}(242) + v_{11}(\frac{n}{5})</math>, <math>v_{13}(3^n-1) = v_{13}(26) + v_{11}(\frac{n}{3})</math> by the Lifting the Exponent lemma. From the first equation we gather that 5 divides n, while from the second equation we gather that both 13 and 3 divide n as <math>v_{13}(3^n-1)>=2</math>. Therefore the minimum possible value of n is <math>3\times5\times13=\boxed{195}</math>.<br />
-bradleyguo<br />
<br />
==See Also==<br />
{{AIME box|year=2018|n=I|num-b=10|num-a=12}}<br />
{{MAA Notice}}</div>Bradleyguohttps://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_11&diff=1092252018 AIME I Problems/Problem 112019-08-22T21:21:36Z<p>Bradleyguo: /* Solution 6(LTE) */</p>
<hr />
<div><br />
==Problem==<br />
Find the least positive integer <math>n</math> such that when <math>3^n</math> is written in base <math>143</math>, its two right-most digits in base <math>143</math> are <math>01</math>.<br />
<br />
==Solutions==<br />
<br />
==Modular Arithmetic Solution- Strange (MASS)==<br />
Note that the given condition is equivalent to <math>3^n \equiv 1 \pmod{143^2}</math> and <math>143=11\cdot 13</math>. Because <math>gcd(11^2, 13^2) = 1</math>, the desired condition is equivalent to <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>.<br />
<br />
If <math>3^n \equiv 1 \pmod{121}</math>, one can see the sequence <math>1, 3, 9, 27, 81, 1, 3, 9...</math> so <math>5|n</math>.<br />
<br />
Now if <math>3^n \equiv 1 \pmod{169}</math>, it is harder. But we do observe that <math>3^3 \equiv 1 \pmod{13}</math>, therefore <math>3^3 = 13a + 1</math> for some integer <math>a</math>. So our goal is to find the first number <math>p_1</math> such that <math>(13a+1)^ {p_1} \equiv 1 \pmod{169}</math>. In other words, the <math>p_1 \equiv 0 \pmod{13}</math>. It is not difficult to see that the smallest <math>p_1=13</math>, so ultimately <math>3^{39} \equiv 1 \pmod{169}</math>. Therefore, <math>39|n</math>.<br />
<br />
The first <math>n</math> satisfying both criteria is thus <math>5\cdot 39=\boxed{195}</math>.<br />
<br />
-expiLnCalc<br />
<br />
==Solution 2==<br />
Note that Euler's Totient Theorem would not necessarily lead to the smallest <math>n</math> and that in this case that <math>n</math> is greater than <math>1000</math>. <br />
<br />
We wish to find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{143^2}</math>. This factors as <math>143^2=11^{2}*13^{2}</math>. Because <math>gcd(121, 169) = 1</math>, we can simply find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>.<br />
<br />
Quick inspection yields <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^3 \equiv 1 \pmod{13}</math>. Now we must find the smallest <math>k</math> such that <math>3^{3k} \equiv 1 \pmod{13}</math>. Euler's gives <math>3^{156} \equiv 1 \pmod{169}</math>. So <math>3k</math> is a factor of <math>156</math>. This gives <math>k=1,2, 4, 13, 26, 52</math>. Some more inspection yields <math>k=13</math> is the smallest valid <math>k</math>. So <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^{39} \equiv 1 \pmod{169}</math>. The least <math>n</math> satisfying both is <math>lcm(5, 39)=\boxed{195}</math>. (RegularHexagon)<br />
<br />
==Solution 3 (Big Bash)==<br />
Listing out the powers of <math>3</math>, modulo <math>169</math> and modulo <math>121</math>, we have:<br />
<cmath>\begin{array}{c|c|c}<br />
n & 3^n\mod{169} & 3^n\mod{121}\\ \hline<br />
0 & 1 & 1\\<br />
1 & 3 & 3\\<br />
2 & 9 & 9\\<br />
3 & 27 & 27\\<br />
4 & 81 & 81\\<br />
5 & 74 & 1\\<br />
6 & 53\\<br />
7 & 159\\<br />
8 & 139\\<br />
9 & 79\\<br />
10 & 68\\<br />
11 & 35\\<br />
12 & 105\\<br />
13 & 146\\<br />
14 & 100\\<br />
15 & 131\\<br />
16 & 55\\<br />
17 & 165\\<br />
18 & 157\\<br />
19 & 133\\<br />
20 & 61\\<br />
21 & 14\\<br />
22 & 42\\<br />
23 & 126\\<br />
24 & 40\\<br />
25 & 120\\<br />
26 & 22\\<br />
27 & 66\\<br />
28 & 29\\<br />
29 & 87\\<br />
30 & 92\\<br />
31 & 107\\<br />
32 & 152\\<br />
33 & 118\\<br />
34 & 16\\<br />
35 & 48\\<br />
36 & 144\\<br />
37 & 94\\<br />
38 & 113\\<br />
39 & 1\\<br />
\end{array}</cmath><br />
<br />
The powers of <math>3</math> repeat in cycles of <math>5</math> an <math>39</math> in modulo <math>121</math> and modulo <math>169</math>, respectively. The answer is <math>\text{lcm}(5, 39) = \boxed{195}</math>.<br />
<br />
==Solution 4(Order+Bash)==<br />
We have that <cmath>3^n \equiv 1 \pmod{143^2}.</cmath>Now, <math>3^{110} \equiv 1 \pmod{11^2}</math> so by the Fundamental Theorem of Orders, <math>\text{ord}_{11^2}(3)|110</math> and with some bashing, we get that it is <math>5</math>. Similarly, we get that <math>\text{ord}_{13^2}(3)=39</math>. Now, <math>\text{lcm}(39,5)=\boxed{195}</math> which is our desired solution.<br />
<br />
==Solution 5 (Easy Binomial Theorem)==<br />
We wish to find the smallest <math>n</math> such that <math>3^n\equiv 1\pmod{143^2}</math>, so we want <math>n\equiv 1\pmod{121}</math> and <math>n\equiv 1\pmod{169}</math>. Note that <math>3^5\equiv 1\pmod{121}</math>, so <math>3^n</math> repeats <math>121</math> with a period of <math>5</math>, so <math>5|n</math>. Now, in order for <math>n\equiv 1\pmod{169}</math>, then <math>n\equiv 1\pmod{13}</math>. Because <math>3^3\equiv 1\pmod{13}</math>, <math>3^n</math> repeats with a period of <math>3</math>, so <math>3|n</math>. <br />
Hence, we have that for some positive integer <math>p</math>, <math>3^n\equiv (3^3)^p\equiv (26+1)^p\equiv \binom{p}{0}26^p+\binom{p}{1}26^{p-1}....+\binom{p}{p-2}26^2+\binom{p}{p-1}26+\binom{p}{p}\equiv 26p+1\equiv 1\pmod{169}</math>, so <math>26p\equiv 0\pmod{169}</math> and <math>p\equiv 0\pmod{13}</math>. Thus, we have that <math>5|n</math>, <math>3|n</math>, and <math>13|n</math>, so the smallest possible value of <math>n</math> is <math>3\times5\times13=\boxed{195}</math>.<br />
-Stormersyle<br />
<br />
==Solution 6(LTE)==<br />
We can see that <math>3^n-1 = 143^2*x</math>, which means that <math>v_(11)(3^n-1) >= 2</math>, <math>v_(13)(3^n-1) >= 2</math>. <math>v_(11)(3^n-1) = v_(11)(242) + v_11(\frac{n}{5})</math>, <math>v_(13)(3^n-1) = v_(13)(26) + v_(11)(\frac{n}{3})</math> by the Lifting the Exponent lemma. From the first equation we gather that 5 divides n, while from the second equation we gather that both 13 and 3 divide n as <math>v_13(3^n-1)>=2</math>. Therefore the minimum possible value of n is <math>3\times5\times13=\boxed{195}</math>.<br />
-bradleyguo<br />
<br />
==See Also==<br />
{{AIME box|year=2018|n=I|num-b=10|num-a=12}}<br />
{{MAA Notice}}</div>Bradleyguohttps://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_11&diff=1092242018 AIME I Problems/Problem 112019-08-22T21:20:47Z<p>Bradleyguo: </p>
<hr />
<div><br />
==Problem==<br />
Find the least positive integer <math>n</math> such that when <math>3^n</math> is written in base <math>143</math>, its two right-most digits in base <math>143</math> are <math>01</math>.<br />
<br />
==Solutions==<br />
<br />
==Modular Arithmetic Solution- Strange (MASS)==<br />
Note that the given condition is equivalent to <math>3^n \equiv 1 \pmod{143^2}</math> and <math>143=11\cdot 13</math>. Because <math>gcd(11^2, 13^2) = 1</math>, the desired condition is equivalent to <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>.<br />
<br />
If <math>3^n \equiv 1 \pmod{121}</math>, one can see the sequence <math>1, 3, 9, 27, 81, 1, 3, 9...</math> so <math>5|n</math>.<br />
<br />
Now if <math>3^n \equiv 1 \pmod{169}</math>, it is harder. But we do observe that <math>3^3 \equiv 1 \pmod{13}</math>, therefore <math>3^3 = 13a + 1</math> for some integer <math>a</math>. So our goal is to find the first number <math>p_1</math> such that <math>(13a+1)^ {p_1} \equiv 1 \pmod{169}</math>. In other words, the <math>p_1 \equiv 0 \pmod{13}</math>. It is not difficult to see that the smallest <math>p_1=13</math>, so ultimately <math>3^{39} \equiv 1 \pmod{169}</math>. Therefore, <math>39|n</math>.<br />
<br />
The first <math>n</math> satisfying both criteria is thus <math>5\cdot 39=\boxed{195}</math>.<br />
<br />
-expiLnCalc<br />
<br />
==Solution 2==<br />
Note that Euler's Totient Theorem would not necessarily lead to the smallest <math>n</math> and that in this case that <math>n</math> is greater than <math>1000</math>. <br />
<br />
We wish to find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{143^2}</math>. This factors as <math>143^2=11^{2}*13^{2}</math>. Because <math>gcd(121, 169) = 1</math>, we can simply find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>.<br />
<br />
Quick inspection yields <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^3 \equiv 1 \pmod{13}</math>. Now we must find the smallest <math>k</math> such that <math>3^{3k} \equiv 1 \pmod{13}</math>. Euler's gives <math>3^{156} \equiv 1 \pmod{169}</math>. So <math>3k</math> is a factor of <math>156</math>. This gives <math>k=1,2, 4, 13, 26, 52</math>. Some more inspection yields <math>k=13</math> is the smallest valid <math>k</math>. So <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^{39} \equiv 1 \pmod{169}</math>. The least <math>n</math> satisfying both is <math>lcm(5, 39)=\boxed{195}</math>. (RegularHexagon)<br />
<br />
==Solution 3 (Big Bash)==<br />
Listing out the powers of <math>3</math>, modulo <math>169</math> and modulo <math>121</math>, we have:<br />
<cmath>\begin{array}{c|c|c}<br />
n & 3^n\mod{169} & 3^n\mod{121}\\ \hline<br />
0 & 1 & 1\\<br />
1 & 3 & 3\\<br />
2 & 9 & 9\\<br />
3 & 27 & 27\\<br />
4 & 81 & 81\\<br />
5 & 74 & 1\\<br />
6 & 53\\<br />
7 & 159\\<br />
8 & 139\\<br />
9 & 79\\<br />
10 & 68\\<br />
11 & 35\\<br />
12 & 105\\<br />
13 & 146\\<br />
14 & 100\\<br />
15 & 131\\<br />
16 & 55\\<br />
17 & 165\\<br />
18 & 157\\<br />
19 & 133\\<br />
20 & 61\\<br />
21 & 14\\<br />
22 & 42\\<br />
23 & 126\\<br />
24 & 40\\<br />
25 & 120\\<br />
26 & 22\\<br />
27 & 66\\<br />
28 & 29\\<br />
29 & 87\\<br />
30 & 92\\<br />
31 & 107\\<br />
32 & 152\\<br />
33 & 118\\<br />
34 & 16\\<br />
35 & 48\\<br />
36 & 144\\<br />
37 & 94\\<br />
38 & 113\\<br />
39 & 1\\<br />
\end{array}</cmath><br />
<br />
The powers of <math>3</math> repeat in cycles of <math>5</math> an <math>39</math> in modulo <math>121</math> and modulo <math>169</math>, respectively. The answer is <math>\text{lcm}(5, 39) = \boxed{195}</math>.<br />
<br />
==Solution 4(Order+Bash)==<br />
We have that <cmath>3^n \equiv 1 \pmod{143^2}.</cmath>Now, <math>3^{110} \equiv 1 \pmod{11^2}</math> so by the Fundamental Theorem of Orders, <math>\text{ord}_{11^2}(3)|110</math> and with some bashing, we get that it is <math>5</math>. Similarly, we get that <math>\text{ord}_{13^2}(3)=39</math>. Now, <math>\text{lcm}(39,5)=\boxed{195}</math> which is our desired solution.<br />
<br />
==Solution 5 (Easy Binomial Theorem)==<br />
We wish to find the smallest <math>n</math> such that <math>3^n\equiv 1\pmod{143^2}</math>, so we want <math>n\equiv 1\pmod{121}</math> and <math>n\equiv 1\pmod{169}</math>. Note that <math>3^5\equiv 1\pmod{121}</math>, so <math>3^n</math> repeats <math>121</math> with a period of <math>5</math>, so <math>5|n</math>. Now, in order for <math>n\equiv 1\pmod{169}</math>, then <math>n\equiv 1\pmod{13}</math>. Because <math>3^3\equiv 1\pmod{13}</math>, <math>3^n</math> repeats with a period of <math>3</math>, so <math>3|n</math>. <br />
Hence, we have that for some positive integer <math>p</math>, <math>3^n\equiv (3^3)^p\equiv (26+1)^p\equiv \binom{p}{0}26^p+\binom{p}{1}26^{p-1}....+\binom{p}{p-2}26^2+\binom{p}{p-1}26+\binom{p}{p}\equiv 26p+1\equiv 1\pmod{169}</math>, so <math>26p\equiv 0\pmod{169}</math> and <math>p\equiv 0\pmod{13}</math>. Thus, we have that <math>5|n</math>, <math>3|n</math>, and <math>13|n</math>, so the smallest possible value of <math>n</math> is <math>3\times5\times13=\boxed{195}</math>.<br />
-Stormersyle<br />
<br />
==Solution 6(LTE)==<br />
We can see that <math>3^n-1 = 143^2*x</math>, which means that <math>v_11(3^n-1) >= 2</math>, <math>v_13(3^n-1) >= 2</math>. <math>v_11(3^n-1) = v_11(242) + v_11(\frac{n}{5})</math>, <math>v_13(3^n-1) = v_13(26) + v_11(\frac{n}{3})</math> by the Lifting the Exponent lemma. From the first equation we gather that 5 divides n, while from the second equation we gather that both 13 and 3 divide n as <math>v_13(3^n-1)>=2</math>. Therefore the minimum possible value of n is <math>3\times5\times13=\boxed{195}</math>.<br />
-bradleyguo<br />
<br />
==See Also==<br />
{{AIME box|year=2018|n=I|num-b=10|num-a=12}}<br />
{{MAA Notice}}</div>Bradleyguohttps://artofproblemsolving.com/wiki/index.php?title=2019_AMC_10B_Problems/Problem_23&diff=1060462019 AMC 10B Problems/Problem 232019-05-30T22:28:00Z<p>Bradleyguo: </p>
<hr />
<div>{{duplicate|[[2019 AMC 10B Problems|2019 AMC 10B #23]] and [[2019 AMC 12B Problems|2019 AMC 12B #20]]}}<br />
<br />
==Problem==<br />
<br />
Points <math>A(6,13)</math> and <math>B(12,11)</math> lie on circle <math>\omega</math> in the plane. Suppose that the tangent lines to <math>\omega</math> at <math>A</math> and <math>B</math> intersect at a point on the <math>x</math>-axis. What is the area of <math>\omega</math>?<br />
<br />
<math>\textbf{(A) }\frac{83\pi}{8}\qquad\textbf{(B) }\frac{21\pi}{2}\qquad\textbf{(C) }<br />
\frac{85\pi}{8}\qquad\textbf{(D) }\frac{43\pi}{4}\qquad\textbf{(E) }\frac{87\pi}{8}</math><br />
<br />
==Solution 1==<br />
First, observe that the two tangent lines are of identical length. Therefore, supposing that the point of intersection is <math>(x, 0)</math>, the Pythagorean Theorem gives <math>x=5</math>.<br />
<br />
Further, notice (due to the right angles formed by a radius and its tangent line) that the quadrilateral (a kite) defined by the circle's center, <math>A</math>, <math>B</math>, and <math>(5, 0)</math> is cyclic. Therefore, we can apply Ptolemy's Theorem to give<br />
<math>2\sqrt{170}x = d \sqrt{40}</math>, where <math>d</math> is the distance between the circle's center and <math>(5, 0)</math>. Therefore, <math>d = \sqrt{17}x</math>. Using the Pythagorean Theorem on the triangle formed by the point <math>(5, 0)</math>, either one of <math>A</math> or <math>B</math>, and the circle's center, we find that <math>170 + x^2 = 17x^2</math>, so <math>x^2 = \frac{85}{8}</math>, and thus the answer is <math>\boxed{\textbf{(C) }\frac{85}{8}\pi}</math>.<br />
<br />
==Solution 2==<br />
We firstly obtain <math>x=5</math> as in Solution 1. Label the point <math>(5,0)</math> as <math>C</math>. The midpoint <math>M</math> of segment <math>AB</math> is <math>(9, 12)</math>. Notice that the center of the circle must lie on the line passing through the points <math>C</math> and <math>M</math>. Thus, the center of the circle lies on the line <math>y=3x-15</math>. <br />
<br />
Line <math>AC</math> is <math>y=13x-65</math>. Therefore, the slope of the line perpendicular to <math>AC</math> is <math>-\frac{1}{13}</math>, so its equation is <math>y=-\frac{x}{13}+\frac{175}{13}</math>. <br />
<br />
But notice that this line must pass through <math>A(6, 13)</math> and <math>(x, 3x-15)</math>. Hence <math>3x-15=-\frac{x}{13}+\frac{175}{13} \Rightarrow x=\frac{37}{4}</math>. So the center of the circle is <math>\left(\frac{37}{4}, \frac{51}{4}\right)</math>. <br />
<br />
Finally, the distance between the center, <math>\left(\frac{37}{4}, \frac{51}{4}\right)</math>, and point <math>A</math> is <math>\frac{\sqrt{170}}{4}</math>. Thus the area of the circle is <math>\boxed{\textbf{(C) }\frac{85}{8}\pi}</math>.<br />
<br />
==Solution 3==<br />
The midpoint of <math>AB</math> is <math>D(9,12)</math>. Let the tangent lines at <math>A</math> and <math>B</math> intersect at <math>C(a,0)</math> on the <math>x</math>-axis. Then <math>CD</math> is the perpendicular bisector of <math>AB</math>. Let the center of the circle be <math>O</math>. Then <math>\triangle AOC</math> is similar to <math>\triangle DAC</math>, so <math>\frac{OA}{AC} = \frac{AD}{DC}</math>.<br />
The slope of <math>AB</math> is <math>\frac{13-11}{6-12}=\frac{-1}{3}</math>, so the slope of <math>CD</math> is <math>3</math>. Hence, the equation of <math>CD</math> is <math>y-12=3(x-9) \Rightarrow y=3x-15</math>. Letting <math>y=0</math>, we have <math>x=5</math>, so <math>C = (5,0)</math>.<br />
<br />
Now, we compute <math>AC=\sqrt{(6-5)^2+(13-0)^2}=\sqrt{170}</math>,<br />
<math>AD=\sqrt{(6-9)^2+(13-12)^2}=\sqrt{10}</math>, and<br />
<math>DC=\sqrt{(9-5)^2+(12-0)^2}=\sqrt{160}</math>.<br />
<br />
Therefore <math>OA = \frac{AC\cdot AD}{DC}=\sqrt{\frac{85}{8}}</math>,<br />
and consequently, the area of the circle is <math>\pi\cdot OA^2 = \boxed{\textbf{(C) }\frac{85}{8}\pi}</math>.<br />
<br />
==Solution 4 (Power of a Point)==<br />
<br />
Firstly, the point of intersection of the two tangent lines has an equal distance to points <math>A</math> and <math>B</math> due to power of a point theorem. This means we can easily find the point, which is <math>(5, 0)</math>. Label this point <math>X</math>. <math>\triangle{XAB}</math> is an isosceles triangle with lengths, <math>\sqrt{170}</math>, <math>\sqrt{170}</math>, and <math>2\sqrt{10}</math>. Label the midpoint of segment <math>AB</math> as <math>M</math>. The height of this triangle, or <math>\overline{XM}</math>, is <math>4\sqrt{10}</math>. Since <math>\overline{XM}</math> bisects <math>\overline{AB}</math>, <math>\overleftrightarrow{XM}</math> contains the diameter of circle <math>\omega</math>. Let the two points on circle <math>\omega</math> where <math>\overleftrightarrow{XM}</math> intersects be <math>P</math> and <math>Q</math> with <math>\overline{XP}</math> being the shorter of the two. Now let <math>\overline{MP}</math> be <math>x</math> and <math>\overline{MQ}</math> be <math>y</math>. By Power of a Point on <math>\overline{PQ}</math> and <math>\overline{AB}</math>, <math>xy = (\sqrt{10})^2 = 10</math>. Applying Power of a Point again on <math>\overline{XQ}</math> and <math>\overline{XA}</math>, <math>(4\sqrt{10}-x)(4\sqrt{10}+y)=(\sqrt{170})^2=170</math>. Expanding while using the fact that <math>xy = 10</math>, <math>y=x+\frac{\sqrt{10}}{2}</math>. Plugging this into <math>xy=10</math>, <math>2x^2+\sqrt{10}x-20=0</math>. Using the quadratic formula, <math>x = \frac{\sqrt{170}-\sqrt{10}}{4}</math>, and since <math>x+y=2x+\frac{\sqrt{10}}{2}</math>, <math>x+y=\frac{\sqrt{170}}{2}</math>. Since this is the diameter, the radius of circle <math>\omega</math> is <math>\frac{\sqrt{170}}{4}</math>, and so the area of circle <math>\omega</math> is <math>\frac{170}{16}\pi = \boxed{\textbf{(C) }\frac{85}{8}\pi}</math>.<br />
<br />
-bradleyguo<br />
<br />
==See Also==<br />
{{AMC10 box|year=2019|ab=B|num-b=22|num-a=24}}<br />
{{AMC12 box|year=2019|ab=B|num-b=19|num-a=21}}<br />
{{MAA Notice}}</div>Bradleyguohttps://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_3&diff=1059822018 AIME I Problems/Problem 32019-05-27T18:10:50Z<p>Bradleyguo: </p>
<hr />
<div>==Problem==<br />
Kathy has <math>5</math> red cards and <math>5</math> green cards. She shuffles the <math>10</math> cards and lays out <math>5</math> of the cards in a row in a random order. She will be happy if and only if all the red cards laid out are adjacent and all the green cards laid out are adjacent. For example, card orders RRGGG, GGGGR, or RRRRR will make Kathy happy, but RRRGR will not. The probability that Kathy will be happy is <math> \frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m + n</math>.<br />
<br />
==Solution 1==<br />
<br />
We have <math>2+4\cdot 2</math> cases total.<br />
<br />
The two are all red and all green. Then, you have 4 of one, 1 of other. 3 of one, 2 of other. 2 of one, 3 of other. 1 of one, 4 of other. Then flip the order, so times two.<br />
<br />
Obviously the denominator is <math>10\cdot 9\cdot 8\cdot 7\cdot 6</math>, since we are choosing a card without replacement.<br />
<br />
Then, we have for the numerator for the two of all red and green: <cmath>5\cdot 4\cdot 3\cdot 2\cdot 1.</cmath><br />
<br />
For the 4 and 1, we have: <cmath>5\cdot 4\cdot 3\cdot 2\cdot 5.</cmath><br />
<br />
For the 3 and 2, we have: <cmath>5\cdot 4\cdot 3\cdot 5\cdot 4.</cmath><br />
<br />
For the 2 and 3, we have: <cmath>5\cdot 4\cdot 5\cdot 4\cdot 3.</cmath><br />
<br />
For the 1 and 4, we have: <cmath>5\cdot 5\cdot 4\cdot 3\cdot 2.</cmath><br />
<br />
Adding up and remembering to double all of them, since they can be reversed and the 5's can be red or green, we get, after simplifying: <math>\dfrac{31}{126}</math><br />
<br />
Thus the answer is <math>31 + 126 = \boxed{157}</math>.<br />
-gorefeebuddie<br />
<br />
==Solution 2==<br />
<br />
Our probability will be <math>\dfrac{\text{number of "happy" configurations of cards}}{\text{total number of configurations of cards}}.</math><br />
<br />
First of all, we have <math>10</math> choices for the first card, <math>9</math> choices for the second card, <math>8</math> choices for the third card, <math>7</math> choices for the fourth card, and <math>6</math> choices for the last card. This gives a total of <math>10\cdot 9\cdot 8\cdot 7\cdot 6</math> possible ways for five cards to be chosen.<br />
<br />
Finding the number of configurations that make Kathy happy is a more difficult task, however, and we will resort to casework to do it.<br />
<br />
First, let's look at the appearances of the "happy configurations" that Kathy likes. Based on the premise of the problem, we can realize that there are ten cases for the appearance of the configurations: <cmath>\text{RRRRR},</cmath> <cmath>\text{GGGGG},</cmath> <cmath>\text{RRRRG},</cmath> <cmath>\text{GGGGR},</cmath> <cmath>\text{RRRGG},</cmath> <cmath>\text{GGGRR},</cmath> <cmath>\text{RRGGG},</cmath> <cmath>\text{GGRRR},</cmath> <cmath>\text{RGGGG},</cmath> <cmath>\text{GRRRR}.</cmath> But this doesn't mean there are 10 "happy configurations" in total-- remember that we've been treating these cards as distinguishable, so we must continue to do so.<br />
<br />
To lighten the load of 10 cases on the human brain, we can note that in the eyes of what we will soon do, <math>RRRRR</math> and <math>GGGGG</math> are effectively equivalent, and therefore may be treated in the same case. We will have to multiply by 2 at the end, though.<br />
<br />
Similarly, we can equate <math>RRRRG,</math> <math>GGGGR,</math> <math>RGGGG,</math> and <math>GRRRR,</math> as well as <math>RRRGG,</math> <math>GGGRR,</math> <math>RRGGG,</math> and <math>GGRRR,</math> so that we just have three cases. We can approach each of these cases with constructive counting.<br />
<br />
Case 1: <math>RRRRR</math>-type.<br />
<br />
For this case, there are <math>5</math> available choices for the first card, <math>4</math> available choices for the second card, <math>3</math> for the third card, <math>2</math> for the fourth card, and <math>1</math> for the last card. This leads to a total of <math>5\cdot 4\cdot 3\cdot 2\cdot 1=120</math> configurations for this case. There are <math>2</math> cases of this type.<br />
<br />
Case 2: <math>RRRRG</math>-type.<br />
<br />
For this case, there are <math>5</math> available choices for the first card, <math>4</math> available choices for the second card, <math>3</math> for the third card, <math>2</math> for the fourth card, and <math>5</math> choices for the last card (not <math>1</math>, because we're doing a new color). This leads to a total of <math>5\cdot 4\cdot 3\cdot 2\cdot 5=600</math> configurations for this case. There are <math>4</math> cases of this type.<br />
<br />
Case 3: <math>RRRGG</math>-type.<br />
<br />
For this case, there are <math>5</math> available choices for the first card, <math>4</math> available choices for the second card, <math>3</math> for the third card, <math>5</math> for the fourth card, and <math>4</math> choices for the last card. This leads to a total of <math>5\cdot 4\cdot 3\cdot 5\cdot 4=1200</math> configurations for this case. There are <math>4</math> cases of this type.<br />
<br />
Adding the cases up gives <math>2\cdot 120+4\cdot 600+4\cdot 1200=7440</math> "happy" configurations in total.<br />
<br />
This means that the probability that Kathy is happy will be <math>\dfrac{7440}{10\cdot 9\cdot 8\cdot 7\cdot 6},</math> which simplifies to <math>\dfrac{31}{126}.</math><br />
<br />
So the answer is <math>31+126=\boxed{157}</math><br />
<br />
==Solution 3==<br />
As the problem states, some examples of valid are <math>RRGGG</math>, <math>GGGGR</math>, and <math>RRRRR</math>. Let's use each of these as more general cases. <br />
<br />
Let <math>RRGGG</math> be the case when there are 2 adjacents of one color, and 3 adjacents of the other color. This yields <math>4</math> combinations (<math>RRGGG</math>, <math>GGRRR</math>, <math>RRRGG</math>, and <math>GGGRR</math>). The probability of each of these is equal, equating to <math>\frac{5}{10}\cdot \frac{4}{9}\cdot \frac{5}{8}\cdot \frac{4}{7}\cdot \frac{3}{6}=\frac{5}{126}</math>, and since there are <math>4</math> combinations, the probability of this case is <math>4\cdot \frac{5}{126}=\frac{10}{63}</math><br />
<br />
Next case is <math>GGGGR</math>. Let this be when there are 4 adjacents of one color, and 1 individual color. Once again, this yields <math>4</math> combinations (<math>GGGGR</math>, <math>RRRRG</math>, <math>RGGGG</math>, and <math>GRRRR</math>). The probability of each is the same, equating to <math>\frac{5}{10}\cdot \frac{4}{9}\cdot \frac{3}{8}\cdot \frac{2}{7}\cdot \frac{5}{6}=\frac{5}{252}</math>, and since there are <math>4</math> combinations, the probability of this case is <math>4\cdot \frac{5}{252}=\frac{5}{63}</math><br />
<br />
The final case is <math>RRRRR</math>, in which there is just an adjacent block of <math>5</math> colors. There are only <math>2</math> combinations this time, each equating to the probability <math>\frac{5}{10}\cdot \frac{4}{9}\cdot \frac{3}{8}\cdot \frac{2}{7}\cdot \frac{1}{6}=\frac{1}{252}</math>, and since there are <math>2</math> combinations, the probability of this case is <math>2\cdot \frac{1}{252}=\frac{1}{126}</math>. <br />
<br />
Thus, the total probability is <math>\frac{10}{63}+\frac{5}{63}+\frac{1}{126}=\frac{31}{126} \implies m+n=\boxed{157}</math><br />
<br />
==Solution 4==<br />
Kathy will draw the 10 cards in some order, but the restriction of having all greens in a row and all reds in a row only applies to the first 5 cards drawn. The total number of ways the 10 cards can be drawn is simply 10 choose 5 which is 252. Now we just count the number of possible successful configurations of the ten cards. The first 5 cards can start either be <math>GRRRR</math>, <math>GGRRR</math>, <math>GGGRR</math>, <math>GGGGR</math>, <math>GGGGG</math> or the same thing except starting with a red. The number of ways to order <math>GRRRR</math> is the number of ways to order the last 5 cards, which is 5C1. Doing all of the other cases, the total is <math>(5C1+5C2+5C3+5C4+5C5)*2 = 62</math>. <math>\frac{62}{252} = \frac{31}{126}</math> <math>31 + 126 = \boxed{157}</math><br />
<br />
-bradleyguo<br />
<br />
==See Also==<br />
{{AIME box|year=2018|n=I|num-b=2|num-a=4}}<br />
{{MAA Notice}}</div>Bradleyguohttps://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_1&diff=1059812018 AIME I Problems/Problem 12019-05-27T18:09:34Z<p>Bradleyguo: </p>
<hr />
<div>==Problem 1==<br />
Let <math>S</math> be the number of ordered pairs of integers <math>(a,b)</math> with <math>1 \leq a \leq 100</math> and <math>b \geq 0</math> such that the polynomial <math>x^2+ax+b</math> can be factored into the product of two (not necessarily distinct) linear factors with integer coefficients. Find the remainder when <math>S</math> is divided by <math>1000</math>.<br />
<br />
==Solution==<br />
<br />
You let the linear factors be as <math>(x+c)(x+d)</math>.<br />
<br />
Then, obviously <math>a=c+d</math> and <math>b=cd</math>.<br />
<br />
We know that <math>1\le a\le 100</math> and <math>b\ge 0</math>, so <math>c</math> and <math>d</math> both have to be non-negative<br />
<br />
However, <math>a</math> cannot be <math>0</math>, so at least one of <math>c</math> and <math>d</math> must be greater than <math>0</math>, ie positive.<br />
<br />
Also, <math>a</math> cannot be greater than <math>100</math>, so <math>c+d</math> must be less than or equal to <math>100</math>.<br />
<br />
Essentially, if we plot the solutions, we get a triangle on the coordinate plane with vertices <math>(0,0), (0, 100),</math> and <math>(100,0)</math>. Remember that <math>(0,0)</math> does not work, so there is a square with top right corner <math>(1,1)</math>.<br />
<br />
Note that <math>c</math> and <math>d</math> are interchangeable, since they end up as <math>a</math> and <math>b</math> in the end anyways. Thus, we simply draw a line from <math>(1,1)</math> to <math>(50,50)</math>, designating one of the halves as our solution (since the other side is simply the coordinates flipped).<br />
<br />
We note that the pattern from <math>(1,1)</math> to <math>(50,50)</math> is <math>2+3+4+\dots+51</math> solutions and from <math>(51, 49)</math> to <math>(100,0)</math> is <math>50+49+48+\dots+1</math> solutions, since we can decrease the <math>y</math>-value by <math>1</math> until <math>0</math> for each coordinate.<br />
<br />
Adding up gives <cmath>\dfrac{2+51}{2}\cdot 50+\dfrac{50+1}{2}\cdot 50.</cmath><br />
This gives us <math>2600</math>, and <math>2600\equiv 600 \bmod{1000}.</math><br />
<br />
Thus, the answer is: <cmath>\boxed{600}.</cmath><br />
<br />
==Solution 2==<br />
<br />
Similar to the previous problem, we plot the triangle and cut it in half. Then, we find the number of boundary points, which is 100+51+51-3, or just 200. Using Pick's theorem, we know that the area of the half-triangle, which is 2500, is just I+100-1. That means that there are 2401 interior points, plus 200 boundary points, which is 2601. However, (0,0) does not work, so the answer is <cmath>\boxed{600}.</cmath><br />
<br />
==Solution 3 (less complicated)==<br />
Notice that for <math>x^2+ax+b</math> to be true, for every <math>a</math>, <math>b</math> will always be the product of the possibilities of how to add two integers to <math>a</math>. For example, if <math>a=3</math>, <math>b</math> will be the product of <math>(3,0)</math> and <math>(2,1)</math>, as those two sets are the only possibilities of adding two integers to <math>a</math>. Note that order does not matter. If we just do some simple casework, we find out that: <br />
<br />
if <math>a</math> is odd, there will always be <math>\left\lceil\frac{a}{2}\right\rceil</math> <math>\left(\text{which is also }\frac{a+1}{2}\right)</math> possibilities of adding two integers to <math>a</math>.<br />
<br />
if <math>a</math> is even, there will always be <math>\frac{a}{2}+1</math> possibilities of adding two integers to <math>a</math>. <br />
<br />
Using the casework, we have <math>1+2+2+3+3+...50+50+51</math> possibilities. This will mean that the answer is <cmath>\frac{(1+51)\cdot100}{2}\Rightarrow52\cdot50=2600</cmath> possibilities.<br />
<br />
Thus, our solution is <math>2600\bmod {1000}\equiv\boxed{600}</math>.<br />
<br />
Solution by IronicNinja~<br />
<br />
==Solution 4==<br />
<br />
Let's write the linear factors as <math>(x+n)(x+m)</math>.<br />
<br />
Then we can write them as: <math>a=n+m, b=nm</math>.<br />
<br />
<math>n</math> or <math>m</math> has to be a positive integer as a cannot be 0.<br />
<br />
<math>n+m</math> has to be between <math>1</math> and <math>100</math>, as a cannot be over <math>100</math>.<br />
<br />
Excluding <math>a=1</math>, we can see there is always a pair of <math>2</math> a-values for a certain amount of b-values. <br />
<br />
For instance, <math>a=2</math> and <math>a=3</math> both have <math>2</math> b-values. <math>a=4</math> and <math>a=5</math> both have <math>3</math> b-values.<br />
<br />
We notice the pattern of the number of b-values in relation to the a-values:<br />
<math>1, 2, 2, 3, 3, 4, 4…</math><br />
<br />
The following link is the URL to the graph I drew showing the relationship between a-values and b-values<br />
http://artofproblemsolving.com/wiki/index.php?title=File:Screen_Shot_2018-04-30_at_8.15.00_PM.png#file<br />
<br />
The pattern continues until <math>a=100</math>, and in total, there are <math>49</math> pairs of a-value with the same amount of b-values. The two lone a-values without a pair are, the (<math>a=1</math>, amount of b-values=1) in the beginning, and (<math>a=100</math>, amount of b-values=51) in the end. <br />
<br />
Then, we add numbers from the opposite ends of the spectrum, and quickly notice that there are <math>50</math> pairs each with a sum of <math>52</math>. <math>52\cdot50</math> gives <math>2600</math> ordered pairs:<br />
<br />
<math>1+51, 2+50, 2+50, 3+49, 3+49, 4+48, 4+48…</math><br />
<br />
When divided by <math>1000</math>, it gives the remainder <math>\boxed{600}</math>, the answer.<br />
<br />
Solution provided by- Yonglao<br />
<br />
==Solution 5==<br />
<br />
Let's say that the quadratic <math>x^2 + ax + b</math> can be factored into <math>(x+c)(x+d)</math> where <math>c</math> and <math>d</math> are non-negative numbers. We can't have both of them zero because <math>a</math> would not be within bounds. Also, <math>c+d \leq 100</math>. Assume that <math>c < d</math>. <math>d</math> can be written as <math>c + x</math> where <math>x \geq 0</math>. Therefore, <math>c + d = 2c + x \leq 100</math>. To find the amount of ordered pairs, we must consider how many values of <math>x</math> are possible for each value of <math>c</math>. The amount of possible values of <math>x</math> is given by <math>100 - 2c + 1</math>. The <math>+1</math> is the case where <math>c = d</math>. We don't include the case where <math>c = d = 0</math>, so we must subtract a case from our total. The amount of ordered pairs of <math>(a,b)</math> is:<br />
<cmath>\left(\sum_{c=0}^{50} (100 - 2c + 1)\right) - 1</cmath><br />
This is an arithmetic progression. <cmath>\frac{(101 + 1)(51)}{2} - 1 = 2601 - 1 = 2600</cmath> <br />
When divided by <math>1000</math>, it gives the remainder <math>\boxed{600}</math><br />
<br />
~Zeric Hang<br />
<br />
==Solution 6(simple)==<br />
By vietas, the sum of the roots is -a and the product is b. Therefore both roots are negative. For each value of a from 1 to 100, the number of b values is the number of ways to sum two numbers between 0 and a-1 inclusive to a. This is just <math>1 + 2 + 2 + 3 + 3 +... 50 + 50 + 51 = 2600</math>. So the answer is <math>\boxed{600}</math><br />
<br />
-bradleyguo<br />
<br />
==See Also==<br />
{{AIME box|year=2018|n=I|before=First Problem|num-a=2}}<br />
{{MAA Notice}}</div>Bradleyguohttps://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_3&diff=1059802018 AIME I Problems/Problem 32019-05-27T17:56:44Z<p>Bradleyguo: </p>
<hr />
<div>==Problem==<br />
Kathy has <math>5</math> red cards and <math>5</math> green cards. She shuffles the <math>10</math> cards and lays out <math>5</math> of the cards in a row in a random order. She will be happy if and only if all the red cards laid out are adjacent and all the green cards laid out are adjacent. For example, card orders RRGGG, GGGGR, or RRRRR will make Kathy happy, but RRRGR will not. The probability that Kathy will be happy is <math> \frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m + n</math>.<br />
<br />
==Solution 1==<br />
<br />
We have <math>2+4\cdot 2</math> cases total.<br />
<br />
The two are all red and all green. Then, you have 4 of one, 1 of other. 3 of one, 2 of other. 2 of one, 3 of other. 1 of one, 4 of other. Then flip the order, so times two.<br />
<br />
Obviously the denominator is <math>10\cdot 9\cdot 8\cdot 7\cdot 6</math>, since we are choosing a card without replacement.<br />
<br />
Then, we have for the numerator for the two of all red and green: <cmath>5\cdot 4\cdot 3\cdot 2\cdot 1.</cmath><br />
<br />
For the 4 and 1, we have: <cmath>5\cdot 4\cdot 3\cdot 2\cdot 5.</cmath><br />
<br />
For the 3 and 2, we have: <cmath>5\cdot 4\cdot 3\cdot 5\cdot 4.</cmath><br />
<br />
For the 2 and 3, we have: <cmath>5\cdot 4\cdot 5\cdot 4\cdot 3.</cmath><br />
<br />
For the 1 and 4, we have: <cmath>5\cdot 5\cdot 4\cdot 3\cdot 2.</cmath><br />
<br />
Adding up and remembering to double all of them, since they can be reversed and the 5's can be red or green, we get, after simplifying: <math>\dfrac{31}{126}</math><br />
<br />
Thus the answer is <math>31 + 126 = \boxed{157}</math>.<br />
-gorefeebuddie<br />
<br />
==Solution 2==<br />
<br />
Our probability will be <math>\dfrac{\text{number of "happy" configurations of cards}}{\text{total number of configurations of cards}}.</math><br />
<br />
First of all, we have <math>10</math> choices for the first card, <math>9</math> choices for the second card, <math>8</math> choices for the third card, <math>7</math> choices for the fourth card, and <math>6</math> choices for the last card. This gives a total of <math>10\cdot 9\cdot 8\cdot 7\cdot 6</math> possible ways for five cards to be chosen.<br />
<br />
Finding the number of configurations that make Kathy happy is a more difficult task, however, and we will resort to casework to do it.<br />
<br />
First, let's look at the appearances of the "happy configurations" that Kathy likes. Based on the premise of the problem, we can realize that there are ten cases for the appearance of the configurations: <cmath>\text{RRRRR},</cmath> <cmath>\text{GGGGG},</cmath> <cmath>\text{RRRRG},</cmath> <cmath>\text{GGGGR},</cmath> <cmath>\text{RRRGG},</cmath> <cmath>\text{GGGRR},</cmath> <cmath>\text{RRGGG},</cmath> <cmath>\text{GGRRR},</cmath> <cmath>\text{RGGGG},</cmath> <cmath>\text{GRRRR}.</cmath> But this doesn't mean there are 10 "happy configurations" in total-- remember that we've been treating these cards as distinguishable, so we must continue to do so.<br />
<br />
To lighten the load of 10 cases on the human brain, we can note that in the eyes of what we will soon do, <math>RRRRR</math> and <math>GGGGG</math> are effectively equivalent, and therefore may be treated in the same case. We will have to multiply by 2 at the end, though.<br />
<br />
Similarly, we can equate <math>RRRRG,</math> <math>GGGGR,</math> <math>RGGGG,</math> and <math>GRRRR,</math> as well as <math>RRRGG,</math> <math>GGGRR,</math> <math>RRGGG,</math> and <math>GGRRR,</math> so that we just have three cases. We can approach each of these cases with constructive counting.<br />
<br />
Case 1: <math>RRRRR</math>-type.<br />
<br />
For this case, there are <math>5</math> available choices for the first card, <math>4</math> available choices for the second card, <math>3</math> for the third card, <math>2</math> for the fourth card, and <math>1</math> for the last card. This leads to a total of <math>5\cdot 4\cdot 3\cdot 2\cdot 1=120</math> configurations for this case. There are <math>2</math> cases of this type.<br />
<br />
Case 2: <math>RRRRG</math>-type.<br />
<br />
For this case, there are <math>5</math> available choices for the first card, <math>4</math> available choices for the second card, <math>3</math> for the third card, <math>2</math> for the fourth card, and <math>5</math> choices for the last card (not <math>1</math>, because we're doing a new color). This leads to a total of <math>5\cdot 4\cdot 3\cdot 2\cdot 5=600</math> configurations for this case. There are <math>4</math> cases of this type.<br />
<br />
Case 3: <math>RRRGG</math>-type.<br />
<br />
For this case, there are <math>5</math> available choices for the first card, <math>4</math> available choices for the second card, <math>3</math> for the third card, <math>5</math> for the fourth card, and <math>4</math> choices for the last card. This leads to a total of <math>5\cdot 4\cdot 3\cdot 5\cdot 4=1200</math> configurations for this case. There are <math>4</math> cases of this type.<br />
<br />
Adding the cases up gives <math>2\cdot 120+4\cdot 600+4\cdot 1200=7440</math> "happy" configurations in total.<br />
<br />
This means that the probability that Kathy is happy will be <math>\dfrac{7440}{10\cdot 9\cdot 8\cdot 7\cdot 6},</math> which simplifies to <math>\dfrac{31}{126}.</math><br />
<br />
So the answer is <math>31+126=\boxed{157}</math><br />
<br />
==Solution 3==<br />
As the problem states, some examples of valid are <math>RRGGG</math>, <math>GGGGR</math>, and <math>RRRRR</math>. Let's use each of these as more general cases. <br />
<br />
Let <math>RRGGG</math> be the case when there are 2 adjacents of one color, and 3 adjacents of the other color. This yields <math>4</math> combinations (<math>RRGGG</math>, <math>GGRRR</math>, <math>RRRGG</math>, and <math>GGGRR</math>). The probability of each of these is equal, equating to <math>\frac{5}{10}\cdot \frac{4}{9}\cdot \frac{5}{8}\cdot \frac{4}{7}\cdot \frac{3}{6}=\frac{5}{126}</math>, and since there are <math>4</math> combinations, the probability of this case is <math>4\cdot \frac{5}{126}=\frac{10}{63}</math><br />
<br />
Next case is <math>GGGGR</math>. Let this be when there are 4 adjacents of one color, and 1 individual color. Once again, this yields <math>4</math> combinations (<math>GGGGR</math>, <math>RRRRG</math>, <math>RGGGG</math>, and <math>GRRRR</math>). The probability of each is the same, equating to <math>\frac{5}{10}\cdot \frac{4}{9}\cdot \frac{3}{8}\cdot \frac{2}{7}\cdot \frac{5}{6}=\frac{5}{252}</math>, and since there are <math>4</math> combinations, the probability of this case is <math>4\cdot \frac{5}{252}=\frac{5}{63}</math><br />
<br />
The final case is <math>RRRRR</math>, in which there is just an adjacent block of <math>5</math> colors. There are only <math>2</math> combinations this time, each equating to the probability <math>\frac{5}{10}\cdot \frac{4}{9}\cdot \frac{3}{8}\cdot \frac{2}{7}\cdot \frac{1}{6}=\frac{1}{252}</math>, and since there are <math>2</math> combinations, the probability of this case is <math>2\cdot \frac{1}{252}=\frac{1}{126}</math>. <br />
<br />
Thus, the total probability is <math>\frac{10}{63}+\frac{5}{63}+\frac{1}{126}=\frac{31}{126} \implies m+n=\boxed{157}</math><br />
<br />
==Solution 4==<br />
Kathy will draw the 10 cards in some order, but the restriction of having all greens in a row and all reds in a row only applies to the first 5 cards drawn. The total number of ways the 10 cards can be drawn is simply 10 choose 5 which is 252. Now we just count the number of possible successful configurations of the ten cards. The first 5 cards can start either be <math>GRRRR</math>, <math>GGRRR</math>, <math>GGGRR</math>, <math>GGGGR</math>, <math>GGGGG</math> or the same thing except starting with a red. The number of ways to order <math>GRRRR</math> is the number of ways to order the last 5 cards, which is 5C1. Doing all of the other cases, the total is <math>(5C1+5C2+5C3+5C4+5C5)*2 = 62</math>. <math>\frac{62}{252} = \frac{31}{126}</math> <math>31 + 126 = \boxed{157}</math><br />
<br />
==See Also==<br />
{{AIME box|year=2018|n=I|num-b=2|num-a=4}}<br />
{{MAA Notice}}</div>Bradleyguohttps://artofproblemsolving.com/wiki/index.php?title=2019_AIME_II_Problems/Problem_2&diff=1059542019 AIME II Problems/Problem 22019-05-26T03:30:33Z<p>Bradleyguo: /* Solution 4 */</p>
<hr />
<div>==Problem 2==<br />
<br />
Lily pads <math>1,2,3,\ldots</math> lie in a row on a pond. A frog makes a sequence of jumps starting on pad <math>1</math>. From any pad <math>k</math> the frog jumps to either pad <math>k+1</math> or pad <math>k+2</math> chosen randomly with probability <math>\tfrac{1}{2}</math> and independently of other jumps. The probability that the frog visits pad <math>7</math> is <math>\tfrac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.<br />
<br />
==Solution==<br />
Let <math>P_n</math> be the probability the frog visits pad <math>7</math> starting from pad <math>n</math>. Then <math>P_7 = 1</math>, <math>P_6 = \frac12</math>, and <math>P_n = \frac12(P_{n + 1} + P_{n + 2})</math> for all integers <math>1 \leq n \leq 5</math>. Working our way down, we find<br />
<cmath>P_5 = \frac{3}{4}</cmath><br />
<cmath>P_4 = \frac{5}{8}</cmath><br />
<cmath>P_3 = \frac{11}{16}</cmath><br />
<cmath>P_2 = \frac{21}{32}</cmath><br />
<cmath>P_1 = \frac{43}{64}</cmath><br />
<math>43 + 64 = \boxed{107}</math>.<br />
<br />
==Solution 2(Casework)==<br />
Define a one jump to be a jump from k to K + 1 and a two jump to be a jump from k to k + 2. <br />
<br />
Case 1: (6 one jumps) (1/2)^6 = 1/64<br />
<br />
Case 2: (4 one jumps and 1 two jumps) 5C1 x (1/2)^5 = 5/32<br />
<br />
Case 3: (2 one jumps and 2 two jumps) 4C2 x (1/2)^4 = 3/8<br />
<br />
Case 4: (3 two jumps) (1/2)^3 = 1/8<br />
<br />
Summing the probabilities gives us 43/64 so the answer is 107. <br />
<br />
- pi_is_3.14<br />
<br />
==Solution 3 (easiest)==<br />
Let <math>P_n</math> be the probability that the frog lands on lily pad <math>n</math>. The probability that the frog never lands on pad <math>n</math> is <math>\frac{1}{2}P_{n-1}</math>, so <math>1-P_n=\frac{1}{2}P_{n-1}</math>. This rearranges to <math>P_n=1-\frac{1}{2}P_{n-1}</math>, and we know that <math>P_1=1</math>, so we can compute <math>P_7</math> to be <math>\frac{43}{64}</math>, meaning that our answer is <math>\boxed{107}</math><br />
<br />
-Stormersyle<br />
<br />
==Solution 4==<br />
For any point <math>n</math>, let the probability that the frog lands on lily pad <math>n</math> be <math>P_n</math>. The frog can land at lily pad <math>n</math> with either a double jump from lily pad <math>n-2</math> or a single jump from lily pad <math>n-1</math>. Since the probability when the frog is at <math>n-2</math> to make a double jump is <math>\frac{1}{2}</math> and same for when it's at <math>n-1</math>, the recursion is just <math>P_n = \frac{P_{n-2}+P_{n-1}}{2}</math>. Using the fact that <math>P_1 = 1</math>, and <math>P_2 = \frac{1}{2}</math>, we find that <math>P_7 = \frac{43}{64}</math>. <math>43 + 63 = \boxed{107}</math><br />
<br />
-bradleyguo<br />
<br />
==See Also==<br />
{{AIME box|year=2019|n=II|num-b=1|num-a=3}}<br />
{{MAA Notice}}</div>Bradleyguohttps://artofproblemsolving.com/wiki/index.php?title=2019_AIME_II_Problems/Problem_2&diff=1059472019 AIME II Problems/Problem 22019-05-25T20:39:30Z<p>Bradleyguo: </p>
<hr />
<div>==Problem 2==<br />
<br />
Lily pads <math>1,2,3,\ldots</math> lie in a row on a pond. A frog makes a sequence of jumps starting on pad <math>1</math>. From any pad <math>k</math> the frog jumps to either pad <math>k+1</math> or pad <math>k+2</math> chosen randomly with probability <math>\tfrac{1}{2}</math> and independently of other jumps. The probability that the frog visits pad <math>7</math> is <math>\tfrac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.<br />
<br />
==Solution==<br />
Let <math>P_n</math> be the probability the frog visits pad <math>7</math> starting from pad <math>n</math>. Then <math>P_7 = 1</math>, <math>P_6 = \frac12</math>, and <math>P_n = \frac12(P_{n + 1} + P_{n + 2})</math> for all integers <math>1 \leq n \leq 5</math>. Working our way down, we find<br />
<cmath>P_5 = \frac{3}{4}</cmath><br />
<cmath>P_4 = \frac{5}{8}</cmath><br />
<cmath>P_3 = \frac{11}{16}</cmath><br />
<cmath>P_2 = \frac{21}{32}</cmath><br />
<cmath>P_1 = \frac{43}{64}</cmath><br />
<math>43 + 64 = \boxed{107}</math>.<br />
<br />
==Solution 2(Casework)==<br />
Define a one jump to be a jump from k to K + 1 and a two jump to be a jump from k to k + 2. <br />
<br />
Case 1: (6 one jumps) (1/2)^6 = 1/64<br />
<br />
Case 2: (4 one jumps and 1 two jumps) 5C1 x (1/2)^5 = 5/32<br />
<br />
Case 3: (2 one jumps and 2 two jumps) 4C2 x (1/2)^4 = 3/8<br />
<br />
Case 4: (3 two jumps) (1/2)^3 = 1/8<br />
<br />
Summing the probabilities gives us 43/64 so the answer is 107. <br />
<br />
- pi_is_3.14<br />
<br />
==Solution 3 (easiest)==<br />
Let <math>P_n</math> be the probability that the frog lands on lily pad <math>n</math>. The probability that the frog never lands on pad <math>n</math> is <math>\frac{1}{2}P_{n-1}</math>, so <math>1-P_n=\frac{1}{2}P_{n-1}</math>. This rearranges to <math>P_n=1-\frac{1}{2}P_{n-1}</math>, and we know that <math>P_1=1</math>, so we can compute <math>P_7</math> to be <math>\frac{43}{64}</math>, meaning that our answer is <math>\boxed{107}</math><br />
<br />
-Stormersyle<br />
<br />
==Solution 4==<br />
For any point <math>n</math>, let the probability that the frog lands on lily pad <math>n</math> be <math>P_n</math>. If the frog is at lily pad <math>n-2</math>, it can either double jump with probability <math>\frac{1}{2}</math> or single jump twice with probability <math>\frac{1}{4}</math> to get to lily pad <math>n</math>. Now consider if the frog is at lily pad <math>n-3</math>. It has a probability of landing on lily pad <math>n</math> without landing on lily pad <math>n-2</math> with probability <math>\frac{1}{4}</math>, double jump then single jump. Therefore the recursion is <math>P_n = \frac{3}{4}P_{n-2} + \frac{1}{4}P_{n-3}</math>. Note that all instances of the frog landing on lily pad <math>n-1</math> has been covered. After calculating a few values of <math>P_n</math> using the fact that <math>P_1 = 1</math>, <math>P_2 = \frac{1}{2}</math>, and <math>P_3 = \frac{3}{4}P_1 = \frac{3}{4}</math> we find that <math>P_7 = \frac{43}{64}</math>. <math>43 + 63 = \boxed{107}</math><br />
<br />
-bradleyguo<br />
<br />
==See Also==<br />
{{AIME box|year=2019|n=II|num-b=1|num-a=3}}<br />
{{MAA Notice}}</div>Bradleyguohttps://artofproblemsolving.com/wiki/index.php?title=2019_AIME_II_Problems/Problem_2&diff=1059462019 AIME II Problems/Problem 22019-05-25T20:38:03Z<p>Bradleyguo: </p>
<hr />
<div>==Problem 2==<br />
<br />
Lily pads <math>1,2,3,\ldots</math> lie in a row on a pond. A frog makes a sequence of jumps starting on pad <math>1</math>. From any pad <math>k</math> the frog jumps to either pad <math>k+1</math> or pad <math>k+2</math> chosen randomly with probability <math>\tfrac{1}{2}</math> and independently of other jumps. The probability that the frog visits pad <math>7</math> is <math>\tfrac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.<br />
<br />
==Solution==<br />
Let <math>P_n</math> be the probability the frog visits pad <math>7</math> starting from pad <math>n</math>. Then <math>P_7 = 1</math>, <math>P_6 = \frac12</math>, and <math>P_n = \frac12(P_{n + 1} + P_{n + 2})</math> for all integers <math>1 \leq n \leq 5</math>. Working our way down, we find<br />
<cmath>P_5 = \frac{3}{4}</cmath><br />
<cmath>P_4 = \frac{5}{8}</cmath><br />
<cmath>P_3 = \frac{11}{16}</cmath><br />
<cmath>P_2 = \frac{21}{32}</cmath><br />
<cmath>P_1 = \frac{43}{64}</cmath><br />
<math>43 + 64 = \boxed{107}</math>.<br />
<br />
==Solution 2(Casework)==<br />
Define a one jump to be a jump from k to K + 1 and a two jump to be a jump from k to k + 2. <br />
<br />
Case 1: (6 one jumps) (1/2)^6 = 1/64<br />
<br />
Case 2: (4 one jumps and 1 two jumps) 5C1 x (1/2)^5 = 5/32<br />
<br />
Case 3: (2 one jumps and 2 two jumps) 4C2 x (1/2)^4 = 3/8<br />
<br />
Case 4: (3 two jumps) (1/2)^3 = 1/8<br />
<br />
Summing the probabilities gives us 43/64 so the answer is 107. <br />
<br />
- pi_is_3.14<br />
<br />
==Solution 3 (easiest)==<br />
Let <math>P_n</math> be the probability that the frog lands on lily pad <math>n</math>. The probability that the frog never lands on pad <math>n</math> is <math>\frac{1}{2}P_{n-1}</math>, so <math>1-P_n=\frac{1}{2}P_{n-1}</math>. This rearranges to <math>P_n=1-\frac{1}{2}P_{n-1}</math>, and we know that <math>P_1=1</math>, so we can compute <math>P_7</math> to be <math>\frac{43}{64}</math>, meaning that our answer is <math>\boxed{107}</math><br />
<br />
-Stormersyle<br />
<br />
==Solution 4==<br />
For any point <math>n</math>, let the probability that the frog lands on lily pad <math>n</math> be <math>P_n</math>. If the frog is at lily pad <math>n-2</math>, it can either double jump with probability <math>\frac{1}{2}</math> or single jump twice with probability <math>\frac{1}{4}</math> to get to lily pad <math>n</math>. Now consider if the frog is at lily pad <math>n-3</math>. It has a probability of landing on lily pad <math>n</math> without landing on lily pad <math>n-2</math> with probability <math>\frac{1}{4}</math>, double jump then single jump. Therefore the recursion is <math>P_n = \frac{3}{4}P_{n-2} + \frac{1}{4}P_{n-3}</math>. Note that all instances of the frog landing on lily pad <math>n-1</math> has been covered. After calculating a few values of <math>P_n</math> using the fact that <math>P_1 = 1</math>, <math>P_2 = \frac{1}{2}</math>, and <math>P_3 = \frac{3}{4}P_1 = \frac{3}{4}</math> we find that <math>P_7 = \frac{43}{64}</math>. <math>43 + 63 = \boxed{107}</math><br />
-bradleyguo<br />
<br />
==See Also==<br />
{{AIME box|year=2019|n=II|num-b=1|num-a=3}}<br />
{{MAA Notice}}</div>Bradleyguo