https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=FINNN&feedformat=atom AoPS Wiki - User contributions [en] 2021-11-30T20:47:50Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2019_AIME_II_Problems/Problem_3&diff=106872 2019 AIME II Problems/Problem 3 2019-06-23T20:29:45Z <p>FINNN: /* Solution */</p> <hr /> <div>==Problem 3==<br /> Find the number of &lt;math&gt;7&lt;/math&gt;-tuples of positive integers &lt;math&gt;(a,b,c,d,e,f,g)&lt;/math&gt; that satisfy the following systems of equations:<br /> &lt;cmath&gt;\begin{align*}<br /> abc&amp;=70,\\<br /> cde&amp;=71,\\<br /> efg&amp;=72.<br /> \end{align*}&lt;/cmath&gt;<br /> <br /> ==Solution==<br /> As 71 is prime, &lt;math&gt;c&lt;/math&gt;, &lt;math&gt;d&lt;/math&gt;, and &lt;math&gt;e&lt;/math&gt; must be 1, 1, and 71 (in some order). However, since &lt;math&gt;c&lt;/math&gt; and &lt;math&gt;e&lt;/math&gt; are divisors of 70 and 72 respectively, the only possibility is &lt;math&gt;(c,d,e) = (1,71,1)&lt;/math&gt;. Now we are left with finding the number of solutions &lt;math&gt;(a,b,f,g)&lt;/math&gt; satisfying &lt;math&gt;ab = 70&lt;/math&gt; and &lt;math&gt;fg = 72&lt;/math&gt;, which separates easily into two subproblems. The number of positive integer solutions to &lt;math&gt;ab = 70&lt;/math&gt; simply equals the number of divisors of 70 (as we can choose a divisor for &lt;math&gt;a&lt;/math&gt;, which uniquely determines &lt;math&gt;b&lt;/math&gt;). As &lt;math&gt;70 = 2^1 \cdot 5^1 \cdot 7^1&lt;/math&gt;, we have &lt;math&gt;d(70) = (1+1)(1+1)(1+1) = 8&lt;/math&gt; solutions. Similarly, &lt;math&gt;72 = 2^3 \cdot 3^2&lt;/math&gt;, so &lt;math&gt;d(72) = 4 \times 3 = 12&lt;/math&gt;.<br /> <br /> Then the answer is simply &lt;math&gt;8 \times 12 = \boxed{096}&lt;/math&gt;.<br /> <br /> -scrabbler94<br /> <br /> ==See Also==<br /> {{AIME box|year=2019|n=II|num-b=2|num-a=4}}<br /> {{MAA Notice}}</div> FINNN https://artofproblemsolving.com/wiki/index.php?title=2001_AMC_12_Problems/Problem_24&diff=99029 2001 AMC 12 Problems/Problem 24 2018-11-24T19:06:24Z <p>FINNN: /* Solution 2 */</p> <hr /> <div>== Problem ==<br /> <br /> In &lt;math&gt;\triangle ABC&lt;/math&gt;, &lt;math&gt;\angle ABC=45^\circ&lt;/math&gt;. Point &lt;math&gt;D&lt;/math&gt; is on &lt;math&gt;\overline{BC}&lt;/math&gt; so that &lt;math&gt;2\cdot BD=CD&lt;/math&gt; and &lt;math&gt;\angle DAB=15^\circ&lt;/math&gt;. Find &lt;math&gt;\angle ACB&lt;/math&gt;.<br /> <br /> &lt;math&gt;<br /> \text{(A) }54^\circ<br /> \qquad<br /> \text{(B) }60^\circ<br /> \qquad<br /> \text{(C) }72^\circ<br /> \qquad<br /> \text{(D) }75^\circ<br /> \qquad<br /> \text{(E) }90^\circ<br /> &lt;/math&gt;<br /> <br /> == Solution 1 ==<br /> <br /> &lt;asy&gt;<br /> unitsize(2cm);<br /> defaultpen(0.8);<br /> pair A=(0,0), B=(4,0), D=intersectionpoint( A -- (dir(15)*100), B -- (B+100*dir(135)) ), C=B+3*(D-B);<br /> pair ortho=rotate(-90)*(D-A);<br /> pair E=extension(C, ortho, A, B);<br /> draw(A--B);<br /> draw(B--C);<br /> draw(A--C);<br /> draw(C--E);<br /> draw(E--D);<br /> draw(A--D);<br /> <br /> \<br /> label(&quot;$A$&quot;,A,SW);<br /> label(&quot;$B$&quot;,B,SE);<br /> label(&quot;$C$&quot;,C,N);<br /> label(&quot;$D$&quot;,D,NE);<br /> label(&quot;$E$&quot;,E,S);<br /> &lt;/asy&gt;<br /> <br /> We start with the observation that &lt;math&gt;\angle ADB = 180^\circ - 15^\circ - 45^\circ = 120^\circ&lt;/math&gt;, and &lt;math&gt;\angle ADC = 15^\circ + 45^\circ = 60^\circ&lt;/math&gt;.<br /> <br /> We can draw the height &lt;math&gt;CE&lt;/math&gt; from &lt;math&gt;C&lt;/math&gt; onto &lt;math&gt;AD&lt;/math&gt;. In the triangle &lt;math&gt;CED&lt;/math&gt;, we have &lt;math&gt;\frac {ED}{CD} = \cos EDC = \cos 60^\circ = \frac 12&lt;/math&gt;. Hence &lt;math&gt;ED = CD/2&lt;/math&gt;.<br /> <br /> By the definition of &lt;math&gt;D&lt;/math&gt;, we also have &lt;math&gt;BD=CD/2&lt;/math&gt;, therefore &lt;math&gt;BD=DE&lt;/math&gt;. This means that the triangle &lt;math&gt;BDE&lt;/math&gt; is isosceles, and as &lt;math&gt;\angle BDE=120^\circ&lt;/math&gt;, we must have &lt;math&gt;\angle BED = \angle EBD = 30^\circ&lt;/math&gt;. <br /> <br /> Then we compute &lt;math&gt;\angle ABE = 45^\circ - 30^\circ = 15^\circ&lt;/math&gt;, thus &lt;math&gt;\angle ABE = \angle BAE&lt;/math&gt; and the triangle &lt;math&gt;ABE&lt;/math&gt; is isosceles as well. Hence &lt;math&gt;AE=BE&lt;/math&gt;.<br /> <br /> Now we can note that &lt;math&gt;\angle DCE = 180^\circ - 90^\circ - 60^\circ = 30^\circ&lt;/math&gt;, hence also the triangle &lt;math&gt;EBC&lt;/math&gt; is isosceles and we have &lt;math&gt;BE=CE&lt;/math&gt;.<br /> <br /> Combining the previous two observations we get that &lt;math&gt;AE=EC&lt;/math&gt;, and as &lt;math&gt;\angle AEC=90^\circ&lt;/math&gt;, this means that &lt;math&gt;\angle CAE = \angle ACE = 45^\circ&lt;/math&gt;.<br /> <br /> Finally, we get &lt;math&gt;\angle ACB = \angle ACE + \angle ECD = 45^\circ + 30^\circ = \boxed{75^\circ}&lt;/math&gt;.<br /> <br /> == Solution 2 ==<br /> <br /> Draw a good diagram! Now, let's call &lt;math&gt;BD=t&lt;/math&gt;, so &lt;math&gt;DC=2t&lt;/math&gt;. Given the rather nice angles of &lt;math&gt;\angle ABD = 45^\circ&lt;/math&gt; and &lt;math&gt;\angle ADC = 60^\circ&lt;/math&gt; as you can see, let's do trig. Drop an altitude from &lt;math&gt;A&lt;/math&gt; to &lt;math&gt;BC&lt;/math&gt;; call this point &lt;math&gt;H&lt;/math&gt;. We realize that there is no specific factor of &lt;math&gt;t&lt;/math&gt; we can call this just yet, so let &lt;math&gt;AH=kt&lt;/math&gt;. Notice that in &lt;math&gt;\triangle{ABH}&lt;/math&gt; we get &lt;math&gt;BH=kt&lt;/math&gt;. Using the 60-degree angle in &lt;math&gt;\triangle{ADH}&lt;/math&gt;, we obtain &lt;math&gt;DH=\frac{\sqrt{3}}{3}kt&lt;/math&gt;. The comparable ratio is that &lt;math&gt;BH-DH=t&lt;/math&gt;. If we involve our &lt;math&gt;k&lt;/math&gt;, we get:<br /> <br /> &lt;math&gt;kt(\frac{3}{3}-\frac{\sqrt{3}}{3})=t&lt;/math&gt;. Eliminating &lt;math&gt;t&lt;/math&gt; and removing radicals from the denominator, we get &lt;math&gt;k=\frac{3+\sqrt{3}}{2}&lt;/math&gt;. From there, one can easily obtain &lt;math&gt;HC=3t-kt=\frac{3-\sqrt{3}}{2}t&lt;/math&gt;. Now we finally have a desired ratio. Since &lt;math&gt;\tan\angle ACH = 2+\sqrt{3}&lt;/math&gt; upon calculation, we know that &lt;math&gt;\angle ACH&lt;/math&gt; can be simplified. Indeed, if you know that &lt;math&gt;\tan(75)=2+\sqrt{3}&lt;/math&gt; or even take a minute or two to work out the sine and cosine using &lt;math&gt;\sin(x)^2+\cos(x)^2=1&lt;/math&gt;, and perhaps the half- or double-angle formulas, you get &lt;math&gt;\boxed{75^\circ}&lt;/math&gt;.<br /> <br /> == Solution 3==<br /> WLOG, we can assume that &lt;math&gt;BD = 1&lt;/math&gt; and &lt;math&gt;CD = 2&lt;/math&gt;. As above, we are able to find that &lt;math&gt;\angle ADB = 60^\circ&lt;/math&gt; and &lt;math&gt;\angle ADC = 120^\circ&lt;/math&gt;.<br /> <br /> Using Law of Sines on triangle &lt;math&gt;ADB&lt;/math&gt;, we find that &lt;math&gt;\frac{1}{\sin15^\circ} = \frac{AD}{\sin 45^\circ} = \frac{AB}{\sin 120^\circ}&lt;/math&gt;. Since we know that &lt;math&gt;\sin 15^\circ = \frac{\sqrt{6}-\sqrt{2}}{4}&lt;/math&gt;, &lt;math&gt;\sin 45^\circ = \frac{\sqrt{2}}{2}&lt;/math&gt;, and &lt;math&gt;\sin 120^\circ = \frac{\sqrt{3}}{2}&lt;/math&gt;, we can compute &lt;math&gt;AD&lt;/math&gt; to equal &lt;math&gt;1+\sqrt{3}&lt;/math&gt; and &lt;math&gt;AB&lt;/math&gt; to be &lt;math&gt;\frac{3\sqrt{2}+\sqrt{6}}{2}&lt;/math&gt;.<br /> <br /> Next, we apply Law of Cosines to triangle &lt;math&gt;ADC&lt;/math&gt; to see that &lt;math&gt;AC^2 = (1+\sqrt{3})^2 + 2^2 - (2)(1+\sqrt{3})(2)(\cos 60^\circ)&lt;/math&gt;. Simplifying the RHS, we get &lt;math&gt;AC^2 = 6&lt;/math&gt;, so &lt;math&gt;AC = \sqrt{6}&lt;/math&gt;.<br /> <br /> Now, we apply Law of Sines to triangle &lt;math&gt;ABC&lt;/math&gt; to see that &lt;math&gt;\frac{\sqrt{6}}{\sin 45^\circ} = \frac{\frac{3\sqrt{2}+\sqrt{6}}{2}}{\sin ACB}&lt;/math&gt;. After rearranging and noting that &lt;math&gt;\sin 45^\circ = \frac{\sqrt{2}}{2}&lt;/math&gt;, we get &lt;math&gt;\sin ACB = \frac{\sqrt{6}+3\sqrt{2}}{4\sqrt{3}}&lt;/math&gt;.<br /> <br /> Dividing the RHS through by &lt;math&gt;\sqrt{3}&lt;/math&gt;, we see that &lt;math&gt;\sin ACB = \frac{\sqrt{6}+\sqrt{2}}{4}&lt;/math&gt;, so &lt;math&gt;\angle ACB&lt;/math&gt; is either &lt;math&gt;75^\circ&lt;/math&gt; or &lt;math&gt;105^\circ&lt;/math&gt;. Since &lt;math&gt;105^\circ&lt;/math&gt; is not a choice, we know &lt;math&gt;\angle ACB = \boxed{75^\circ}&lt;/math&gt;.<br /> <br /> Note that we can also confirm that &lt;math&gt;\angle ACB \neq 105^\circ&lt;/math&gt; by computing &lt;math&gt;\angle CAB&lt;/math&gt; with Law of Sines.<br /> <br /> == See Also ==<br /> <br /> {{AMC12 box|year=2001|num-b=23|num-a=25}}<br /> {{MAA Notice}}</div> FINNN https://artofproblemsolving.com/wiki/index.php?title=2018_AMC_12A_Problems/Problem_9&diff=90790 2018 AMC 12A Problems/Problem 9 2018-02-09T17:56:26Z <p>FINNN: /* Solution 2 */</p> <hr /> <div>== Problem ==<br /> <br /> Which of the following describes the largest subset of values of &lt;math&gt;y&lt;/math&gt; within the closed interval &lt;math&gt;[0,\pi]&lt;/math&gt; for which<br /> &lt;cmath&gt;\sin(x+y)\leq \sin(x)+\sin(y)&lt;/cmath&gt;for every &lt;math&gt;x&lt;/math&gt; between &lt;math&gt;0&lt;/math&gt; and &lt;math&gt;\pi&lt;/math&gt;, inclusive?<br /> &lt;cmath&gt;\textbf{(A) } y=0 \qquad \textbf{(B) } 0\leq y\leq \frac{\pi}{4} \qquad \textbf{(C) } 0\leq y\leq \frac{\pi}{2} \qquad \textbf{(D) } 0\leq y\leq \frac{3\pi}{4} \qquad \textbf{(E) } 0\leq y\leq \pi &lt;/cmath&gt;<br /> <br /> == Solution 1 ==<br /> On the interval &lt;math&gt;[0, \pi]&lt;/math&gt; sine is nonnegative; thus &lt;math&gt;\sin(x + y) = \sin x \cos y + \sin y \cos x \le \sin x + \sin y&lt;/math&gt; for all &lt;math&gt;x, y \in [0, \pi]&lt;/math&gt;. The answer is &lt;math&gt;\boxed{\textbf{(E) } 0\le y\le \pi}&lt;/math&gt;. (CantonMathGuy)<br /> <br /> ==Solution 2==<br /> Expanding, &lt;cmath&gt;\cos y \sin x + \cos x \sin y \le \sin x + \sin y&lt;/cmath&gt; Let &lt;math&gt;\sin x =a \ge 0&lt;/math&gt;, &lt;math&gt;\sin y = b \ge 0&lt;/math&gt;. We have that &lt;cmath&gt;(\cos y)a+(\cos x)b \le a+b&lt;/cmath&gt; Comparing coefficients of &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; gives a clear solution: both &lt;math&gt;\cos y&lt;/math&gt; and &lt;math&gt;\cos x&lt;/math&gt; are less than or equal to one, so the coefficients of &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; on the left are less than on the right. Since &lt;math&gt;a, b \ge 0&lt;/math&gt;, that means that this equality is always satisfied over this interval, or &lt;math&gt;\boxed{\textbf{(E) } 0\le y\le \pi}&lt;/math&gt;.<br /> <br /> ==See Also==<br /> {{AMC12 box|year=2018|ab=A|num-b=8|num-a=10}}<br /> {{MAA Notice}}</div> FINNN https://artofproblemsolving.com/wiki/index.php?title=2018_AMC_12A_Problems/Problem_9&diff=90789 2018 AMC 12A Problems/Problem 9 2018-02-09T17:55:55Z <p>FINNN: /* Solution */</p> <hr /> <div>== Problem ==<br /> <br /> Which of the following describes the largest subset of values of &lt;math&gt;y&lt;/math&gt; within the closed interval &lt;math&gt;[0,\pi]&lt;/math&gt; for which<br /> &lt;cmath&gt;\sin(x+y)\leq \sin(x)+\sin(y)&lt;/cmath&gt;for every &lt;math&gt;x&lt;/math&gt; between &lt;math&gt;0&lt;/math&gt; and &lt;math&gt;\pi&lt;/math&gt;, inclusive?<br /> &lt;cmath&gt;\textbf{(A) } y=0 \qquad \textbf{(B) } 0\leq y\leq \frac{\pi}{4} \qquad \textbf{(C) } 0\leq y\leq \frac{\pi}{2} \qquad \textbf{(D) } 0\leq y\leq \frac{3\pi}{4} \qquad \textbf{(E) } 0\leq y\leq \pi &lt;/cmath&gt;<br /> <br /> == Solution 1 ==<br /> On the interval &lt;math&gt;[0, \pi]&lt;/math&gt; sine is nonnegative; thus &lt;math&gt;\sin(x + y) = \sin x \cos y + \sin y \cos x \le \sin x + \sin y&lt;/math&gt; for all &lt;math&gt;x, y \in [0, \pi]&lt;/math&gt;. The answer is &lt;math&gt;\boxed{\textbf{(E) } 0\le y\le \pi}&lt;/math&gt;. (CantonMathGuy)<br /> <br /> ==Solution 2==<br /> Expanding as before, &lt;cmath&gt;\cos y \sin x + \cos x \sin y \le \sin x + \sin y&lt;/cmath&gt; Let &lt;math&gt;\sin x =a \ge 0&lt;/math&gt;, &lt;math&gt;\sin y = b \ge 0&lt;/math&gt;. We have that &lt;cmath&gt;(\cos y)a+(\cos x)b \le a+b&lt;/cmath&gt; Comparing coefficients of &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; gives a clear solution: both &lt;math&gt;\cos y&lt;/math&gt; and &lt;math&gt;\cos x&lt;/math&gt; are less than or equal to one, so the coefficients of &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; on the left are less than on the right. Since &lt;math&gt;a, b \ge 0&lt;/math&gt;, that means that this equality is always satisfied over this interval, or &lt;math&gt;\boxed{\textbf{(E) } 0\le y\le \pi}&lt;/math&gt;.<br /> <br /> ==See Also==<br /> {{AMC12 box|year=2018|ab=A|num-b=8|num-a=10}}<br /> {{MAA Notice}}</div> FINNN https://artofproblemsolving.com/wiki/index.php?title=2008_AMC_12B_Problems/Problem_24&diff=90044 2008 AMC 12B Problems/Problem 24 2018-01-29T03:35:01Z <p>FINNN: /* Solution */</p> <hr /> <div>==Problem 24==<br /> Let &lt;math&gt;A_0=(0,0)&lt;/math&gt;. Distinct points &lt;math&gt;A_1,A_2,\dots&lt;/math&gt; lie on the &lt;math&gt;x&lt;/math&gt;-axis, and distinct points &lt;math&gt;B_1,B_2,\dots&lt;/math&gt; lie on the graph of &lt;math&gt;y=\sqrt{x}&lt;/math&gt;. For every positive integer &lt;math&gt;n,\ A_{n-1}B_nA_n&lt;/math&gt; is an equilateral triangle. What is the least &lt;math&gt;n&lt;/math&gt; for which the length &lt;math&gt;A_0A_n\geq100&lt;/math&gt;?<br /> <br /> &lt;math&gt;\textbf{(A)}\ 13\qquad \textbf{(B)}\ 15\qquad \textbf{(C)}\ 17\qquad \textbf{(D)}\ 19\qquad \textbf{(E)}\ 21&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> Let &lt;math&gt;a_n=|A_{n-1}A_n|&lt;/math&gt;. We need to rewrite the recursion into something manageable. The two strange conditions, &lt;math&gt;B&lt;/math&gt;'s lie on the graph of &lt;math&gt;y=\sqrt{x}&lt;/math&gt; and &lt;math&gt;A_{n-1}B_nA_n&lt;/math&gt; is an equilateral triangle, can be compacted as follows: &lt;cmath&gt;\left(a_n\frac{\sqrt{3}}{2}\right)^2=\frac{a_n}{2}+a_{n-1}+a_{n-2}+\cdots+a_1&lt;/cmath&gt;<br /> which uses &lt;math&gt;y^2=x&lt;/math&gt;, where &lt;math&gt;x&lt;/math&gt; is the height of the equilateral triangle and therefore &lt;math&gt;\frac{\sqrt{3}}{2}&lt;/math&gt; times its base.<br /> <br /> The relation above holds for &lt;math&gt;n=k&lt;/math&gt; and for &lt;math&gt;n=k-1&lt;/math&gt; &lt;math&gt;(k&gt;1)&lt;/math&gt;, so &lt;cmath&gt;\left(a_k\frac{\sqrt{3}}{2}\right)^2-\left(a_{k-1}\frac{\sqrt{3}}{2}\right)^2=&lt;/cmath&gt;<br /> &lt;cmath&gt;=\left(\frac{a_k}{2}+a_{k-1}+a_{k-2}+\cdots+a_1\right)-\left(\frac{a_{k-1}}{2}+a_{k-2}+a_{k-3}+\cdots+a_1\right)&lt;/cmath&gt;<br /> Or, &lt;cmath&gt;a_k-a_{k-1}=\frac23&lt;/cmath&gt; This implies that each segment of a successive triangle is &lt;math&gt;\frac23&lt;/math&gt; more than the last triangle. To find &lt;math&gt;a_{1}&lt;/math&gt;, we merely have to plug in &lt;math&gt;k=1&lt;/math&gt; into the aforementioned recursion and we have &lt;math&gt;a_{1} - a_{0} = \frac23&lt;/math&gt;. Knowing that &lt;math&gt;a_{0}&lt;/math&gt; is &lt;math&gt;0&lt;/math&gt;, we can deduce that &lt;math&gt;a_{1} = 2/3&lt;/math&gt;.Thus, &lt;math&gt;a_n=\frac{2n}{3}&lt;/math&gt;, so &lt;math&gt;A_0A_n=a_n+a_{n-1}+\cdots+a_1=\frac{2}{3} \cdot \frac{n(n+1)}{2} = \frac{n(n+1)}{3}&lt;/math&gt;. We want to find &lt;math&gt;n&lt;/math&gt; so that &lt;math&gt;n^2&lt;300&lt;(n+1)^2&lt;/math&gt;. &lt;math&gt;n=\boxed{17}&lt;/math&gt; is our answer.<br /> <br /> ==Solution 2==<br /> <br /> Consider two adjacent equilateral triangles obeying the problem statement. For each, drop an altitude to the &lt;math&gt;x&lt;/math&gt; axis and denote the resulting heights &lt;math&gt;h_n&lt;/math&gt; and &lt;math&gt;h_{n+1}&lt;/math&gt;. From 30-60-90 rules, the difference between the base of these altitudes is &lt;cmath&gt;\frac{h_{n+1}}{\sqrt{3}}+\frac{h_n}{\sqrt{3}} \Rightarrow \frac{h_{n+1}+h_n}{\sqrt{3}}&lt;/cmath&gt;<br /> <br /> But the square root curve means that this distance is also expressible as &lt;math&gt;h_{n+1}^2-h_n^2&lt;/math&gt; (the &lt;math&gt;x&lt;/math&gt; coordinates are the squares of the heights). Setting these expressions equal and dividing throughout by &lt;math&gt;h_{n+1}+h_n&lt;/math&gt; leaves &lt;math&gt;h_{n+1}-h_n=\frac{1}{\sqrt{3}}&lt;/math&gt;. So the difference in height of successive triangles is &lt;math&gt;\frac{1}{\sqrt{3}}&lt;/math&gt;, meaning their bases are &lt;math&gt;2/3&lt;/math&gt; wider and wider each time. From here, one can proceed as in Solution 1 to arrive at &lt;math&gt;n=\boxed{17}&lt;/math&gt;.<br /> <br /> ==See Also==<br /> {{AMC12 box|year=2008|ab=B|num-b=23|num-a=25}}<br /> {{MAA Notice}}</div> FINNN https://artofproblemsolving.com/wiki/index.php?title=2004_AMC_12A_Problems/Problem_24&diff=88738 2004 AMC 12A Problems/Problem 24 2017-12-02T00:21:08Z <p>FINNN: /* Problem 24 */</p> <hr /> <div>== Problem 24 ==<br /> A [[plane]] contains points &lt;math&gt;A&lt;/math&gt; and &lt;math&gt;B&lt;/math&gt; with &lt;math&gt;\overline{AB} = 1&lt;/math&gt;. Let &lt;math&gt;S&lt;/math&gt; be the [[union]] of all disks of radius &lt;math&gt;1&lt;/math&gt; in the plane that cover &lt;math&gt;\overline{AB}&lt;/math&gt;. What is the area of &lt;math&gt;S&lt;/math&gt;?<br /> <br /> &lt;math&gt;\text {(A)} 2\pi + \sqrt3 \qquad \text {(B)} \frac {8\pi}{3} \qquad \text {(C)} 3\pi - \frac {\sqrt3}{2} \qquad \text {(D)} \frac {10\pi}{3} - \sqrt3 \qquad \text {(E)}4\pi - 2\sqrt3&lt;/math&gt;<br /> <br /> ==Solution==<br /> &lt;center&gt;&lt;asy&gt;<br /> pair A=(-.5,0), B=(.5,0), C=(0,3**(.5)/2), D=(0,-3**(.5)/2);<br /> <br /> draw(arc(A,2,-60,60),blue);<br /> draw(arc(B,2,120,240),blue);<br /> draw(circle(C,1),red);<br /> <br /> draw(A--(.5,3^.5));<br /> draw(B--(-.5,3^.5));<br /> draw(A--(.5,-3^.5));<br /> draw(B--(-.5,-3^.5));<br /> draw(A--B);<br /> <br /> dot(A);dot(B);dot(C);dot(D);<br /> <br /> label(&quot;$$1$$&quot;,(0,0),N);<br /> label(&quot;$$1$$&quot;,A/2+D/2,W);<br /> label(&quot;$$1$$&quot;,A/2+C/2,W);<br /> label(&quot;$$1$$&quot;,B/2+D/2,E);<br /> label(&quot;$$1$$&quot;,B/2+C/2,E);<br /> label(&quot;$$1$$&quot;,A/2+3D/2,W);<br /> label(&quot;$$1$$&quot;,A/2+3C/2,W);<br /> label(&quot;$$1$$&quot;,B/2+3D/2,E);<br /> label(&quot;$$1$$&quot;,B/2+3C/2,E);<br /> <br /> label(&quot;$$A$$&quot;,A,W);<br /> label(&quot;$$B$$&quot;,B,E);<br /> label(&quot;$$C$$&quot;,C,W);<br /> label(&quot;$$D$$&quot;,D,E);<br /> &lt;/asy&gt;&lt;/center&gt;<br /> <br /> As the red circles move about segment &lt;math&gt;AB&lt;/math&gt;, they cover the area we are looking for.<br /> On the left side, the circle must move around pivoted on &lt;math&gt;B&lt;/math&gt;.<br /> On the right side, the circle must move pivoted on &lt;math&gt;A&lt;/math&gt;<br /> However, at the top and bottom, the circle must lie on both A and B, giving us our upper and lower bounds.<br /> <br /> This egg-like shape is &lt;math&gt;S&lt;/math&gt;.<br /> &lt;center&gt;&lt;asy&gt;<br /> pair A=(-.5,0), B=(.5,0), C=(0,3**(.5)/2), D=(0,-3**(.5)/2);<br /> <br /> draw(arc(A,2,-60,60),blue);<br /> draw(arc(B,2,120,240),blue);<br /> draw(arc(C,1,60,120),red);<br /> draw(arc(D,1,-120,-60),red);<br /> <br /> draw(A--(.5,3^.5));<br /> draw(B--(-.5,3^.5));<br /> draw(A--(.5,-3^.5));<br /> draw(B--(-.5,-3^.5));<br /> draw(A--B);<br /> <br /> dot(A);dot(B);dot(C);dot(D);<br /> label(&quot;$$A$$&quot;,A,W);<br /> label(&quot;$$B$$&quot;,B,E);<br /> label(&quot;$$C$$&quot;,C,W);<br /> label(&quot;$$D$$&quot;,D,E);<br /> <br /> label(&quot;$$1$$&quot;,(0,0),N);<br /> label(&quot;$$1$$&quot;,A/2+D/2,W);<br /> label(&quot;$$1$$&quot;,A/2+C/2,W);<br /> label(&quot;$$1$$&quot;,B/2+D/2,E);<br /> label(&quot;$$1$$&quot;,B/2+C/2,E);<br /> label(&quot;$$1$$&quot;,A/2+3D/2,W);<br /> label(&quot;$$1$$&quot;,A/2+3C/2,W);<br /> label(&quot;$$1$$&quot;,B/2+3D/2,E);<br /> label(&quot;$$1$$&quot;,B/2+3C/2,E);<br /> &lt;/asy&gt;&lt;/center&gt;<br /> <br /> The area of the region can be found by dividing it into several sectors, namely<br /> <br /> &lt;cmath&gt;\begin{align*}<br /> A &amp;= 2(\mathrm{Blue\ Sector}) + 2(\mathrm{Red\ Sector}) - 2(\mathrm{Equilateral\ Triangle}) \\<br /> A &amp;= 2\left(\frac{120^\circ}{360^\circ} \cdot \pi (2)^2\right) + 2\left(\frac{60^\circ}{360^\circ} \cdot \pi (1)^2\right) - 2\left(\frac{(1)^2\sqrt{3}}{4}\right) \\<br /> A &amp;= \frac{8\pi}{3} + \frac{\pi}{3} - \frac{\sqrt{3}}{2} \\<br /> A &amp;= 3\pi - \frac{\sqrt{3}}{2} \Longrightarrow \textbf {(C)}\end{align*}&lt;/cmath&gt;<br /> <br /> ==See also== <br /> {{AMC12 box|year=2004|ab=A|num-b=23|num-a=25}}<br /> <br /> [[Category:Intermediate Geometry Problems]]<br /> {{MAA Notice}}</div> FINNN https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_I_Problems/Problem_11&diff=85238 2011 AIME I Problems/Problem 11 2017-04-16T01:26:40Z <p>FINNN: /* Solution 4 */</p> <hr /> <div>== Problem ==<br /> Let &lt;math&gt;R&lt;/math&gt; be the set of all possible remainders when a number of the form &lt;math&gt;2^n&lt;/math&gt;, &lt;math&gt;n&lt;/math&gt; a nonnegative integer, is divided by &lt;math&gt;1000&lt;/math&gt;. Let &lt;math&gt;S&lt;/math&gt; be the sum of the elements in &lt;math&gt;R&lt;/math&gt;. Find the remainder when &lt;math&gt;S&lt;/math&gt; is divided by &lt;math&gt;1000&lt;/math&gt;.<br /> <br /> == Solution 1==<br /> Note that &lt;math&gt;x \equiv y \pmod{1000} \Leftrightarrow x \equiv y \pmod{125}&lt;/math&gt; and &lt;math&gt;x \equiv y \pmod{8}&lt;/math&gt;. So we must find the first two integers &lt;math&gt;i&lt;/math&gt; and &lt;math&gt;j&lt;/math&gt; such that &lt;math&gt;2^i \equiv 2^j \pmod{125}&lt;/math&gt; and &lt;math&gt;2^i \equiv 2^j \pmod{8}&lt;/math&gt; and &lt;math&gt;i \neq j&lt;/math&gt;. Note that &lt;math&gt;i&lt;/math&gt; and &lt;math&gt;j&lt;/math&gt; will be greater than 2 since remainders of &lt;math&gt;1, 2, 4&lt;/math&gt; will not be possible after 2 (the numbers following will always be congruent to 0 modulo 8). Note that &lt;math&gt;2^{100}\equiv 1\pmod{125}&lt;/math&gt; (see [[Euler's Totient Theorem|Euler's theorem]]) and &lt;math&gt;2^0,2^1,2^2,\ldots,2^{99}&lt;/math&gt; are all distinct modulo 125 (proof below). Thus, &lt;math&gt;i = 103&lt;/math&gt; and &lt;math&gt;j =3&lt;/math&gt; are the first two integers such that &lt;math&gt;2^i \equiv 2^j \pmod{1000}&lt;/math&gt;. All that is left is to find &lt;math&gt;S&lt;/math&gt; in mod &lt;math&gt;1000&lt;/math&gt;. After some computation:<br /> &lt;cmath&gt;<br /> S = 2^0+2^1+2^2+2^3+2^4+...+2^{101}+ 2^{102} = 2^{103}-1 \equiv 8 - 1 \mod 1000 = \boxed{007}.<br /> &lt;/cmath&gt;<br /> To show that &lt;math&gt;2^0, 2^1,\ldots, 2^{99}&lt;/math&gt; are distinct modulo 125, suppose for the sake of contradiction that they are not. Then, we must have at least one of &lt;math&gt;2^{20}\equiv 1\pmod{125}&lt;/math&gt; or &lt;math&gt;2^{50}\equiv 1\pmod{125}&lt;/math&gt;. However, writing &lt;math&gt;2^{10}\equiv 25 - 1\pmod{125}&lt;/math&gt;, we can easily verify that &lt;math&gt;2^{20}\equiv -49\pmod{125}&lt;/math&gt; and &lt;math&gt;2^{50}\equiv -1\pmod{125}&lt;/math&gt;, giving us the needed contradiction.<br /> <br /> == Solution 2 ==<br /> Notice that our sum of remainders looks like &lt;cmath&gt;S = 1 + 2 + 4 + 2^3 + 2^4 + \cdots.&lt;/cmath&gt; We want to find the remainder of &lt;math&gt;S&lt;/math&gt; upon division by &lt;math&gt;1000.&lt;/math&gt; Since &lt;math&gt;1000&lt;/math&gt; decomposes into primes as &lt;math&gt;1000 = 2^3 \cdot 5^3&lt;/math&gt;, we can check the remainders of &lt;math&gt;S&lt;/math&gt; modulo &lt;math&gt;2^3&lt;/math&gt; and modulo &lt;math&gt;5^3&lt;/math&gt; separately. <br /> <br /> Checking &lt;math&gt;S&lt;/math&gt; modulo &lt;math&gt;2^3&lt;/math&gt; is easy, so lets start by computing the remainder of &lt;math&gt;S&lt;/math&gt; upon division by &lt;math&gt;5^3.&lt;/math&gt; To do this, let's figure out when our sequence finally repeats.<br /> Notice that since the remainder when dividing any term of &lt;math&gt;S&lt;/math&gt; (after the third term) by &lt;math&gt;1000&lt;/math&gt; will be a multiple of &lt;math&gt;2^3&lt;/math&gt;, when this summation finally repeats, the first term to repeat will be ''not'' be &lt;math&gt;1&lt;/math&gt; since &lt;math&gt;2^3 \nmid 1.&lt;/math&gt; Instead, the first term to repeat will be &lt;math&gt;2^3&lt;/math&gt;, and then the sequence will continue once again &lt;math&gt;2^4, 2^5, \cdots.&lt;/math&gt; <br /> <br /> Now, to compute &lt;math&gt;S&lt;/math&gt; modulo &lt;math&gt;125&lt;/math&gt;, we want to find the least positive integer &lt;math&gt;d&lt;/math&gt; such that &lt;math&gt;2^d \equiv 1 \pmod {125}&lt;/math&gt; since then &lt;math&gt;d&lt;/math&gt; will just be the number of terms of &lt;math&gt;S&lt;/math&gt; (after the third term!) before the sequence repeats. In other words, our sequence will be of the form &lt;math&gt;S = 1 + 2 + 4 + \left(2^3 + 2^4 + \cdots + 2^{2 + d}\right)&lt;/math&gt; and then we will have &lt;math&gt;2^{d + 3} \equiv 2^3 \pmod {125}&lt;/math&gt;, and the sequence will repeat from there. Here, &lt;math&gt;d&lt;/math&gt; simply represents the order of &lt;math&gt;2&lt;/math&gt; modulo &lt;math&gt;125&lt;/math&gt;, denoted by &lt;math&gt;d = \text{ord}_{125}(2).&lt;/math&gt; To begin with, we'll use a well-known property of the order to get a bound on &lt;math&gt;d.&lt;/math&gt;<br /> <br /> Since &lt;math&gt;\gcd(2, 125) = 1&lt;/math&gt; and &lt;math&gt;\phi(125) = 100&lt;/math&gt;, we know by Euler's Theorem that &lt;math&gt;2^{100} \equiv 1 \pmod {125}.&lt;/math&gt; However, we do not know that &lt;math&gt;100&lt;/math&gt; is the ''least'' &lt;math&gt;d&lt;/math&gt; satisfying &lt;math&gt;2^d \equiv 1 \pmod {125}.&lt;/math&gt; Nonetheless, it is a well known property of the order that &lt;math&gt;\text{ord}_{125}(2) = d | \phi(125) = 100.&lt;/math&gt; Therefore, we can conclude that &lt;math&gt;d&lt;/math&gt; must be a positive divisor of &lt;math&gt;100.&lt;/math&gt;<br /> <br /> Now, this still leaves a lot of possibilities, so let's consider a smaller modulus for the moment, say &lt;math&gt;\mod 5.&lt;/math&gt; Clearly, we must have that &lt;math&gt;2^d \equiv 1 \pmod 5.&lt;/math&gt; Since &lt;math&gt;2^4 \equiv 1 \pmod 5&lt;/math&gt; and powers of two will then cycle every four terms, we know that &lt;math&gt;2^d \equiv 1 \pmod 5 \iff 4 | d.&lt;/math&gt; Combining this relation with &lt;math&gt;d | 100&lt;/math&gt;, it follows that &lt;math&gt;d \in \{4, 20, 100\}.&lt;/math&gt; <br /> <br /> Now, it is trivial to verify that &lt;math&gt;d \ne 4.&lt;/math&gt; In addition, we know that &lt;cmath&gt;2^{20} = \left(2^{10}\right)^2 = \left(1024\right)^2 \equiv 24^2 = 576 \not\equiv 1 \pmod {125}.&lt;/cmath&gt; Therefore, we conclude that &lt;math&gt;d \ne 20.&lt;/math&gt; Hence, we must have &lt;math&gt;d = 100.&lt;/math&gt; (Notice that we could have guessed this by Euler's, but we couldn't have been certain without investigating the order more thoroughly).<br /> <br /> Now, since we have found &lt;math&gt;d = 100&lt;/math&gt;, we know that &lt;cmath&gt;S = 1 + 2 + 4 + 2^3 + 2^4 + \cdots + 2^{102}.&lt;/cmath&gt; There are two good ways to finish from here: <br /> <br /> The first way is to use a trick involving powers of &lt;math&gt;2.&lt;/math&gt; Notice that &lt;cmath&gt;S = 1 + 2 + 4 + ... + 2^{102} = 2^{103} - 1.&lt;/cmath&gt; Certainly &lt;cmath&gt;S = 2^{103} - 1 \equiv -1 \equiv 7 \pmod {8}.&lt;/cmath&gt; In addition, since we already computed &lt;math&gt;\text{ord}_{125}(2) = d = 100&lt;/math&gt;, we know that &lt;cmath&gt;S = 2^{103} - 1 = 2^{100} \cdot 2^3 - 1 \equiv 2^3 - 1 \equiv 7 \pmod {125}.&lt;/cmath&gt; Therefore, since &lt;math&gt;S \equiv 7 \pmod{8}&lt;/math&gt; and &lt;math&gt;S \equiv 7 \pmod{125}&lt;/math&gt;, we conclude that &lt;math&gt;S \equiv \boxed{007} \pmod {1000}.&lt;/math&gt;<br /> <br /> The second way is not as slick, but works better in a general setting when there aren't any convenient tricks as in Method 1. Let us split the terms of &lt;math&gt;S&lt;/math&gt; into groups: &lt;cmath&gt;R = 1 + 2 + 4; \quad T = 2^3 + 2^4 + \cdots + 2^{102}.&lt;/cmath&gt; It is easy to see that &lt;math&gt;R&lt;/math&gt; is congruent to &lt;math&gt;7&lt;/math&gt; modulo &lt;math&gt;1000.&lt;/math&gt; <br /> <br /> Now, for &lt;math&gt;T&lt;/math&gt;, notice that there are &lt;math&gt;100&lt;/math&gt; terms in the summation, each with a different remainder upon division by &lt;math&gt;125.&lt;/math&gt; Since each of these remainders is certainly relatively prime to &lt;math&gt;125&lt;/math&gt;, these &lt;math&gt;100&lt;/math&gt; remainders correspond to the &lt;math&gt;100&lt;/math&gt; positive integers less than &lt;math&gt;125&lt;/math&gt; that are relatively prime to &lt;math&gt;125.&lt;/math&gt; Therefore, <br /> &lt;cmath&gt;\begin{align*}T &amp;\equiv 1 + 2 + 3 + 4 + 6 + 7 + 8 + 9 + 11 + \cdots + 124 \pmod{125} \\<br /> &amp;= \left(1 + 2 + 3 + \cdots + 125\right) - \left(5 + 10 + 15 + \cdots 125\right) \\<br /> &amp;= \frac{125 \cdot 126}{2} - 5\left(1 + 2 + 3 + \cdots 25\right) \\<br /> &amp;= 125 \cdot 63 - 5\left(\frac{25 \cdot 26}{2}\right) \\<br /> &amp;= 125\left(63 - 13\right) \\<br /> &amp;\equiv 0 \pmod{125}.\end{align*}&lt;/cmath&gt;<br /> Then, since &lt;math&gt;T&lt;/math&gt; is divisible by &lt;math&gt;125&lt;/math&gt; and &lt;math&gt;8&lt;/math&gt;, it follows that &lt;math&gt;T&lt;/math&gt; is divisible by &lt;math&gt;1000.&lt;/math&gt; Therefore, &lt;cmath&gt;S = R + T \equiv R \equiv \boxed{007} \pmod{1000}.&lt;/cmath&gt;<br /> <br /> == Solution 3 (Fake-ish) ==<br /> After listing out a few remainders of numbers of the form &lt;math&gt;2^i&lt;/math&gt;, namely &lt;math&gt;1, 2, 4, 8, 16, 64, 128, 512, 024, 048...&lt;/math&gt;, we can guess that, except for the first &lt;math&gt;3&lt;/math&gt;, the remainder will hit every multiple of &lt;math&gt;8&lt;/math&gt; between &lt;math&gt;8&lt;/math&gt; and &lt;math&gt;992&lt;/math&gt;, inclusive. This means that our sum is of the form &lt;math&gt;1 + 2 + 4 + 8(1+2+...+124)&lt;/math&gt;. This can be written as <br /> &lt;math&gt;1 + 2 + 4 + 8(\frac{124\cdot125}{2}) = 7+4(124\cdot125)&lt;/math&gt;. Since the, last term, &lt;math&gt;4(124\cdot125)&lt;/math&gt;, is divisible by &lt;math&gt;1000&lt;/math&gt; it's remainder is &lt;math&gt;0&lt;/math&gt;. Thus the total remainder is just &lt;math&gt;1+2+4 = \boxed{007}.&lt;/math&gt;<br /> <br /> == Solution 4 ==<br /> We know &lt;math&gt;1, 2,&lt;/math&gt; and &lt;math&gt;4&lt;/math&gt; are in &lt;math&gt;R&lt;/math&gt;. Any other element in &lt;math&gt;R&lt;/math&gt; must be a multiple of &lt;math&gt;8&lt;/math&gt;. All multiples of &lt;math&gt;8&lt;/math&gt; under &lt;math&gt;1000&lt;/math&gt; sum up to a multiple of &lt;math&gt;1000&lt;/math&gt;. So we can ignore them. We need to remove all multiples of &lt;math&gt;5&lt;/math&gt;, or &lt;math&gt;40&lt;/math&gt; in what we counted because all elements of &lt;math&gt;R&lt;/math&gt; can only be divisible by &lt;math&gt;2&lt;/math&gt;. But, their sum is also a multiple of &lt;math&gt;1000&lt;/math&gt;. Likewise, the sum of all multiples of &lt;math&gt;8k&lt;/math&gt; for some &lt;math&gt;k&lt;/math&gt; will be a multiple of &lt;math&gt;1000&lt;/math&gt;. Thus, our answer is &lt;math&gt;1+2+4=\boxed{007}&lt;/math&gt;.<br /> <br /> Solution by TheUltimate123<br /> <br /> == Solution 5 ==<br /> <br /> Recognize that as you cycle through progressively higher powers of two, you will have to begin repeating in a pattern at some point, since there are only a finite number of possible 3-digit endings and clearly there is no way for a small sub-pattern to form. The previous statement is true by induction since if a pattern began occurring, then it would need to occur for all values before that as well which is clearly untrue unless it encompasses all possible powers of two. Thus we can start thinking about a final value for it to start repeating. It can't be &lt;math&gt;001&lt;/math&gt; or &lt;math&gt;501&lt;/math&gt;, and it can't be &lt;math&gt;002&lt;/math&gt; or &lt;math&gt;502&lt;/math&gt; either because the last two digits of any power of 2 greater than &lt;math&gt;2^1&lt;/math&gt; are divisible by 4. However, it can be &lt;math&gt;004&lt;/math&gt; or &lt;math&gt;504&lt;/math&gt;. From the fact that &lt;math&gt;1+2+4+8 \dots 2^n=2^{n+1}-1&lt;/math&gt;, we can safely assume that the sum of all possible endings mod 1000 will be &lt;math&gt;2 \times4 -1=\boxed{007}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=2011|n=I|num-b=10|num-a=12}}<br /> {{MAA Notice}}</div> FINNN https://artofproblemsolving.com/wiki/index.php?title=2017_AIME_II_Problems/Problem_6&diff=84936 2017 AIME II Problems/Problem 6 2017-03-23T20:00:31Z <p>FINNN: /* Solution */</p> <hr /> <div>==Problem==<br /> Find the sum of all positive integers &lt;math&gt;n&lt;/math&gt; such that &lt;math&gt;\sqrt{n^2+85n+2017}&lt;/math&gt; is an integer.<br /> <br /> ==Solution 1==<br /> Manipulating the given expression, &lt;math&gt;\sqrt{n^2+85n+2017}=\frac{1}{2}\sqrt{4n^2+340n+8068}=\frac{1}{2}\sqrt{(2n+85)^2+843}&lt;/math&gt;. The expression under the radical must be an square number for the entire expression to be an integer, so &lt;math&gt;(2n+85)^2+843=s^2&lt;/math&gt;. Rearranging, &lt;math&gt;s^2-(2n+85)^2=843&lt;/math&gt;. By difference of squares, &lt;math&gt;(s-(2n+85))(s+(2n+85))=1\times843=3\times281&lt;/math&gt;. It is easy to check that those are all the factor pairs of 843. Considering each factor pair separately, &lt;math&gt;2n+85&lt;/math&gt; is found to be &lt;math&gt;421&lt;/math&gt; and &lt;math&gt;139&lt;/math&gt;. The two values of &lt;math&gt;n&lt;/math&gt; that satisfy one of the equations are &lt;math&gt;168&lt;/math&gt; and &lt;math&gt;27&lt;/math&gt;. Summing these together, the answer is &lt;math&gt;168+27=\boxed{195}&lt;/math&gt;.<br /> <br /> ==Solution 2==<br /> Clearly, the result when &lt;math&gt;n&lt;/math&gt; is plugged into the given expression is larger than &lt;math&gt;n&lt;/math&gt; itself. Let &lt;math&gt;x&lt;/math&gt; be the positive difference between that result and &lt;math&gt;n&lt;/math&gt;, so that &lt;math&gt;\sqrt{n^2+85n+2017}=n+x&lt;/math&gt;. Squaring both sides and canceling the &lt;math&gt;n^2&lt;/math&gt; terms gives &lt;math&gt;85n+2017=2xn+x^2&lt;/math&gt;. Combining like terms, &lt;math&gt;(85-2x)n=x^2-2017&lt;/math&gt;, so<br /> <br /> &lt;cmath&gt;n=\frac{x^2-2017}{85-2x}.&lt;/cmath&gt;<br /> <br /> Since &lt;math&gt;n&lt;/math&gt; is positive, there are two cases, which are simple (luckily). Remembering that &lt;math&gt;x&lt;/math&gt; is a positive integer, then &lt;math&gt;x^2-2017&lt;/math&gt; and &lt;math&gt;85-2x&lt;/math&gt; are either both positive or both negative. The smallest value for which &lt;math&gt;x^2&gt;2017&lt;/math&gt; is 45, which makes the denominator, and the entire expression, negative. Evaluating the other case where numerator and denominator are both negative, then we have that &lt;math&gt;x&lt;45&lt;/math&gt; (from the numerator) and &lt;math&gt;85-2x&lt;0&lt;/math&gt;, which means &lt;math&gt;x&gt;42&lt;/math&gt;. This only gives two solutions, &lt;math&gt;x=43, 44&lt;/math&gt;. Plugging these into the expression for &lt;math&gt;n&lt;/math&gt;, we find that they result in 27 and 168, which both satisfy the initial question. Therefore, the answer is &lt;math&gt;168+27=\boxed{195}&lt;/math&gt;.<br /> <br /> =See Also=<br /> {{AIME box|year=2017|n=II|num-b=5|num-a=7}}<br /> {{MAA Notice}}</div> FINNN https://artofproblemsolving.com/wiki/index.php?title=2017_AIME_II_Problems/Problem_1&diff=84925 2017 AIME II Problems/Problem 1 2017-03-23T19:16:44Z <p>FINNN: /* Solution */</p> <hr /> <div>==Problem==<br /> Find the number of subsets of &lt;math&gt;\{1, 2, 3, 4, 5, 6, 7, 8\}&lt;/math&gt; that are subsets of neither &lt;math&gt;\{1, 2, 3, 4, 5\}&lt;/math&gt; nor &lt;math&gt;\{4, 5, 6, 7, 8\}&lt;/math&gt;.<br /> <br /> ==Solution 1==<br /> The number of subsets of a set with &lt;math&gt;n&lt;/math&gt; elements is &lt;math&gt;2^n&lt;/math&gt;. The total number of subsets of &lt;math&gt;\{1, 2, 3, 4, 5, 6, 7, 8\}&lt;/math&gt; is equal to &lt;math&gt;2^8&lt;/math&gt;. The number of sets that are subsets of at least one of &lt;math&gt;\{1, 2, 3, 4, 5\}&lt;/math&gt; or &lt;math&gt;\{4, 5, 6, 7, 8\}&lt;/math&gt; can be found using complimentary counting. There are &lt;math&gt;2^5&lt;/math&gt; subsets of &lt;math&gt;\{1, 2, 3, 4, 5\}&lt;/math&gt; and &lt;math&gt;2^5&lt;/math&gt; subsets of &lt;math&gt;\{4, 5, 6, 7, 8\}&lt;/math&gt;. It is easy to make the mistake of assuming there are &lt;math&gt;2^5+2^5&lt;/math&gt; sets that are subsets of at least one of &lt;math&gt;\{1, 2, 3, 4, 5\}&lt;/math&gt; or &lt;math&gt;\{4, 5, 6, 7, 8\}&lt;/math&gt;, but the &lt;math&gt;2^2&lt;/math&gt; subsets of &lt;math&gt;\{4, 5\}&lt;/math&gt; are overcounted. There are &lt;math&gt;2^5+2^5-2^2&lt;/math&gt; sets that are subsets of at least one of &lt;math&gt;\{1, 2, 3, 4, 5\}&lt;/math&gt; or &lt;math&gt;\{4, 5, 6, 7, 8\}&lt;/math&gt;, so there are &lt;math&gt;2^8-(2^5+2^5-2^2)&lt;/math&gt; subsets of &lt;math&gt;\{1, 2, 3, 4, 5, 6, 7, 8\}&lt;/math&gt; that are subsets of neither &lt;math&gt;\{1, 2, 3, 4, 5\}&lt;/math&gt; nor &lt;math&gt;\{4, 5, 6, 7, 8\}&lt;/math&gt;. &lt;math&gt;2^8-(2^5+2^5-2^2)=\boxed{196}&lt;/math&gt;.<br /> <br /> ==Solution 2== <br /> Upon inspection, a viable set must contain at least one element from both of the sets &lt;math&gt;\{1, 2, 3, 4, 5\}&lt;/math&gt; and &lt;math&gt;\{4, 5, 6, 7, 8\}&lt;/math&gt;. Since 4 and 5 are included in both of these sets, then they basically don't matter, i.e. if set A is a subset of both of those two then adding a 4 or a 5 won't change that fact. Thus, we can count the number of ways to choose at least one number from 1 to 3 and at least one number from 6 to 8, and then multiply that by the number of ways to add in 4 and 5. The number of subsets of a 3 element set is &lt;math&gt;2^3=8&lt;/math&gt;, but we want to exclude the empty set, giving us 7 ways to choose from &lt;math&gt;\{1, 2, 3\}&lt;/math&gt; or &lt;math&gt;\{4, 5, 6\}&lt;/math&gt;. We can take each of these &lt;math&gt;7 \times 7=49&lt;/math&gt; sets and add in a 4 and/or a 5, which can be done in 4 different ways (by adding both, none, one, or the other one). Thus, the answer is &lt;math&gt;49 \times 4=\boxed{196}&lt;/math&gt;.<br /> <br /> =See Also=<br /> {{AIME box|year=2017|n=II|before=First Problem|num-a=2}}<br /> {{MAA Notice}}</div> FINNN https://artofproblemsolving.com/wiki/index.php?title=1999_AMC_8_Problems/Problem_24&diff=65949 1999 AMC 8 Problems/Problem 24 2014-11-18T17:59:53Z <p>FINNN: /* Solution */</p> <hr /> <div>==Problem==<br /> <br /> When &lt;math&gt;1999^{2000}&lt;/math&gt; is divided by &lt;math&gt;5&lt;/math&gt;, the remainder is <br /> <br /> &lt;math&gt;\text{(A)}\ 4 \qquad \text{(B)}\ 3 \qquad \text{(C)}\ 2 \qquad \text{(D)}\ 1 \qquad \text{(E)}\ 0&lt;/math&gt;<br /> <br /> <br /> ==Solution 1==<br /> Note that the units digits of the powers of 9 have a pattern: &lt;math&gt;9^1 = {\bf 9}&lt;/math&gt;,&lt;math&gt;9^2 = 8{\bf 1}&lt;/math&gt;,&lt;math&gt;9^3 = 72{\bf 9}&lt;/math&gt;,&lt;math&gt;9^4 = 656{\bf 1}&lt;/math&gt;, and so on. Since all natural numbers with the same last digit have the same remainder when divided by 5, the entire number doesn't matter, just the last digit. For even powers of &lt;math&gt;9&lt;/math&gt;, the number ends in a &lt;math&gt;1&lt;/math&gt;. Since the exponent is even, the final digit is &lt;math&gt;1&lt;/math&gt;. Note that all natural numbers that end in &lt;math&gt;1&lt;/math&gt; have a remainder of &lt;math&gt;1&lt;/math&gt; when divided by &lt;math&gt;5&lt;/math&gt;. So, our answer is &lt;math&gt;\boxed{\text{(D)}\ 1}&lt;/math&gt;.<br /> <br /> ==Solution 2==<br /> <br /> Write &lt;math&gt;1999&lt;/math&gt; as &lt;math&gt;2000-1&lt;/math&gt;. We are taking &lt;math&gt;(2000-1)^{2000} \mod{10}&lt;/math&gt;. Using the binomial theorem, we see that ALL terms in this expansion are divisible by &lt;math&gt;2000&lt;/math&gt; except for the very last term, which is just &lt;math&gt;(-1)^{2000}&lt;/math&gt;. This is clear because the binomial expansion is just choosing how many &lt;math&gt;2000&lt;/math&gt;s and how many &lt;math&gt;-1&lt;/math&gt;s there are for each term. Using this, we can take the entire polynomial &lt;math&gt;\mod{10}&lt;/math&gt;, which leaves just &lt;math&gt;(-1)^{2000}=\boxed{\text{(D)}\ 1}&lt;/math&gt;.<br /> <br /> ==See Also==<br /> {{AMC8 box|year=1999|num-b=23|num-a=25}}<br /> {{MAA Notice}}</div> FINNN