https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Avn&feedformat=atom AoPS Wiki - User contributions [en] 2021-11-29T16:05:00Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_12B_Problems/Problem_24&diff=140543 2016 AMC 12B Problems/Problem 24 2020-12-25T01:55:41Z <p>Avn: /* Solution */</p> <hr /> <div>==Problem==<br /> There are exactly &lt;math&gt;77,000&lt;/math&gt; ordered quadruplets &lt;math&gt;(a, b, c, d)&lt;/math&gt; such that &lt;math&gt;\gcd(a, b, c, d) = 77&lt;/math&gt; and &lt;math&gt;\operatorname{lcm}(a, b, c, d) = n&lt;/math&gt;. What is the smallest possible value for &lt;math&gt;n&lt;/math&gt;?<br /> <br /> &lt;math&gt;\textbf{(A)}\ 13,860\qquad\textbf{(B)}\ 20,790\qquad\textbf{(C)}\ 21,560 \qquad\textbf{(D)}\ 27,720 \qquad\textbf{(E)}\ 41,580&lt;/math&gt;<br /> <br /> ==Solution==<br /> Let &lt;math&gt;A=\frac{a}{77},\ B=\frac{b}{77}&lt;/math&gt;, etc., so that &lt;math&gt;\gcd(A,B,C,D)=1&lt;/math&gt;. Then for each prime power &lt;math&gt;p^k&lt;/math&gt; in the prime factorization of &lt;math&gt;N=\frac{n}{77}&lt;/math&gt;, at least one of the prime factorizations of &lt;math&gt;(A,B,C,D)&lt;/math&gt; has &lt;math&gt;p^k&lt;/math&gt;, at least one has &lt;math&gt;p^0&lt;/math&gt;, and all must have &lt;math&gt;p^m&lt;/math&gt; with &lt;math&gt;0\le m\le k&lt;/math&gt;.<br /> <br /> Let &lt;math&gt;f(k)&lt;/math&gt; be the number of ordered quadruplets of integers &lt;math&gt;(m_1,m_2,m_3,m_4)&lt;/math&gt; such that &lt;math&gt;0\le m_i\le k&lt;/math&gt; for all &lt;math&gt;i&lt;/math&gt;, the largest is &lt;math&gt;k&lt;/math&gt;, and the smallest is &lt;math&gt;0&lt;/math&gt;. Then for the prime factorization &lt;math&gt;N=2^{k_2}3^{k_3}5^{k_5}\ldots&lt;/math&gt; we must have &lt;math&gt;77000=f(k_2)f(k_3)f(k_5)\ldots&lt;/math&gt; So let's take a look at the function &lt;math&gt;f(k)&lt;/math&gt; by counting the quadruplets we just mentioned.<br /> <br /> There are &lt;math&gt;14&lt;/math&gt; quadruplets which consist only of &lt;math&gt;0&lt;/math&gt; and &lt;math&gt;k&lt;/math&gt;. Then there are &lt;math&gt;36(k-1)&lt;/math&gt; quadruplets which include three different values, and &lt;math&gt;12(k-1)(k-2)&lt;/math&gt; with four. Thus &lt;math&gt;f(k)=14+12(k-1)(3+k-2)=14+12(k^2-1)&lt;/math&gt; and the first few values from &lt;math&gt;k=1&lt;/math&gt; onwards are &lt;cmath&gt;14,50,110,194,302,434,590,770,\ldots&lt;/cmath&gt; Straight away we notice that &lt;math&gt;14\cdot 50\cdot 110=77000&lt;/math&gt;, so the prime factorization of &lt;math&gt;N&lt;/math&gt; can use the exponents &lt;math&gt;1,2,3&lt;/math&gt;. To make it as small as possible, assign the larger exponents to smaller primes. The result is &lt;math&gt;N=2^33^25^1=360&lt;/math&gt;, so &lt;math&gt;n=360\cdot 77=27720&lt;/math&gt; which is answer &lt;math&gt;\boxed{\textbf{(D)}}&lt;/math&gt;.<br /> <br /> Also, to get the above formula of &lt;math&gt;f(k)=12 k^2+2&lt;/math&gt;, we can also use the complementary counting by doing &lt;math&gt;(k+1)^4-k^4-k^4+(k-1)^4&lt;/math&gt;, while the first term &lt;math&gt;(k+1)^4&lt;/math&gt; is for the four integers to independently have &lt;math&gt;k+1&lt;/math&gt; choices each, with the second term indicating to subtract all the possibilities for the four integers to have values between &lt;math&gt;0&lt;/math&gt; and &lt;math&gt;k-1&lt;/math&gt;, and similarly the third term indicating to subtract all the possibilities for the four integers to have values between &lt;math&gt;1&lt;/math&gt; and &lt;math&gt;k&lt;/math&gt;, in the end the fourth term meaning the make up for the values between &lt;math&gt;1&lt;/math&gt; and &lt;math&gt;k-1&lt;/math&gt;.<br /> <br /> ==See Also==<br /> {{AMC12 box|year=2016|ab=B|num-a=25|num-b=23}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_II_Problems/Problem_3&diff=124945 2020 AIME II Problems/Problem 3 2020-06-11T05:20:34Z <p>Avn: /* Video Solution 2 */</p> <hr /> <div>==Problem==<br /> <br /> The value of &lt;math&gt;x&lt;/math&gt; that satisfies &lt;math&gt;\log_{2^x} 3^{20} = \log_{2^{x+3}} 3^{2020}&lt;/math&gt; can be written as &lt;math&gt;\frac{m}{n}&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m+n&lt;/math&gt;.<br /> <br /> ==Solution==<br /> Let &lt;math&gt;\log _{2^x}3^{20}=\log _{2^{x+3}}3^{2020}=n&lt;/math&gt;. Based on the equation, we get &lt;math&gt;(2^x)^n=3^{20}&lt;/math&gt; and &lt;math&gt;(2^{x+3})^n=3^{2020}&lt;/math&gt;. Expanding the second equation, we get &lt;math&gt;8^n\cdot2^{xn}=3^{2020}&lt;/math&gt;. Substituting the first equation in, we get &lt;math&gt;8^n\cdot3^{20}=3^{2020}&lt;/math&gt;, so &lt;math&gt;8^n=3^{2000}&lt;/math&gt;. Taking the 100th root, we get &lt;math&gt;8^{\frac{n}{100}}=3^{20}&lt;/math&gt;. Therefore, &lt;math&gt;(2^{\frac{3}{100}})^n=3^{20}&lt;/math&gt;, so &lt;math&gt;n=\frac{3}{100}&lt;/math&gt; and the answer is &lt;math&gt;\boxed{103}&lt;/math&gt;.<br /> ~rayfish<br /> <br /> ==Easiest Solution==<br /> Recall the identity &lt;math&gt;\log_{a^n} b^{m} = \frac{m}{n}\log_{a} b &lt;/math&gt; (which is easily proven using exponents or change of base)<br /> Then this problem turns into &lt;cmath&gt;\frac{20}{x}\log_{2} 3 = \frac{2020}{x+3}\log_{2} 3&lt;/cmath&gt;<br /> Divide &lt;math&gt;\log_{2} 3&lt;/math&gt; from both sides. And we are left with &lt;math&gt;\frac{20}{x}=\frac{2020}{x+3}&lt;/math&gt;.Solving this simple equation we get &lt;cmath&gt;x = \tfrac{3}{100} \Rightarrow \boxed{103}&lt;/cmath&gt;<br /> ~mlgjeffdoge21<br /> <br /> ==Solution 2==<br /> Because &lt;math&gt;\log_a{b^c}=c\log_a{b},&lt;/math&gt; we have that &lt;math&gt;20\log_{2^x} 3 = 2020\log_{2^{x+3}} 3,&lt;/math&gt; or &lt;math&gt;\log_{2^x} 3 = 101\log_{2^{x+3}} 3.&lt;/math&gt; Since &lt;math&gt;\log_a{b}=\dfrac{1}{\log_b{a}},&lt;/math&gt; &lt;math&gt;\log_{2^x} 3=\dfrac{1}{\log_{3} 2^x},&lt;/math&gt; and &lt;math&gt;101\log_{2^{x+3}} 3=101\dfrac{1}{\log_{3}2^{x+3}},&lt;/math&gt; thus resulting in &lt;math&gt;\log_{3}2^{x+3}=101\log_{3} 2^x,&lt;/math&gt; or &lt;math&gt;\log_{3}2^{x+3}=\log_{3} 2^{101x}.&lt;/math&gt; We remove the base 3 logarithm and the power of 2 to yield &lt;math&gt;x+3=101x,&lt;/math&gt; or &lt;math&gt;x=\dfrac{3}{100}.&lt;/math&gt;<br /> <br /> Our answer is &lt;math&gt;\boxed{3+100=103}.&lt;/math&gt;<br /> ~ OreoChocolate<br /> <br /> ==Solution 3 (Official MAA)==<br /> Using the Change of Base Formula to convert the logarithms in the given equation to base &lt;math&gt;2&lt;/math&gt; yields<br /> &lt;cmath&gt;\frac{\log_2 3^{20}}{\log_2 2^x} = \frac{\log_2 3^{2020}}{\log_2 2^{x+3}}, \text{~ and then ~}<br /> \frac{20\log_2 3}{x\cdot\log_2 2} = \frac{2020\log_2 3}{(x+3)\log_2 2}.&lt;/cmath&gt;Canceling the logarithm factors then yields&lt;cmath&gt;\frac{20}x = \frac{2020}{x+3},&lt;/cmath&gt;which has solution &lt;math&gt;x = \frac3{100}.&lt;/math&gt; The requested sum is &lt;math&gt;3 + 100 = 103&lt;/math&gt;.<br /> <br /> ==Video Solution==<br /> https://youtu.be/lPr4fYEoXi0 ~ CNCM<br /> ==Video Solution 2==<br /> https://www.youtube.com/watch?v=x0QznvXcwHY?t=528<br /> <br /> ~IceMatrix<br /> <br /> ==Video Solution 3==<br /> <br /> https://youtu.be/-CkEF5nWOaI <br /> <br /> ~avn<br /> <br /> ==See Also==<br /> {{AIME box|year=2020|n=II|num-b=2|num-a=4}}<br /> [[Category:Intermediate Algebra Problems]]<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_II_Problems/Problem_2&diff=124944 2020 AIME II Problems/Problem 2 2020-06-11T05:18:05Z <p>Avn: /* Video Solution */</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;P&lt;/math&gt; be a point chosen uniformly at random in the interior of the unit square with vertices at &lt;math&gt;(0,0), (1,0), (1,1)&lt;/math&gt;, and &lt;math&gt;(0,1)&lt;/math&gt;. The probability that the slope of the line determined by &lt;math&gt;P&lt;/math&gt; and the point &lt;math&gt;\left(\frac58, \frac38 \right)&lt;/math&gt; is greater than &lt;math&gt;\frac12&lt;/math&gt; can be written as &lt;math&gt;\frac{m}{n}&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m+n&lt;/math&gt;.<br /> <br /> ==Solution==<br /> The areas bounded by the unit square and alternately bounded by the lines through &lt;math&gt;\left(\frac{5}{8},\frac{3}{8}\right)&lt;/math&gt; that are vertical or have a slope of &lt;math&gt;1/2&lt;/math&gt; show where &lt;math&gt;P&lt;/math&gt; can be placed to satisfy the condition. One of the areas is a trapezoid with bases &lt;math&gt;1/16&lt;/math&gt; and &lt;math&gt;3/8&lt;/math&gt; and height &lt;math&gt;5/8&lt;/math&gt;. The other area is a trapezoid with bases &lt;math&gt;7/16&lt;/math&gt; and &lt;math&gt;5/8&lt;/math&gt; and height &lt;math&gt;3/8&lt;/math&gt;. Then, &lt;cmath&gt;\frac{\frac{1}{16}+\frac{3}{8}}{2}\cdot\frac{5}{8}+\frac{\frac{7}{16}+\frac{5}{8}}{2}\cdot\frac{3}{8}=\frac{86}{256}=\frac{43}{128}\implies43+128=\boxed{171}&lt;/cmath&gt;<br /> ~mn28407<br /> <br /> ==Solution 2 (Official MAA)==<br /> The line through the fixed point &lt;math&gt;\left(\frac58,\frac38\right)&lt;/math&gt; with slope &lt;math&gt;\frac12&lt;/math&gt; has equation &lt;math&gt;y=\frac12 x + \frac1{16}&lt;/math&gt;. The slope between &lt;math&gt;P&lt;/math&gt; and the fixed point exceeds &lt;math&gt;\frac12&lt;/math&gt; if &lt;math&gt;P&lt;/math&gt; falls within the shaded region in the diagram below consisting of two trapezoids with area<br /> &lt;cmath&gt;\frac{\frac1{16}+\frac38}2\cdot\frac58 + \frac{\frac58+\frac7{16}}2\cdot\frac38 = \frac{43}{128}.&lt;/cmath&gt;Because the entire square has area &lt;math&gt;1,&lt;/math&gt; the required probability is &lt;math&gt;\frac{43}{128}&lt;/math&gt;. The requested sum is &lt;math&gt;43+128 = 171&lt;/math&gt;.<br /> &lt;asy&gt;<br /> defaultpen(fontsize(8pt));<br /> unitsize(4cm);<br /> pair A = (0,0); <br /> pair B = (1,0); <br /> pair C = (1,1); <br /> pair D = (0,1);<br /> <br /> pair F = (0, 1/16); <br /> pair G = (1, 9/16); <br /> pair H = (5/8, 0); <br /> pair J = (5/8, 1); <br /> pair K = IP(H--J, F--G); <br /> <br /> pair P = (13/16, 12/16); <br /> pair Q = extension(P,K,A,B); <br /> pair R = extension(K,P,C,D);<br /> <br /> draw(A--B--C--D--cycle); <br /> <br /> label(&quot;$(0,0)$&quot;, A, SW); <br /> label(&quot;$(1,0)$&quot;, B, SE); <br /> label(&quot;$(1,1)$&quot;, C, E); <br /> label(&quot;$(0,1)$&quot;, D, W);<br /> <br /> filldraw(A--H--K--F--cycle, lightgray); <br /> filldraw(K--G--C--J--cycle, lightgray);<br /> <br /> dot(K); <br /> dot(&quot;$P$&quot;, P, W); <br /> draw(Q -- R, dashed);<br /> <br /> label(&quot;$\frac 38$&quot;, H--K, E);<br /> label(&quot;$\frac 58$&quot;, K--J, W); <br /> label(&quot;$\frac 7{16}$&quot;, G--C, E); <br /> label(&quot;$\frac 38$&quot;, C--J, N); <br /> label(&quot;$\frac 1{16}$&quot;, A--F, dir(160));<br /> <br /> &lt;/asy&gt;<br /> <br /> ==Video Solution==<br /> https://youtu.be/x0QznvXcwHY?t=190<br /> <br /> ~IceMatrix<br /> <br /> <br /> ==Video Solution 2==<br /> https://youtu.be/VBwlVbM0GRw <br /> <br /> ~avn<br /> <br /> ==See Also==<br /> {{AIME box|year=2020|n=II|num-b=1|num-a=3}}<br /> [[Category:Intermediate Geometry Problems]]<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_II_Problems/Problem_2&diff=124943 2020 AIME II Problems/Problem 2 2020-06-11T05:17:55Z <p>Avn: /* Video Solution */</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;P&lt;/math&gt; be a point chosen uniformly at random in the interior of the unit square with vertices at &lt;math&gt;(0,0), (1,0), (1,1)&lt;/math&gt;, and &lt;math&gt;(0,1)&lt;/math&gt;. The probability that the slope of the line determined by &lt;math&gt;P&lt;/math&gt; and the point &lt;math&gt;\left(\frac58, \frac38 \right)&lt;/math&gt; is greater than &lt;math&gt;\frac12&lt;/math&gt; can be written as &lt;math&gt;\frac{m}{n}&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m+n&lt;/math&gt;.<br /> <br /> ==Solution==<br /> The areas bounded by the unit square and alternately bounded by the lines through &lt;math&gt;\left(\frac{5}{8},\frac{3}{8}\right)&lt;/math&gt; that are vertical or have a slope of &lt;math&gt;1/2&lt;/math&gt; show where &lt;math&gt;P&lt;/math&gt; can be placed to satisfy the condition. One of the areas is a trapezoid with bases &lt;math&gt;1/16&lt;/math&gt; and &lt;math&gt;3/8&lt;/math&gt; and height &lt;math&gt;5/8&lt;/math&gt;. The other area is a trapezoid with bases &lt;math&gt;7/16&lt;/math&gt; and &lt;math&gt;5/8&lt;/math&gt; and height &lt;math&gt;3/8&lt;/math&gt;. Then, &lt;cmath&gt;\frac{\frac{1}{16}+\frac{3}{8}}{2}\cdot\frac{5}{8}+\frac{\frac{7}{16}+\frac{5}{8}}{2}\cdot\frac{3}{8}=\frac{86}{256}=\frac{43}{128}\implies43+128=\boxed{171}&lt;/cmath&gt;<br /> ~mn28407<br /> <br /> ==Solution 2 (Official MAA)==<br /> The line through the fixed point &lt;math&gt;\left(\frac58,\frac38\right)&lt;/math&gt; with slope &lt;math&gt;\frac12&lt;/math&gt; has equation &lt;math&gt;y=\frac12 x + \frac1{16}&lt;/math&gt;. The slope between &lt;math&gt;P&lt;/math&gt; and the fixed point exceeds &lt;math&gt;\frac12&lt;/math&gt; if &lt;math&gt;P&lt;/math&gt; falls within the shaded region in the diagram below consisting of two trapezoids with area<br /> &lt;cmath&gt;\frac{\frac1{16}+\frac38}2\cdot\frac58 + \frac{\frac58+\frac7{16}}2\cdot\frac38 = \frac{43}{128}.&lt;/cmath&gt;Because the entire square has area &lt;math&gt;1,&lt;/math&gt; the required probability is &lt;math&gt;\frac{43}{128}&lt;/math&gt;. The requested sum is &lt;math&gt;43+128 = 171&lt;/math&gt;.<br /> &lt;asy&gt;<br /> defaultpen(fontsize(8pt));<br /> unitsize(4cm);<br /> pair A = (0,0); <br /> pair B = (1,0); <br /> pair C = (1,1); <br /> pair D = (0,1);<br /> <br /> pair F = (0, 1/16); <br /> pair G = (1, 9/16); <br /> pair H = (5/8, 0); <br /> pair J = (5/8, 1); <br /> pair K = IP(H--J, F--G); <br /> <br /> pair P = (13/16, 12/16); <br /> pair Q = extension(P,K,A,B); <br /> pair R = extension(K,P,C,D);<br /> <br /> draw(A--B--C--D--cycle); <br /> <br /> label(&quot;$(0,0)$&quot;, A, SW); <br /> label(&quot;$(1,0)$&quot;, B, SE); <br /> label(&quot;$(1,1)$&quot;, C, E); <br /> label(&quot;$(0,1)$&quot;, D, W);<br /> <br /> filldraw(A--H--K--F--cycle, lightgray); <br /> filldraw(K--G--C--J--cycle, lightgray);<br /> <br /> dot(K); <br /> dot(&quot;$P$&quot;, P, W); <br /> draw(Q -- R, dashed);<br /> <br /> label(&quot;$\frac 38$&quot;, H--K, E);<br /> label(&quot;$\frac 58$&quot;, K--J, W); <br /> label(&quot;$\frac 7{16}$&quot;, G--C, E); <br /> label(&quot;$\frac 38$&quot;, C--J, N); <br /> label(&quot;$\frac 1{16}$&quot;, A--F, dir(160));<br /> <br /> &lt;/asy&gt;<br /> <br /> ==Video Solution==<br /> https://youtu.be/x0QznvXcwHY?t=190<br /> <br /> ~IceMatrix<br /> <br /> <br /> ==Video Solution==<br /> https://youtu.be/VBwlVbM0GRw <br /> <br /> ~avn<br /> <br /> ==See Also==<br /> {{AIME box|year=2020|n=II|num-b=1|num-a=3}}<br /> [[Category:Intermediate Geometry Problems]]<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_II_Problems/Problem_1&diff=124933 2020 AIME II Problems/Problem 1 2020-06-11T03:33:10Z <p>Avn: /* Video Solution */</p> <hr /> <div>==Problem==<br /> Find the number of ordered pairs of positive integers &lt;math&gt;(m,n)&lt;/math&gt; such that &lt;math&gt;{m^2n = 20 ^{20}}&lt;/math&gt;.<br /> <br /> ==Solution==<br /> First, we find the prime factorization of &lt;math&gt;20^{20}&lt;/math&gt;, which is &lt;math&gt;2^{40}\times5^{20}&lt;/math&gt;. The equation &lt;math&gt;{m^2n = 20 ^{20}}&lt;/math&gt; tells us that we want to select a perfect square factor of &lt;math&gt;20^{20}&lt;/math&gt;, &lt;math&gt;m^2&lt;/math&gt;. &lt;math&gt;n&lt;/math&gt; will be assigned by default. There are &lt;math&gt;21\times11=231&lt;/math&gt; ways to select a perfect square factor of &lt;math&gt;20^{20}&lt;/math&gt;, thus our answer is &lt;math&gt;\boxed{231}&lt;/math&gt;.<br /> <br /> ~superagh<br /> &lt;br&gt;&lt;br&gt;<br /> <br /> ==Solution 2 (Official MAA)==<br /> Because &lt;math&gt;20^{20}=2^{40}5^{20}&lt;/math&gt;, if &lt;math&gt;m^2n = 20^{20}&lt;/math&gt;, there must be nonnegative integers &lt;math&gt;a&lt;/math&gt;, &lt;math&gt;b&lt;/math&gt;, &lt;math&gt;c&lt;/math&gt;, and &lt;math&gt;d&lt;/math&gt; such that<br /> &lt;math&gt;m = 2^a5^b&lt;/math&gt; and &lt;math&gt;n = 2^c5^d&lt;/math&gt;. Then<br /> &lt;cmath&gt;2a + c = 40&lt;/cmath&gt;<br /> and<br /> &lt;cmath&gt;2b+d = 20&lt;/cmath&gt;<br /> The first equation has &lt;math&gt;21&lt;/math&gt; solutions corresponding to &lt;math&gt;a = 0,1,2,\dots,20&lt;/math&gt;, and the second equation has &lt;math&gt;11&lt;/math&gt; solutions corresponding to &lt;math&gt;b = 0,1,2,\dots,10&lt;/math&gt;. Therefore there are a total of &lt;math&gt;21\cdot11 = 231&lt;/math&gt; ordered pairs &lt;math&gt;(m,n)&lt;/math&gt; such that &lt;math&gt;m^2n = 20^{20}&lt;/math&gt;.<br /> <br /> <br /> ==Video Solution==<br /> https://www.youtube.com/watch?v=x0QznvXcwHY<br /> <br /> ~IceMatrix<br /> <br /> <br /> ==Video Solution 2==<br /> <br /> https://youtu.be/Va3MPyAULdU <br /> <br /> ~avn<br /> <br /> ==See Also==<br /> {{AIME box|year=2020|n=II|before=First Problem|num-a=2}}<br /> [[Category:Introductory Number Theory Problems]]<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_II_Problems/Problem_1&diff=124932 2020 AIME II Problems/Problem 1 2020-06-11T03:32:43Z <p>Avn: /* Video Solution 2 */</p> <hr /> <div>==Problem==<br /> Find the number of ordered pairs of positive integers &lt;math&gt;(m,n)&lt;/math&gt; such that &lt;math&gt;{m^2n = 20 ^{20}}&lt;/math&gt;.<br /> <br /> ==Solution==<br /> First, we find the prime factorization of &lt;math&gt;20^{20}&lt;/math&gt;, which is &lt;math&gt;2^{40}\times5^{20}&lt;/math&gt;. The equation &lt;math&gt;{m^2n = 20 ^{20}}&lt;/math&gt; tells us that we want to select a perfect square factor of &lt;math&gt;20^{20}&lt;/math&gt;, &lt;math&gt;m^2&lt;/math&gt;. &lt;math&gt;n&lt;/math&gt; will be assigned by default. There are &lt;math&gt;21\times11=231&lt;/math&gt; ways to select a perfect square factor of &lt;math&gt;20^{20}&lt;/math&gt;, thus our answer is &lt;math&gt;\boxed{231}&lt;/math&gt;.<br /> <br /> ~superagh<br /> &lt;br&gt;&lt;br&gt;<br /> <br /> ==Solution 2 (Official MAA)==<br /> Because &lt;math&gt;20^{20}=2^{40}5^{20}&lt;/math&gt;, if &lt;math&gt;m^2n = 20^{20}&lt;/math&gt;, there must be nonnegative integers &lt;math&gt;a&lt;/math&gt;, &lt;math&gt;b&lt;/math&gt;, &lt;math&gt;c&lt;/math&gt;, and &lt;math&gt;d&lt;/math&gt; such that<br /> &lt;math&gt;m = 2^a5^b&lt;/math&gt; and &lt;math&gt;n = 2^c5^d&lt;/math&gt;. Then<br /> &lt;cmath&gt;2a + c = 40&lt;/cmath&gt;<br /> and<br /> &lt;cmath&gt;2b+d = 20&lt;/cmath&gt;<br /> The first equation has &lt;math&gt;21&lt;/math&gt; solutions corresponding to &lt;math&gt;a = 0,1,2,\dots,20&lt;/math&gt;, and the second equation has &lt;math&gt;11&lt;/math&gt; solutions corresponding to &lt;math&gt;b = 0,1,2,\dots,10&lt;/math&gt;. Therefore there are a total of &lt;math&gt;21\cdot11 = 231&lt;/math&gt; ordered pairs &lt;math&gt;(m,n)&lt;/math&gt; such that &lt;math&gt;m^2n = 20^{20}&lt;/math&gt;.<br /> <br /> <br /> ==Video Solution==<br /> https://www.youtube.com/watch?v=x0QznvXcwHY<br /> <br /> ~IceMatrix<br /> <br /> ==See Also==<br /> {{AIME box|year=2020|n=II|before=First Problem|num-a=2}}<br /> [[Category:Introductory Number Theory Problems]]<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_II_Problems/Problem_1&diff=124930 2020 AIME II Problems/Problem 1 2020-06-11T03:32:18Z <p>Avn: /* Solution 2 (Official MAA) */</p> <hr /> <div>==Problem==<br /> Find the number of ordered pairs of positive integers &lt;math&gt;(m,n)&lt;/math&gt; such that &lt;math&gt;{m^2n = 20 ^{20}}&lt;/math&gt;.<br /> <br /> ==Solution==<br /> First, we find the prime factorization of &lt;math&gt;20^{20}&lt;/math&gt;, which is &lt;math&gt;2^{40}\times5^{20}&lt;/math&gt;. The equation &lt;math&gt;{m^2n = 20 ^{20}}&lt;/math&gt; tells us that we want to select a perfect square factor of &lt;math&gt;20^{20}&lt;/math&gt;, &lt;math&gt;m^2&lt;/math&gt;. &lt;math&gt;n&lt;/math&gt; will be assigned by default. There are &lt;math&gt;21\times11=231&lt;/math&gt; ways to select a perfect square factor of &lt;math&gt;20^{20}&lt;/math&gt;, thus our answer is &lt;math&gt;\boxed{231}&lt;/math&gt;.<br /> <br /> ~superagh<br /> &lt;br&gt;&lt;br&gt;<br /> <br /> ==Solution 2 (Official MAA)==<br /> Because &lt;math&gt;20^{20}=2^{40}5^{20}&lt;/math&gt;, if &lt;math&gt;m^2n = 20^{20}&lt;/math&gt;, there must be nonnegative integers &lt;math&gt;a&lt;/math&gt;, &lt;math&gt;b&lt;/math&gt;, &lt;math&gt;c&lt;/math&gt;, and &lt;math&gt;d&lt;/math&gt; such that<br /> &lt;math&gt;m = 2^a5^b&lt;/math&gt; and &lt;math&gt;n = 2^c5^d&lt;/math&gt;. Then<br /> &lt;cmath&gt;2a + c = 40&lt;/cmath&gt;<br /> and<br /> &lt;cmath&gt;2b+d = 20&lt;/cmath&gt;<br /> The first equation has &lt;math&gt;21&lt;/math&gt; solutions corresponding to &lt;math&gt;a = 0,1,2,\dots,20&lt;/math&gt;, and the second equation has &lt;math&gt;11&lt;/math&gt; solutions corresponding to &lt;math&gt;b = 0,1,2,\dots,10&lt;/math&gt;. Therefore there are a total of &lt;math&gt;21\cdot11 = 231&lt;/math&gt; ordered pairs &lt;math&gt;(m,n)&lt;/math&gt; such that &lt;math&gt;m^2n = 20^{20}&lt;/math&gt;.<br /> <br /> <br /> ==Video Solution 2==<br /> <br /> https://youtu.be/Va3MPyAULdU <br /> <br /> ~avn<br /> <br /> ==Video Solution==<br /> https://www.youtube.com/watch?v=x0QznvXcwHY<br /> <br /> ~IceMatrix<br /> <br /> ==See Also==<br /> {{AIME box|year=2020|n=II|before=First Problem|num-a=2}}<br /> [[Category:Introductory Number Theory Problems]]<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=Combinatorial_identity&diff=124655 Combinatorial identity 2020-06-09T21:38:17Z <p>Avn: /* Vandermonde's Identity */</p> <hr /> <div>==Vandermonde's Identity==<br /> Vandermonde's Identity states that &lt;math&gt;\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r&lt;/math&gt;, which can be proven combinatorially by noting that any combination of &lt;math&gt;r&lt;/math&gt; objects from a group of &lt;math&gt;m+n&lt;/math&gt; objects must have some &lt;math&gt;0\le k\le r&lt;/math&gt; objects from group &lt;math&gt;m&lt;/math&gt; and the remaining from group &lt;math&gt;n&lt;/math&gt;.<br /> <br /> ===Video Proof=== <br /> <br /> https://www.youtube.com/watch?v=u1fktz9U9ig<br /> <br /> ~avn<br /> <br /> ==Hockey-Stick Identity==<br /> For &lt;math&gt;n,r\in\mathbb{N}, n&gt;r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}&lt;/math&gt;.<br /> <br /> &lt;asy&gt;<br /> int chew(int n,int r){<br /> int res=1;<br /> for(int i=0;i&lt;r;++i){<br /> res=quotient(res*(n-i),i+1);<br /> }<br /> return res;<br /> }<br /> for(int n=0;n&lt;9;++n){<br /> for(int i=0;i&lt;=n;++i){<br /> if((i==2 &amp;&amp; n&lt;8)||(i==3 &amp;&amp; n==8)){<br /> if(n==8){label(string(chew(n,i)),(11+n/2-i,-n),p=red+2.5);}<br /> else{label(string(chew(n,i)),(11+n/2-i,-n),p=blue+2);}<br /> }<br /> else{<br /> label(string(chew(n,i)),(11+n/2-i,-n));<br /> }<br /> }<br /> }<br /> &lt;/asy&gt;<br /> <br /> This identity is known as the ''hockey-stick'' identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself is highlighted, a hockey-stick shape is revealed.<br /> <br /> <br /> ===Proof===<br /> <br /> '''Inductive Proof'''<br /> <br /> This identity can be proven by induction on &lt;math&gt;n&lt;/math&gt;.<br /> <br /> &lt;u&gt;Base Case&lt;/u&gt;<br /> Let &lt;math&gt;n=r&lt;/math&gt;.<br /> <br /> &lt;math&gt;\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}&lt;/math&gt;.<br /> <br /> &lt;u&gt;Inductive Step&lt;/u&gt;<br /> Suppose, for some &lt;math&gt;k\in\mathbb{N}, k&gt;r&lt;/math&gt;, &lt;math&gt;\sum^k_{i=r}{i\choose r}={k+1\choose r+1}&lt;/math&gt;.<br /> Then &lt;math&gt;\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}&lt;/math&gt;.<br /> <br /> '''Algebraic Proof'''<br /> <br /> It can also be proven algebraically with [[Pascal's Identity]], &lt;math&gt;{n \choose k}={n-1\choose k-1}+{n-1\choose k}&lt;/math&gt;.<br /> Note that<br /> <br /> &lt;math&gt;{r \choose r}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}&lt;/math&gt;<br /> &lt;math&gt;={r+1 \choose r+1}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}&lt;/math&gt;<br /> &lt;math&gt;={r+2 \choose r+1}+{r+2 \choose r}+\cdots+{r+a \choose r}=\cdots={r+a \choose r+1}+{r+a \choose r}={r+a+1 \choose r+1}&lt;/math&gt;, which is equivalent to the desired result.<br /> <br /> '''Combinatorial Proof 1'''<br /> <br /> Imagine that we are distributing &lt;math&gt;n&lt;/math&gt; indistinguishable candies to &lt;math&gt;k&lt;/math&gt; distinguishable children. By a direct application of Balls and Urns, there are &lt;math&gt;{n+k-1\choose k-1}&lt;/math&gt; ways to do this. Alternatively, we can first give &lt;math&gt;0\le i\le n&lt;/math&gt; candies to the oldest child so that we are essentially giving &lt;math&gt;n-i&lt;/math&gt; candies to &lt;math&gt;k-1&lt;/math&gt; kids and again, with Balls and Urns, &lt;math&gt;{n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}&lt;/math&gt;, which simplifies to the desired result.<br /> <br /> '''Combinatorial Proof 2'''<br /> <br /> We can form a committee of size &lt;math&gt;k+1&lt;/math&gt; from a group of &lt;math&gt;n+1&lt;/math&gt; people in &lt;math&gt;{{n+1}\choose{k+1}}&lt;/math&gt; ways. Now we hand out the numbers &lt;math&gt;1,2,3,\dots,n-k+1&lt;/math&gt; to &lt;math&gt;n-k+1&lt;/math&gt; of the &lt;math&gt;n+1&lt;/math&gt; people. We can divide this into &lt;math&gt;n-k+1&lt;/math&gt; disjoint cases. In general, in case &lt;math&gt;x&lt;/math&gt;, &lt;math&gt;1\le x\le n-k+1&lt;/math&gt;, person &lt;math&gt;x&lt;/math&gt; is on the committee and persons &lt;math&gt;1,2,3,\dots, x-1&lt;/math&gt; are not on the committee. This can be done in &lt;math&gt;\binom{n-x+1}{k}&lt;/math&gt; ways. Now we can sum the values of these &lt;math&gt;n-k+1&lt;/math&gt; disjoint cases, getting &lt;cmath&gt;{{n+1}\choose {k+1}} ={{n}\choose{k}}+{{n-1}\choose{k}}+{{n-2}\choose{k}}+\hdots+{{k+1}\choose{k}}+{{k}\choose{k}}.&lt;/cmath&gt;<br /> <br /> '''Algebraic Proof 2'''<br /> <br /> Apply the finite geometric series formula to &lt;math&gt;(1+x)&lt;/math&gt;: &lt;cmath&gt;1+(1+x)+(1+x)^2+...+(1+x)^n=\frac{(1+x)^{n+1}-1}{(1+x)-1}&lt;/cmath&gt; Then expand with the Binomial Theorem and simplify: &lt;cmath&gt;1+(1+x)+(1+2x+x^2)+...+(\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n-1}x^{n-1}+\binom{n}{n}x^n)=\binom{n+1}{1}+\binom{n+1}{2}x+...+\binom{n+1}{n+1}x^n&lt;/cmath&gt; Finally, equate coefficients of &lt;math&gt;x^m&lt;/math&gt; on both sides: &lt;cmath&gt;\binom{0}{m}+\binom{1}{m}+\binom{2}{m}+...+\binom{n}{m}=\binom{n+1}{m+1}&lt;/cmath&gt; Since for &lt;math&gt;i&lt;m&lt;/math&gt;, &lt;math&gt;\binom{i}{m}=0&lt;/math&gt;, this simplifies to the hockey stick identity. -- EVIN-<br /> <br /> ==Another Identity==<br /> <br /> &lt;cmath&gt;<br /> \sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}<br /> &lt;/cmath&gt;<br /> <br /> ===Hat Proof===<br /> We have &lt;math&gt;2k&lt;/math&gt; different hats. We split them into two groups, each with k hats: then we choose &lt;math&gt;i&lt;/math&gt; hats from the first group and &lt;math&gt;k-i&lt;/math&gt; hats from the second group. This may be done in &lt;math&gt;\binom{k}{i}^2&lt;/math&gt; ways. Evidently, to generate all possible choices of &lt;math&gt;k&lt;/math&gt; hats from the &lt;math&gt;2k&lt;/math&gt; hats, we must choose &lt;math&gt;i=0,1,\cdots,k&lt;/math&gt; hats from the first &lt;math&gt;k&lt;/math&gt; and the remaining &lt;math&gt;k-i&lt;/math&gt; hats from the second &lt;math&gt;k&lt;/math&gt;; the sum over all such &lt;math&gt;i&lt;/math&gt; is the number of ways of choosing &lt;math&gt;k&lt;/math&gt; hats from &lt;math&gt;2k&lt;/math&gt;. Therefore &lt;math&gt;\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}&lt;/math&gt;, as desired.<br /> <br /> ===Proof 2===<br /> This is a special case of Vandermonde's identity, in which we set &lt;math&gt;m=n&lt;/math&gt; and &lt;math&gt;r=m&lt;/math&gt;.<br /> <br /> <br /> == Examples ==<br /> * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=394407#394407 1986 AIME Problem 11]<br /> * [http://www.artofproblemsolving.com/Forum/resources.php?c=182&amp;cid=45&amp;year=2000&amp;p=385891 2000 AIME II Problem 7]<br /> * [https://artofproblemsolving.com/wiki/index.php?title=2013_AIME_I_Problems/Problem_6#Solution_Two 2013 AIME II Problem 6 (Solution 2)]<br /> * [http://artofproblemsolving.com/wiki/index.php/2015_AIME_I_Problems/Problem_12 2015 AIME I Problem 12]<br /> * [https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems/Problem_7 2020 AIME I Problem 7]<br /> <br /> ==See also==<br /> * [[Pascal's Triangle]]<br /> * [[Combinatorics]]<br /> <br /> [[Category:Theorems]]<br /> <br /> [[Category:Combinatorics]]</div> Avn https://artofproblemsolving.com/wiki/index.php?title=Combinatorial_identity&diff=124622 Combinatorial identity 2020-06-09T18:53:15Z <p>Avn: /* Vandermonde's Identity */</p> <hr /> <div>==Vandermonde's Identity==<br /> Vandermonde's Identity states that &lt;math&gt;\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r&lt;/math&gt;, which can be proven combinatorially by noting that any combination of &lt;math&gt;r&lt;/math&gt; objects from a group of &lt;math&gt;m+n&lt;/math&gt; objects must have some &lt;math&gt;0\le k\le r&lt;/math&gt; objects from group &lt;math&gt;m&lt;/math&gt; and the remaining from group &lt;math&gt;n&lt;/math&gt;.<br /> <br /> Video Proof: <br /> <br /> https://www.youtube.com/watch?v=u1fktz9U9ig<br /> <br /> ~avn<br /> <br /> ==Hockey-Stick Identity==<br /> For &lt;math&gt;n,r\in\mathbb{N}, n&gt;r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}&lt;/math&gt;.<br /> <br /> &lt;asy&gt;<br /> int chew(int n,int r){<br /> int res=1;<br /> for(int i=0;i&lt;r;++i){<br /> res=quotient(res*(n-i),i+1);<br /> }<br /> return res;<br /> }<br /> for(int n=0;n&lt;9;++n){<br /> for(int i=0;i&lt;=n;++i){<br /> if((i==2 &amp;&amp; n&lt;8)||(i==3 &amp;&amp; n==8)){<br /> if(n==8){label(string(chew(n,i)),(11+n/2-i,-n),p=red+2.5);}<br /> else{label(string(chew(n,i)),(11+n/2-i,-n),p=blue+2);}<br /> }<br /> else{<br /> label(string(chew(n,i)),(11+n/2-i,-n));<br /> }<br /> }<br /> }<br /> &lt;/asy&gt;<br /> <br /> This identity is known as the ''hockey-stick'' identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself is highlighted, a hockey-stick shape is revealed.<br /> <br /> <br /> ===Proof===<br /> <br /> '''Inductive Proof'''<br /> <br /> This identity can be proven by induction on &lt;math&gt;n&lt;/math&gt;.<br /> <br /> &lt;u&gt;Base Case&lt;/u&gt;<br /> Let &lt;math&gt;n=r&lt;/math&gt;.<br /> <br /> &lt;math&gt;\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}&lt;/math&gt;.<br /> <br /> &lt;u&gt;Inductive Step&lt;/u&gt;<br /> Suppose, for some &lt;math&gt;k\in\mathbb{N}, k&gt;r&lt;/math&gt;, &lt;math&gt;\sum^k_{i=r}{i\choose r}={k+1\choose r+1}&lt;/math&gt;.<br /> Then &lt;math&gt;\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}&lt;/math&gt;.<br /> <br /> '''Algebraic Proof'''<br /> <br /> It can also be proven algebraically with [[Pascal's Identity]], &lt;math&gt;{n \choose k}={n-1\choose k-1}+{n-1\choose k}&lt;/math&gt;.<br /> Note that<br /> <br /> &lt;math&gt;{r \choose r}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}&lt;/math&gt;<br /> &lt;math&gt;={r+1 \choose r+1}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}&lt;/math&gt;<br /> &lt;math&gt;={r+2 \choose r+1}+{r+2 \choose r}+\cdots+{r+a \choose r}=\cdots={r+a \choose r+1}+{r+a \choose r}={r+a+1 \choose r+1}&lt;/math&gt;, which is equivalent to the desired result.<br /> <br /> '''Combinatorial Proof 1'''<br /> <br /> Imagine that we are distributing &lt;math&gt;n&lt;/math&gt; indistinguishable candies to &lt;math&gt;k&lt;/math&gt; distinguishable children. By a direct application of Balls and Urns, there are &lt;math&gt;{n+k-1\choose k-1}&lt;/math&gt; ways to do this. Alternatively, we can first give &lt;math&gt;0\le i\le n&lt;/math&gt; candies to the oldest child so that we are essentially giving &lt;math&gt;n-i&lt;/math&gt; candies to &lt;math&gt;k-1&lt;/math&gt; kids and again, with Balls and Urns, &lt;math&gt;{n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}&lt;/math&gt;, which simplifies to the desired result.<br /> <br /> '''Combinatorial Proof 2'''<br /> <br /> We can form a committee of size &lt;math&gt;k+1&lt;/math&gt; from a group of &lt;math&gt;n+1&lt;/math&gt; people in &lt;math&gt;{{n+1}\choose{k+1}}&lt;/math&gt; ways. Now we hand out the numbers &lt;math&gt;1,2,3,\dots,n-k+1&lt;/math&gt; to &lt;math&gt;n-k+1&lt;/math&gt; of the &lt;math&gt;n+1&lt;/math&gt; people. We can divide this into &lt;math&gt;n-k+1&lt;/math&gt; disjoint cases. In general, in case &lt;math&gt;x&lt;/math&gt;, &lt;math&gt;1\le x\le n-k+1&lt;/math&gt;, person &lt;math&gt;x&lt;/math&gt; is on the committee and persons &lt;math&gt;1,2,3,\dots, x-1&lt;/math&gt; are not on the committee. This can be done in &lt;math&gt;\binom{n-x+1}{k}&lt;/math&gt; ways. Now we can sum the values of these &lt;math&gt;n-k+1&lt;/math&gt; disjoint cases, getting &lt;cmath&gt;{{n+1}\choose {k+1}} ={{n}\choose{k}}+{{n-1}\choose{k}}+{{n-2}\choose{k}}+\hdots+{{k+1}\choose{k}}+{{k}\choose{k}}.&lt;/cmath&gt;<br /> <br /> '''Algebraic Proof 2'''<br /> <br /> Apply the finite geometric series formula to &lt;math&gt;(1+x)&lt;/math&gt;: &lt;cmath&gt;1+(1+x)+(1+x)^2+...+(1+x)^n=\frac{(1+x)^{n+1}-1}{(1+x)-1}&lt;/cmath&gt; Then expand with the Binomial Theorem and simplify: &lt;cmath&gt;1+(1+x)+(1+2x+x^2)+...+(\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n-1}x^{n-1}+\binom{n}{n}x^n)=\binom{n+1}{1}+\binom{n+1}{2}x+...+\binom{n+1}{n+1}x^n&lt;/cmath&gt; Finally, equate coefficients of &lt;math&gt;x^m&lt;/math&gt; on both sides: &lt;cmath&gt;\binom{0}{m}+\binom{1}{m}+\binom{2}{m}+...+\binom{n}{m}=\binom{n+1}{m+1}&lt;/cmath&gt; Since for &lt;math&gt;i&lt;m&lt;/math&gt;, &lt;math&gt;\binom{i}{m}=0&lt;/math&gt;, this simplifies to the hockey stick identity. -- EVIN-<br /> <br /> ==Another Identity==<br /> <br /> &lt;cmath&gt;<br /> \sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}<br /> &lt;/cmath&gt;<br /> <br /> ===Hat Proof===<br /> We have &lt;math&gt;2k&lt;/math&gt; different hats. We split them into two groups, each with k hats: then we choose &lt;math&gt;i&lt;/math&gt; hats from the first group and &lt;math&gt;k-i&lt;/math&gt; hats from the second group. This may be done in &lt;math&gt;\binom{k}{i}^2&lt;/math&gt; ways. Evidently, to generate all possible choices of &lt;math&gt;k&lt;/math&gt; hats from the &lt;math&gt;2k&lt;/math&gt; hats, we must choose &lt;math&gt;i=0,1,\cdots,k&lt;/math&gt; hats from the first &lt;math&gt;k&lt;/math&gt; and the remaining &lt;math&gt;k-i&lt;/math&gt; hats from the second &lt;math&gt;k&lt;/math&gt;; the sum over all such &lt;math&gt;i&lt;/math&gt; is the number of ways of choosing &lt;math&gt;k&lt;/math&gt; hats from &lt;math&gt;2k&lt;/math&gt;. Therefore &lt;math&gt;\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}&lt;/math&gt;, as desired.<br /> <br /> ===Proof 2===<br /> This is a special case of Vandermonde's identity, in which we set &lt;math&gt;m=n&lt;/math&gt; and &lt;math&gt;r=m&lt;/math&gt;.<br /> <br /> <br /> == Examples ==<br /> * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=394407#394407 1986 AIME Problem 11]<br /> * [http://www.artofproblemsolving.com/Forum/resources.php?c=182&amp;cid=45&amp;year=2000&amp;p=385891 2000 AIME II Problem 7]<br /> * [https://artofproblemsolving.com/wiki/index.php?title=2013_AIME_I_Problems/Problem_6#Solution_Two 2013 AIME II Problem 6 (Solution 2)]<br /> * [http://artofproblemsolving.com/wiki/index.php/2015_AIME_I_Problems/Problem_12 2015 AIME I Problem 12]<br /> * [https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems/Problem_7 2020 AIME I Problem 7]<br /> <br /> ==See also==<br /> * [[Pascal's Triangle]]<br /> * [[Combinatorics]]<br /> <br /> [[Category:Theorems]]<br /> <br /> [[Category:Combinatorics]]</div> Avn https://artofproblemsolving.com/wiki/index.php?title=Combinatorial_identity&diff=124621 Combinatorial identity 2020-06-09T18:52:50Z <p>Avn: /* Vandermonde's Identity */</p> <hr /> <div>==Vandermonde's Identity==<br /> Vandermonde's Identity states that &lt;math&gt;\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r&lt;/math&gt;, which can be proven combinatorially by noting that any combination of &lt;math&gt;r&lt;/math&gt; objects from a group of &lt;math&gt;m+n&lt;/math&gt; objects must have some &lt;math&gt;0\le k\le r&lt;/math&gt; objects from group &lt;math&gt;m&lt;/math&gt; and the remaining from group &lt;math&gt;n&lt;/math&gt;.<br /> <br /> Video Proof: <br /> <br /> https://www.youtube.com/watch?v=u1fktz9U9ig<br /> <br /> ==Hockey-Stick Identity==<br /> For &lt;math&gt;n,r\in\mathbb{N}, n&gt;r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}&lt;/math&gt;.<br /> <br /> &lt;asy&gt;<br /> int chew(int n,int r){<br /> int res=1;<br /> for(int i=0;i&lt;r;++i){<br /> res=quotient(res*(n-i),i+1);<br /> }<br /> return res;<br /> }<br /> for(int n=0;n&lt;9;++n){<br /> for(int i=0;i&lt;=n;++i){<br /> if((i==2 &amp;&amp; n&lt;8)||(i==3 &amp;&amp; n==8)){<br /> if(n==8){label(string(chew(n,i)),(11+n/2-i,-n),p=red+2.5);}<br /> else{label(string(chew(n,i)),(11+n/2-i,-n),p=blue+2);}<br /> }<br /> else{<br /> label(string(chew(n,i)),(11+n/2-i,-n));<br /> }<br /> }<br /> }<br /> &lt;/asy&gt;<br /> <br /> This identity is known as the ''hockey-stick'' identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself is highlighted, a hockey-stick shape is revealed.<br /> <br /> <br /> ===Proof===<br /> <br /> '''Inductive Proof'''<br /> <br /> This identity can be proven by induction on &lt;math&gt;n&lt;/math&gt;.<br /> <br /> &lt;u&gt;Base Case&lt;/u&gt;<br /> Let &lt;math&gt;n=r&lt;/math&gt;.<br /> <br /> &lt;math&gt;\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}&lt;/math&gt;.<br /> <br /> &lt;u&gt;Inductive Step&lt;/u&gt;<br /> Suppose, for some &lt;math&gt;k\in\mathbb{N}, k&gt;r&lt;/math&gt;, &lt;math&gt;\sum^k_{i=r}{i\choose r}={k+1\choose r+1}&lt;/math&gt;.<br /> Then &lt;math&gt;\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}&lt;/math&gt;.<br /> <br /> '''Algebraic Proof'''<br /> <br /> It can also be proven algebraically with [[Pascal's Identity]], &lt;math&gt;{n \choose k}={n-1\choose k-1}+{n-1\choose k}&lt;/math&gt;.<br /> Note that<br /> <br /> &lt;math&gt;{r \choose r}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}&lt;/math&gt;<br /> &lt;math&gt;={r+1 \choose r+1}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}&lt;/math&gt;<br /> &lt;math&gt;={r+2 \choose r+1}+{r+2 \choose r}+\cdots+{r+a \choose r}=\cdots={r+a \choose r+1}+{r+a \choose r}={r+a+1 \choose r+1}&lt;/math&gt;, which is equivalent to the desired result.<br /> <br /> '''Combinatorial Proof 1'''<br /> <br /> Imagine that we are distributing &lt;math&gt;n&lt;/math&gt; indistinguishable candies to &lt;math&gt;k&lt;/math&gt; distinguishable children. By a direct application of Balls and Urns, there are &lt;math&gt;{n+k-1\choose k-1}&lt;/math&gt; ways to do this. Alternatively, we can first give &lt;math&gt;0\le i\le n&lt;/math&gt; candies to the oldest child so that we are essentially giving &lt;math&gt;n-i&lt;/math&gt; candies to &lt;math&gt;k-1&lt;/math&gt; kids and again, with Balls and Urns, &lt;math&gt;{n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}&lt;/math&gt;, which simplifies to the desired result.<br /> <br /> '''Combinatorial Proof 2'''<br /> <br /> We can form a committee of size &lt;math&gt;k+1&lt;/math&gt; from a group of &lt;math&gt;n+1&lt;/math&gt; people in &lt;math&gt;{{n+1}\choose{k+1}}&lt;/math&gt; ways. Now we hand out the numbers &lt;math&gt;1,2,3,\dots,n-k+1&lt;/math&gt; to &lt;math&gt;n-k+1&lt;/math&gt; of the &lt;math&gt;n+1&lt;/math&gt; people. We can divide this into &lt;math&gt;n-k+1&lt;/math&gt; disjoint cases. In general, in case &lt;math&gt;x&lt;/math&gt;, &lt;math&gt;1\le x\le n-k+1&lt;/math&gt;, person &lt;math&gt;x&lt;/math&gt; is on the committee and persons &lt;math&gt;1,2,3,\dots, x-1&lt;/math&gt; are not on the committee. This can be done in &lt;math&gt;\binom{n-x+1}{k}&lt;/math&gt; ways. Now we can sum the values of these &lt;math&gt;n-k+1&lt;/math&gt; disjoint cases, getting &lt;cmath&gt;{{n+1}\choose {k+1}} ={{n}\choose{k}}+{{n-1}\choose{k}}+{{n-2}\choose{k}}+\hdots+{{k+1}\choose{k}}+{{k}\choose{k}}.&lt;/cmath&gt;<br /> <br /> '''Algebraic Proof 2'''<br /> <br /> Apply the finite geometric series formula to &lt;math&gt;(1+x)&lt;/math&gt;: &lt;cmath&gt;1+(1+x)+(1+x)^2+...+(1+x)^n=\frac{(1+x)^{n+1}-1}{(1+x)-1}&lt;/cmath&gt; Then expand with the Binomial Theorem and simplify: &lt;cmath&gt;1+(1+x)+(1+2x+x^2)+...+(\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n-1}x^{n-1}+\binom{n}{n}x^n)=\binom{n+1}{1}+\binom{n+1}{2}x+...+\binom{n+1}{n+1}x^n&lt;/cmath&gt; Finally, equate coefficients of &lt;math&gt;x^m&lt;/math&gt; on both sides: &lt;cmath&gt;\binom{0}{m}+\binom{1}{m}+\binom{2}{m}+...+\binom{n}{m}=\binom{n+1}{m+1}&lt;/cmath&gt; Since for &lt;math&gt;i&lt;m&lt;/math&gt;, &lt;math&gt;\binom{i}{m}=0&lt;/math&gt;, this simplifies to the hockey stick identity. -- EVIN-<br /> <br /> ==Another Identity==<br /> <br /> &lt;cmath&gt;<br /> \sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}<br /> &lt;/cmath&gt;<br /> <br /> ===Hat Proof===<br /> We have &lt;math&gt;2k&lt;/math&gt; different hats. We split them into two groups, each with k hats: then we choose &lt;math&gt;i&lt;/math&gt; hats from the first group and &lt;math&gt;k-i&lt;/math&gt; hats from the second group. This may be done in &lt;math&gt;\binom{k}{i}^2&lt;/math&gt; ways. Evidently, to generate all possible choices of &lt;math&gt;k&lt;/math&gt; hats from the &lt;math&gt;2k&lt;/math&gt; hats, we must choose &lt;math&gt;i=0,1,\cdots,k&lt;/math&gt; hats from the first &lt;math&gt;k&lt;/math&gt; and the remaining &lt;math&gt;k-i&lt;/math&gt; hats from the second &lt;math&gt;k&lt;/math&gt;; the sum over all such &lt;math&gt;i&lt;/math&gt; is the number of ways of choosing &lt;math&gt;k&lt;/math&gt; hats from &lt;math&gt;2k&lt;/math&gt;. Therefore &lt;math&gt;\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}&lt;/math&gt;, as desired.<br /> <br /> ===Proof 2===<br /> This is a special case of Vandermonde's identity, in which we set &lt;math&gt;m=n&lt;/math&gt; and &lt;math&gt;r=m&lt;/math&gt;.<br /> <br /> <br /> == Examples ==<br /> * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=394407#394407 1986 AIME Problem 11]<br /> * [http://www.artofproblemsolving.com/Forum/resources.php?c=182&amp;cid=45&amp;year=2000&amp;p=385891 2000 AIME II Problem 7]<br /> * [https://artofproblemsolving.com/wiki/index.php?title=2013_AIME_I_Problems/Problem_6#Solution_Two 2013 AIME II Problem 6 (Solution 2)]<br /> * [http://artofproblemsolving.com/wiki/index.php/2015_AIME_I_Problems/Problem_12 2015 AIME I Problem 12]<br /> * [https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems/Problem_7 2020 AIME I Problem 7]<br /> <br /> ==See also==<br /> * [[Pascal's Triangle]]<br /> * [[Combinatorics]]<br /> <br /> [[Category:Theorems]]<br /> <br /> [[Category:Combinatorics]]</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_7&diff=124619 2020 AIME I Problems/Problem 7 2020-06-09T18:37:03Z <p>Avn: /* Solution 4 */</p> <hr /> <div><br /> == Problem ==<br /> A club consisting of &lt;math&gt;11&lt;/math&gt; men and &lt;math&gt;12&lt;/math&gt; women needs to choose a committee from among its members so that the number of women on the committee is one more than the number of men on the committee. The committee could have as few as &lt;math&gt;1&lt;/math&gt; member or as many as &lt;math&gt;23&lt;/math&gt; members. Let &lt;math&gt;N&lt;/math&gt; be the number of such committees that can be formed. Find the sum of the prime numbers that divide &lt;math&gt;N.&lt;/math&gt;<br /> <br /> == Solution 1 ==<br /> <br /> Let &lt;math&gt;k&lt;/math&gt; be the number of women selected. Then, the number of men not selected is &lt;math&gt;(11-(k-1)=12-k&lt;/math&gt;.<br /> Note that the sum of the number of women selected and the number of men not selected is constant at &lt;math&gt;12&lt;/math&gt;. Each combination of women selected and men not selected corresponds to a committee selection. Since choosing 12 individuals from the total of 23 would give &lt;math&gt;k&lt;/math&gt; women and &lt;math&gt;12-k&lt;/math&gt; men, the number of committee selections is &lt;math&gt;\binom{23}{12}&lt;/math&gt;. <br /> The answer is &lt;math&gt;\boxed{081}&lt;/math&gt;.<br /> ~awang11's sol<br /> <br /> == Solution 2 (Bash) ==<br /> <br /> We casework on the amount of men on the committee. <br /> <br /> If there are no men in the committee, there are &lt;math&gt;\dbinom{12}{1}&lt;/math&gt; ways to pick the women on the committee, for a total of &lt;math&gt;\dbinom{11}{0} \cdot \dbinom{12}{1}&lt;/math&gt;. Notice that &lt;math&gt;\dbinom{11}{0}&lt;/math&gt; is equal to &lt;math&gt;\dbinom{11}{11}&lt;/math&gt;, so the case where no men are picked can be grouped with the case where all men are picked. When all men are picked, all females must also be picked, for a total of &lt;math&gt;\dbinom{12}{12}&lt;/math&gt;. Therefore, these cases can be combined to &lt;cmath&gt;\dbinom{11}{0} \cdot \left(\dbinom{12}{1} + \dbinom{12}{12}\right)&lt;/cmath&gt; Since &lt;math&gt;\dbinom{12}{12} = \dbinom{12}{0}&lt;/math&gt;, and &lt;math&gt;\dbinom{12}{0} + \dbinom{12}{1} = \dbinom{13}{1}&lt;/math&gt;, we can further simplify this to &lt;cmath&gt;\dbinom{11}{0} \cdot \dbinom{13}{1}&lt;/cmath&gt;<br /> <br /> All other cases proceed similarly. For example, the case with one men or ten men is equal to &lt;math&gt;\dbinom{11}{1} \cdot \dbinom{13}{2}&lt;/math&gt;. Now, if we factor out a &lt;math&gt;13&lt;/math&gt;, then all cases except the first two have a factor of &lt;math&gt;121&lt;/math&gt;, so we can factor this out too to make our computation slightly easier. The first two cases (with &lt;math&gt;13&lt;/math&gt; factored out) give &lt;math&gt;1+66=67&lt;/math&gt;, and the rest gives &lt;math&gt;121(10+75+270+504) = 103,939&lt;/math&gt;. Adding the &lt;math&gt;67&lt;/math&gt; gives &lt;math&gt;104,006&lt;/math&gt;. Now, we can test for prime factors. We know there is a factor of &lt;math&gt;2&lt;/math&gt;, and the rest is &lt;math&gt;52,003&lt;/math&gt;. We can also factor out a &lt;math&gt;7&lt;/math&gt;, for &lt;math&gt;7,429&lt;/math&gt;, and the rest is &lt;math&gt;17 \cdot 19 \cdot 23&lt;/math&gt;. Adding up all the prime factors gives &lt;math&gt;2+7+13+17+19+23 = \boxed{081}&lt;/math&gt;.<br /> <br /> &lt;h3&gt;Video Solution:&lt;/h3&gt;<br /> <br /> https://youtu.be/MVxsY8DwHVk<br /> <br /> (Solves using both methods - Casework and Vandermonde's Identity)<br /> <br /> == Solution 3 (Vandermonde's identity) ==<br /> Applying Vandermonde's identity by setting &lt;math&gt;m=12&lt;/math&gt;, &lt;math&gt;n=11&lt;/math&gt;, and &lt;math&gt;r=11&lt;/math&gt;, we obtain &lt;math&gt;\binom{23}{11}\implies&lt;/math&gt; &lt;math&gt;\boxed{081}&lt;/math&gt;.<br /> ~Lcz<br /> <br /> &lt;h3&gt;Short Proof&lt;/h3&gt;<br /> Consider the following setup:<br /> &lt;asy&gt;<br /> size(1000, 100);<br /> for(int i=0; i&lt;23; ++i){<br /> dot((i, 0));<br /> }<br /> draw((10.5, -1.5)--(10.5, 1.5), dashed);<br /> &lt;/asy&gt;<br /> The dots to the left represent the men, and the dots to the right represent the women. Now, suppose we put a mark on &lt;math&gt;11&lt;/math&gt; people (the &lt;math&gt;*&lt;/math&gt;). Those to the left of the dashed line get to be &quot;in&quot; on the committee if they have a mark. Those on the right side of the dashed line are already on the committee, but if they're marked they get forcibly evicted from it. If there were &lt;math&gt;x&lt;/math&gt; people marked on the left, there ends up being &lt;math&gt;12-(11-x) = x+1&lt;/math&gt; people not marked on the right. Circles represent those in the committee.<br /> &lt;asy&gt;<br /> size(1000, 100);<br /> for(int i=0; i&lt;23; ++i){<br /> dot((i, 0));<br /> }<br /> for(int i=0; i&lt;23; ++i){<br /> if(i%2==0){<br /> if(i &gt;= 11){<br /> draw(circle((i, 0), 0.25));<br /> }<br /> continue;<br /> }<br /> label(&quot;$*$&quot;, (i,0.5), N);<br /> if(i &lt; 11){<br /> draw(circle((i, 0), 0.25));<br /> }<br /> }<br /> draw((10.5, -1.5)--(10.5, 1.5), dashed);<br /> &lt;/asy&gt;<br /> <br /> We have our bijection, so the number of ways will be &lt;math&gt;\binom{23}{11}&lt;/math&gt;.<br /> <br /> ~programjames1<br /> <br /> == Solution 4 ==<br /> Notice that the committee can consist of &lt;math&gt;k&lt;/math&gt; boys and &lt;math&gt;k+1&lt;/math&gt; girls. Summing over all possible &lt;math&gt;k&lt;/math&gt; gives <br /> &lt;cmath&gt;\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{11}{0}\binom{12}{1}+\binom{11}{1}\binom{12}{2}+\cdots + \binom{11}{11}\binom{12}{12}&lt;/cmath&gt;<br /> Using the identity &lt;math&gt;\binom{n}{k}=\binom{n}{n-k}&lt;/math&gt;, and Pascal's Identity &lt;math&gt;\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}&lt;/math&gt;, we get<br /> &lt;cmath&gt;\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{12}{12}+\binom{12}{1}\left(\binom{11}{0}+\binom{11}{1}\right)+\cdots &lt;/cmath&gt;<br /> &lt;cmath&gt;=\binom{12}{0}^2+\binom{12}{1}^2+\binom{12}{2}^2+\binom{12}{3}^2+\binom{12}{4}^2+\binom{12}{5}^2+\frac{\binom{12}{6}^2}{2}&lt;/cmath&gt;<br /> &lt;cmath&gt;=\frac{1}{2}\sum_{k=0}^{12}\binom{12}{k}^2&lt;/cmath&gt;<br /> Using the identity &lt;math&gt;\sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}&lt;/math&gt;, this simplifies to <br /> &lt;cmath&gt;\frac{1}{2}\cdot \binom{24}{12}=\frac{24\cdot 23\cdot 22\cdot 21\cdot 20\cdot 19\cdot 18\cdot 17\cdot 16\cdot 15\cdot 14\cdot 13}{2\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2}=2\cdot 7\cdot 13\cdot 17\cdot 19\cdot 23&lt;/cmath&gt;<br /> so the desired answer is &lt;math&gt;2+7+13+17+19+23=\boxed{081}&lt;/math&gt; ~ktong<br /> <br /> == Video Solution ==<br /> <br /> https://youtu.be/MVxsY8DwHVk<br /> <br /> (Solves using both methods - Casework and Vandermonde's Identity)<br /> <br /> ==See Also==<br /> <br /> {{AIME box|year=2020|n=I|num-b=6|num-a=8}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_8&diff=124617 2020 AIME I Problems/Problem 8 2020-06-09T18:29:28Z <p>Avn: /* Solution 3 (Solution 1 faster) */</p> <hr /> <div><br /> == Problem ==<br /> A bug walks all day and sleeps all night. On the first day, it starts at point &lt;math&gt;O,&lt;/math&gt; faces east, and walks a distance of &lt;math&gt;5&lt;/math&gt; units due east. Each night the bug rotates &lt;math&gt;60^\circ&lt;/math&gt; counterclockwise. Each day it walks in this new direction half as far as it walked the previous day. The bug gets arbitrarily close to the point &lt;math&gt;P.&lt;/math&gt; Then &lt;math&gt;OP^2=\tfrac{m}{n},&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m+n.&lt;/math&gt;<br /> <br /> == Solution 1 (Coordinates) ==<br /> &lt;asy&gt;<br /> size(8cm);<br /> pair O, A, B, C, D, F, G, P, X;<br /> O = (0, 0);<br /> A = (5, 0);<br /> X = (8, 0);<br /> P = (5, 5 / sqrt(3));<br /> B = rotate(-120, A) * ((O + A) / 2);<br /> C = rotate(-120, B) * ((A + B) / 2);<br /> D = rotate(-120, C) * ((B + C) / 2);<br /> F = rotate(-120, D) * ((C + D) / 2);<br /> G = rotate(-120, F) * ((D + F) / 2);<br /> draw(O -- A -- B -- C -- D -- F -- G);<br /> draw(A -- X, dashed);<br /> markscalefactor = 0.05;<br /> path angle = anglemark(X, A, B);<br /> draw(angle);<br /> <br /> dot(P);<br /> dot(O);<br /> <br /> label(&quot;$O$&quot;, O, W);<br /> label(&quot;$P$&quot;, P, E);<br /> label(&quot;$60^\circ$&quot;, angle, ENE*3);<br /> &lt;/asy&gt;<br /> <br /> We plot this on the coordinate grid with point &lt;math&gt;O&lt;/math&gt; as the origin. We will keep a tally of the x-coordinate and y-coordinate separately.<br /> <br /> First move: The ant moves right &lt;math&gt;5&lt;/math&gt;. <br /> Second move: We use properties of a &lt;math&gt;30-60-90&lt;/math&gt; triangle to get &lt;math&gt;\frac{5}{4}&lt;/math&gt; right, &lt;math&gt;\frac{5\sqrt{3}}{4}&lt;/math&gt; up. <br /> Third move: &lt;math&gt;\frac{5}{8}&lt;/math&gt; left, &lt;math&gt;\frac{5\sqrt{3}}{8}&lt;/math&gt; up.<br /> Fourth move: &lt;math&gt;\frac{5}{8}&lt;/math&gt; left.<br /> Fifth move: &lt;math&gt;\frac{5}{32}&lt;/math&gt; left, &lt;math&gt;\frac{5\sqrt{3}}{32}&lt;/math&gt; down.<br /> Sixth move: &lt;math&gt;\frac{5}{64}&lt;/math&gt; right, &lt;math&gt;\frac{5\sqrt{3}}{64}&lt;/math&gt; down.<br /> <br /> Total of x-coordinate: &lt;math&gt;5 + \frac{5}{4} - \frac{5}{8} - \frac{5}{8} - \frac{5}{32} + \frac{5}{64} = \frac{315}{64}&lt;/math&gt;.<br /> Total of y-coordinate: &lt;math&gt;0 + \frac{5\sqrt{3}}{4} + \frac{5\sqrt{3}}{8} + 0 - \frac{5\sqrt{3}}{32} - \frac{5\sqrt{3}}{64} = \frac{105\sqrt{3}}{64}&lt;/math&gt;.<br /> <br /> After this cycle of six moves, all moves repeat with a factor of &lt;math&gt;(\frac{1}{2})^6 = \frac{1}{64}&lt;/math&gt;. Using the formula for a geometric series, multiplying each sequence by &lt;math&gt;\frac{1}{1-\frac{1}{64}} = \frac{64}{63}&lt;/math&gt; will give us the point &lt;math&gt;P&lt;/math&gt;.<br /> <br /> &lt;math&gt;\frac{315}{64} \cdot \frac{64}{63} = 5&lt;/math&gt;, &lt;math&gt;\frac{105\sqrt{3}}{64} \cdot \frac{64}{63} = \frac{5\sqrt{3}}{3}&lt;/math&gt;.<br /> Therefore, the coordinates of point &lt;math&gt;P&lt;/math&gt; are &lt;math&gt;(5,\frac{5\sqrt{3}}{3})&lt;/math&gt;, so using the Pythagorean Theorem, &lt;math&gt;OP^2 = \frac{100}{3}&lt;/math&gt;, for an answer of &lt;math&gt;\boxed{103}&lt;/math&gt;.<br /> <br /> -molocyxu<br /> <br /> == Solution 2 (Complex) ==<br /> We place the ant at the origin of the complex plane with its first move being in the positive real direction. Then the ant's journey can be represented as the infinite series<br /> &lt;cmath&gt;5\left(1 + \frac{e^{\frac{i\pi}{3}}}{2} + \left(\frac{e^{\frac{i\pi}{3}}}{2}\right)^2 + \cdots\right)&lt;/cmath&gt;<br /> Using the formula for an infinite geometric series, this is equal to<br /> &lt;cmath&gt;\frac{5}{1 - \frac12e^{\frac{i\pi}{3}}} = \frac{5}{1 - \frac{1 + i\sqrt{3}}{4}} = \frac{20}{3 - i\sqrt{3}} = 5 + \frac{5i\sqrt{3}}{3}&lt;/cmath&gt;<br /> We are looking for the square of the modulus of this value:<br /> &lt;cmath&gt;\left|\frac{5 + 5i\sqrt{3}}{3}\right|^2 = 25 + \frac{25}{3} = \frac{100}{3}&lt;/cmath&gt;<br /> so the answer is &lt;math&gt;100 + 3 = \boxed{103}&lt;/math&gt;.<br /> <br /> == Solution 3 (Solution 1 faster) ==<br /> The ant goes in the opposite direction every &lt;math&gt;3&lt;/math&gt; moves, going &lt;math&gt;(1/2)^3=1/8&lt;/math&gt; the distance backwards. Using geometric series, he travels &lt;math&gt;1-1/8+1/64-1/512...=(7/8)(1+1/64+1/4096...)=(7/8)(64/63)=8/9&lt;/math&gt; the distance of the first three moves over infinity moves. Now, we use coordinates meaning &lt;math&gt;(5+5/4-5/8, 0+5\sqrt3/4+5\sqrt3/8)&lt;/math&gt; or &lt;math&gt;(45/8, 15\sqrt3/8)&lt;/math&gt;. Multiplying these by &lt;math&gt;8/9&lt;/math&gt;, we get &lt;math&gt;(5, 5\sqrt3/3)&lt;/math&gt; &lt;math&gt;\implies&lt;/math&gt; &lt;math&gt;\boxed{103}&lt;/math&gt; .<br /> <br /> ~Lcz<br /> <br /> == Video Solution ==<br /> <br /> https://www.youtube.com/watch?v=BtMBSoZ3cMQ<br /> <br /> -avn<br /> <br /> ==See Also==<br /> <br /> {{AIME box|year=2020|n=I|num-b=7|num-a=9}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=Combinatorial_identity&diff=123859 Combinatorial identity 2020-06-05T05:07:03Z <p>Avn: /* Vandermonde's Identity */</p> <hr /> <div>==Vandermonde's Identity==<br /> Vandermonde's Identity states that &lt;math&gt;\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r&lt;/math&gt;, which can be proven combinatorially by noting that any combination of &lt;math&gt;r&lt;/math&gt; objects from a group of &lt;math&gt;m+n&lt;/math&gt; objects must have some &lt;math&gt;0\le k\le r&lt;/math&gt; objects from group &lt;math&gt;m&lt;/math&gt; and the remaining from group &lt;math&gt;n&lt;/math&gt;.<br /> <br /> Video Proof: <br /> <br /> https://www.youtube.com/watch?v=wCl9Kqz5kUA<br /> <br /> ==Hockey-Stick Identity==<br /> For &lt;math&gt;n,r\in\mathbb{N}, n&gt;r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}&lt;/math&gt;.<br /> <br /> &lt;asy&gt;<br /> int chew(int n,int r){<br /> int res=1;<br /> for(int i=0;i&lt;r;++i){<br /> res=quotient(res*(n-i),i+1);<br /> }<br /> return res;<br /> }<br /> for(int n=0;n&lt;9;++n){<br /> for(int i=0;i&lt;=n;++i){<br /> if((i==2 &amp;&amp; n&lt;8)||(i==3 &amp;&amp; n==8)){<br /> if(n==8){label(string(chew(n,i)),(11+n/2-i,-n),p=red+2.5);}<br /> else{label(string(chew(n,i)),(11+n/2-i,-n),p=blue+2);}<br /> }<br /> else{<br /> label(string(chew(n,i)),(11+n/2-i,-n));<br /> }<br /> }<br /> }<br /> &lt;/asy&gt;<br /> <br /> This identity is known as the ''hockey-stick'' identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself is highlighted, a hockey-stick shape is revealed.<br /> <br /> <br /> ===Proof===<br /> <br /> '''Inductive Proof'''<br /> <br /> This identity can be proven by induction on &lt;math&gt;n&lt;/math&gt;.<br /> <br /> &lt;u&gt;Base Case&lt;/u&gt;<br /> Let &lt;math&gt;n=r&lt;/math&gt;.<br /> <br /> &lt;math&gt;\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}&lt;/math&gt;.<br /> <br /> &lt;u&gt;Inductive Step&lt;/u&gt;<br /> Suppose, for some &lt;math&gt;k\in\mathbb{N}, k&gt;r&lt;/math&gt;, &lt;math&gt;\sum^k_{i=r}{i\choose r}={k+1\choose r+1}&lt;/math&gt;.<br /> Then &lt;math&gt;\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}&lt;/math&gt;.<br /> <br /> '''Algebraic Proof'''<br /> <br /> It can also be proven algebraically with [[Pascal's Identity]], &lt;math&gt;{n \choose k}={n-1\choose k-1}+{n-1\choose k}&lt;/math&gt;.<br /> Note that<br /> <br /> &lt;math&gt;{r \choose r}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}&lt;/math&gt;<br /> &lt;math&gt;={r+1 \choose r+1}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}&lt;/math&gt;<br /> &lt;math&gt;={r+2 \choose r+1}+{r+2 \choose r}+\cdots+{r+a \choose r}=\cdots={r+a \choose r+1}+{r+a \choose r}={r+a+1 \choose r+1}&lt;/math&gt;, which is equivalent to the desired result.<br /> <br /> '''Combinatorial Proof 1'''<br /> <br /> Imagine that we are distributing &lt;math&gt;n&lt;/math&gt; indistinguishable candies to &lt;math&gt;k&lt;/math&gt; distinguishable children. By a direct application of Balls and Urns, there are &lt;math&gt;{n+k-1\choose k-1}&lt;/math&gt; ways to do this. Alternatively, we can first give &lt;math&gt;0\le i\le n&lt;/math&gt; candies to the oldest child so that we are essentially giving &lt;math&gt;n-i&lt;/math&gt; candies to &lt;math&gt;k-1&lt;/math&gt; kids and again, with Balls and Urns, &lt;math&gt;{n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}&lt;/math&gt;, which simplifies to the desired result.<br /> <br /> '''Combinatorial Proof 2'''<br /> <br /> We can form a committee of size &lt;math&gt;k+1&lt;/math&gt; from a group of &lt;math&gt;n+1&lt;/math&gt; people in &lt;math&gt;{{n+1}\choose{k+1}}&lt;/math&gt; ways. Now we hand out the numbers &lt;math&gt;1,2,3,\dots,n-k+1&lt;/math&gt; to &lt;math&gt;n-k+1&lt;/math&gt; of the &lt;math&gt;n+1&lt;/math&gt; people. We can divide this into &lt;math&gt;n-k+1&lt;/math&gt; disjoint cases. In general, in case &lt;math&gt;x&lt;/math&gt;, &lt;math&gt;1\le x\le n-k+1&lt;/math&gt;, person &lt;math&gt;x&lt;/math&gt; is on the committee and persons &lt;math&gt;1,2,3,\dots, x-1&lt;/math&gt; are not on the committee. This can be done in &lt;math&gt;\binom{n-x+1}{k}&lt;/math&gt; ways. Now we can sum the values of these &lt;math&gt;n-k+1&lt;/math&gt; disjoint cases, getting &lt;cmath&gt;{{n+1}\choose {k+1}} ={{n}\choose{k}}+{{n-1}\choose{k}}+{{n-2}\choose{k}}+\hdots+{{k+1}\choose{k}}+{{k}\choose{k}}.&lt;/cmath&gt;<br /> <br /> '''Algebraic Proof 2'''<br /> <br /> Apply the finite geometric series formula to &lt;math&gt;(1+x)&lt;/math&gt;: &lt;cmath&gt;1+(1+x)+(1+x)^2+...+(1+x)^n=\frac{(1+x)^{n+1}-1}{(1+x)-1}&lt;/cmath&gt; Then expand with the Binomial Theorem and simplify: &lt;cmath&gt;1+(1+x)+(1+2x+x^2)+...+(\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n-1}x^{n-1}+\binom{n}{n}x^n)=\binom{n+1}{1}+\binom{n+1}{2}x+...+\binom{n+1}{n+1}x^n&lt;/cmath&gt; Finally, equate coefficients of &lt;math&gt;x^m&lt;/math&gt; on both sides: &lt;cmath&gt;\binom{0}{m}+\binom{1}{m}+\binom{2}{m}+...+\binom{n}{m}=\binom{n+1}{m+1}&lt;/cmath&gt; Since for &lt;math&gt;i&lt;m&lt;/math&gt;, &lt;math&gt;\binom{i}{m}=0&lt;/math&gt;, this simplifies to the hockey stick identity. -- EVIN-<br /> <br /> ==Another Identity==<br /> <br /> &lt;cmath&gt;<br /> \sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}<br /> &lt;/cmath&gt;<br /> <br /> ===Hat Proof===<br /> We have &lt;math&gt;2k&lt;/math&gt; different hats. We split them into two groups, each with k hats: then we choose &lt;math&gt;i&lt;/math&gt; hats from the first group and &lt;math&gt;k-i&lt;/math&gt; hats from the second group. This may be done in &lt;math&gt;\binom{k}{i}^2&lt;/math&gt; ways. Evidently, to generate all possible choices of &lt;math&gt;k&lt;/math&gt; hats from the &lt;math&gt;2k&lt;/math&gt; hats, we must choose &lt;math&gt;i=0,1,\cdots,k&lt;/math&gt; hats from the first &lt;math&gt;k&lt;/math&gt; and the remaining &lt;math&gt;k-i&lt;/math&gt; hats from the second &lt;math&gt;k&lt;/math&gt;; the sum over all such &lt;math&gt;i&lt;/math&gt; is the number of ways of choosing &lt;math&gt;k&lt;/math&gt; hats from &lt;math&gt;2k&lt;/math&gt;. Therefore &lt;math&gt;\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}&lt;/math&gt;, as desired.<br /> <br /> ===Proof 2===<br /> This is a special case of Vandermonde's identity, in which we set &lt;math&gt;m=n&lt;/math&gt; and &lt;math&gt;r=m&lt;/math&gt;.<br /> <br /> <br /> == Examples ==<br /> * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=394407#394407 1986 AIME Problem 11]<br /> * [http://www.artofproblemsolving.com/Forum/resources.php?c=182&amp;cid=45&amp;year=2000&amp;p=385891 2000 AIME II Problem 7]<br /> * [https://artofproblemsolving.com/wiki/index.php?title=2013_AIME_I_Problems/Problem_6#Solution_Two 2013 AIME II Problem 6 (Solution 2)]<br /> * [http://artofproblemsolving.com/wiki/index.php/2015_AIME_I_Problems/Problem_12 2015 AIME I Problem 12]<br /> * [https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems/Problem_7 2020 AIME I Problem 7]<br /> <br /> ==See also==<br /> * [[Pascal's Triangle]]<br /> * [[Combinatorics]]<br /> <br /> [[Category:Theorems]]<br /> <br /> [[Category:Combinatorics]]</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_7&diff=123216 2020 AIME I Problems/Problem 7 2020-05-28T23:36:07Z <p>Avn: /* Solution 2 (Bash) */</p> <hr /> <div><br /> == Problem ==<br /> A club consisting of &lt;math&gt;11&lt;/math&gt; men and &lt;math&gt;12&lt;/math&gt; women needs to choose a committee from among its members so that the number of women on the committee is one more than the number of men on the committee. The committee could have as few as &lt;math&gt;1&lt;/math&gt; member or as many as &lt;math&gt;23&lt;/math&gt; members. Let &lt;math&gt;N&lt;/math&gt; be the number of such committees that can be formed. Find the sum of the prime numbers that divide &lt;math&gt;N.&lt;/math&gt;<br /> <br /> == Solution 1 ==<br /> We will be selecting women, but &lt;i&gt;not&lt;/i&gt; selecting men. We claim that the amount of women selected and the amount of men not selected adds to &lt;math&gt;12&lt;/math&gt;. This is easy to see: if &lt;math&gt;k&lt;/math&gt; women were chosen, then &lt;math&gt;k + (11 - k + 1) = 12&lt;/math&gt;. Therefore, we simply take &lt;math&gt;\binom{23}{12} \implies \boxed{081}&lt;/math&gt;. ~awang11's sol<br /> <br /> == Solution 2 (Bash) ==<br /> <br /> We casework on the amount of men on the committee. <br /> <br /> If there are no men in the committee, there are &lt;math&gt;\dbinom{12}{1}&lt;/math&gt; ways to pick the women on the committee, for a total of &lt;math&gt;\dbinom{11}{0} \cdot \dbinom{12}{1}&lt;/math&gt;. Notice that &lt;math&gt;\dbinom{11}{0}&lt;/math&gt; is equal to &lt;math&gt;\dbinom{11}{11}&lt;/math&gt;, so the case where no men are picked can be grouped with the case where all men are picked. When all men are picked, all females must also be picked, for a total of &lt;math&gt;\dbinom{12}{12}&lt;/math&gt;. Therefore, these cases can be combined to &lt;cmath&gt;\dbinom{11}{0} \cdot \left(\dbinom{12}{1} + \dbinom{12}{12}\right)&lt;/cmath&gt; Since &lt;math&gt;\dbinom{12}{12} = \dbinom{12}{0}&lt;/math&gt;, and &lt;math&gt;\dbinom{12}{0} + \dbinom{12}{1} = \dbinom{13}{1}&lt;/math&gt;, we can further simplify this to &lt;cmath&gt;\dbinom{11}{0} \cdot \dbinom{13}{1}&lt;/cmath&gt;<br /> <br /> All other cases proceed similarly. For example, the case with one men or ten men is equal to &lt;math&gt;\dbinom{11}{1} \cdot \dbinom{13}{2}&lt;/math&gt;. Now, if we factor out a &lt;math&gt;13&lt;/math&gt;, then all cases except the first two have a factor of &lt;math&gt;121&lt;/math&gt;, so we can factor this out too to make our computation slightly easier. The first two cases (with &lt;math&gt;13&lt;/math&gt; factored out) give &lt;math&gt;1+66=67&lt;/math&gt;, and the rest gives &lt;math&gt;121(10+75+270+504) = 103,939&lt;/math&gt;. Adding the &lt;math&gt;67&lt;/math&gt; gives &lt;math&gt;104,006&lt;/math&gt;. Now, we can test for prime factors. We know there is a factor of &lt;math&gt;2&lt;/math&gt;, and the rest is &lt;math&gt;52,003&lt;/math&gt;. We can also factor out a &lt;math&gt;7&lt;/math&gt;, for &lt;math&gt;7,429&lt;/math&gt;, and the rest is &lt;math&gt;17 \cdot 19 \cdot 23&lt;/math&gt;. Adding up all the prime factors gives &lt;math&gt;2+7+13+17+19+23 = \boxed{081}&lt;/math&gt;.<br /> <br /> &lt;h3&gt;Video Solution:&lt;/h3&gt;<br /> <br /> https://youtu.be/MVxsY8DwHVk<br /> <br /> (Solves using both methods - Casework and Vandermonde's Identity)<br /> <br /> == Solution 3 (Vandermonde's identity) ==<br /> Applying Vandermonde's identity by setting &lt;math&gt;m=12&lt;/math&gt;, &lt;math&gt;n=11&lt;/math&gt;, and &lt;math&gt;r=11&lt;/math&gt;, we obtain &lt;math&gt;\binom{23}{11}\implies&lt;/math&gt; &lt;math&gt;\boxed{081}&lt;/math&gt;.<br /> ~Lcz<br /> <br /> &lt;h3&gt;Short Proof&lt;/h3&gt;<br /> Consider the following setup:<br /> &lt;asy&gt;<br /> size(1000, 100);<br /> for(int i=0; i&lt;23; ++i){<br /> dot((i, 0));<br /> }<br /> draw((10.5, -1.5)--(10.5, 1.5), dashed);<br /> &lt;/asy&gt;<br /> The dots to the left represent the men, and the dots to the right represent the women. Now, suppose we put a mark on &lt;math&gt;11&lt;/math&gt; people (the &lt;math&gt;*&lt;/math&gt;). Those to the left of the dashed line get to be &quot;in&quot; on the committee if they have a mark. Those on the right side of the dashed line are already on the committee, but if they're marked they get forcibly evicted from it. If there were &lt;math&gt;x&lt;/math&gt; people marked on the left, there ends up being &lt;math&gt;12-(11-x) = x+1&lt;/math&gt; people not marked on the right. Circles represent those in the committee.<br /> &lt;asy&gt;<br /> size(1000, 100);<br /> for(int i=0; i&lt;23; ++i){<br /> dot((i, 0));<br /> }<br /> for(int i=0; i&lt;23; ++i){<br /> if(i%2==0){<br /> if(i &gt;= 11){<br /> draw(circle((i, 0), 0.25));<br /> }<br /> continue;<br /> }<br /> label(&quot;$*$&quot;, (i,0.5), N);<br /> if(i &lt; 11){<br /> draw(circle((i, 0), 0.25));<br /> }<br /> }<br /> draw((10.5, -1.5)--(10.5, 1.5), dashed);<br /> &lt;/asy&gt;<br /> <br /> We have our bijection, so the number of ways will be &lt;math&gt;\binom{23}{11}&lt;/math&gt;.<br /> <br /> ~programjames1<br /> <br /> == Solution 4 ==<br /> Notice that the committee can consist of &lt;math&gt;k&lt;/math&gt; boys and &lt;math&gt;k+1&lt;/math&gt; girls. Summing over all possible &lt;math&gt;k&lt;/math&gt; gives <br /> &lt;cmath&gt;\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{11}{0}\binom{12}{1}+\binom{11}{1}\binom{12}{2}+\cdots + \binom{11}{11}\binom{12}{12}&lt;/cmath&gt;<br /> Using the identity &lt;math&gt;\binom{n}{k}=\binom{n}{n-k}&lt;/math&gt;, and Pascal's Identity &lt;math&gt;\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}&lt;/math&gt;, we get<br /> &lt;cmath&gt;\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{12}{12}+\binom{12}{1}\left(\binom{11}{0}+\binom{11}{1}\right)+\cdots &lt;/cmath&gt;<br /> &lt;cmath&gt;=\binom{12}{0}^2+\binom{12}{1}^2+\binom{12}{2}^2+\binom{12}{3}^2+\binom{12}{4}^2+\binom{12}{5}^2+\frac{\binom{12}{6}^2}{2}&lt;/cmath&gt;<br /> &lt;cmath&gt;=\frac{1}{2}\sum_{k=0}^{12}\binom{12}{k}^2&lt;/cmath&gt;<br /> Using the identity &lt;math&gt;\sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}&lt;/math&gt;, this simplifies to <br /> &lt;cmath&gt;\frac{1}{2}\cdot \binom{24}{12}=\frac{24\cdot 23\cdot 22\cdot 21\cdot 20\cdot 19\cdot 18\cdot 17\cdot 16\cdot 15\cdot 14\cdot 13}{2\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2}=2\cdot 7\cdot 13\cdot 17\cdot 19\cdot 23&lt;/cmath&gt;<br /> so the desired answer is &lt;math&gt;2+7+13+17+19+23=\boxed{081}&lt;/math&gt; ~ktong<br /> <br /> ==See Also==<br /> <br /> {{AIME box|year=2020|n=I|num-b=6|num-a=8}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_7&diff=123135 2020 AIME I Problems/Problem 7 2020-05-28T03:34:24Z <p>Avn: /* Solution 2 (Bash) */</p> <hr /> <div><br /> == Problem ==<br /> A club consisting of &lt;math&gt;11&lt;/math&gt; men and &lt;math&gt;12&lt;/math&gt; women needs to choose a committee from among its members so that the number of women on the committee is one more than the number of men on the committee. The committee could have as few as &lt;math&gt;1&lt;/math&gt; member or as many as &lt;math&gt;23&lt;/math&gt; members. Let &lt;math&gt;N&lt;/math&gt; be the number of such committees that can be formed. Find the sum of the prime numbers that divide &lt;math&gt;N.&lt;/math&gt;<br /> <br /> == Solution 1 ==<br /> We will be selecting women, but &lt;i&gt;not&lt;/i&gt; selecting men. We claim that the amount of women selected and the amount of men not selected adds to &lt;math&gt;12&lt;/math&gt;. This is easy to see: if &lt;math&gt;k&lt;/math&gt; women were chosen, then &lt;math&gt;k + (11 - k + 1) = 12&lt;/math&gt;. Therefore, we simply take &lt;math&gt;\binom{23}{12} \implies \boxed{081}&lt;/math&gt;. ~awang11's sol<br /> <br /> == Solution 2 (Bash) ==<br /> <br /> We casework on the amount of men on the committee. <br /> <br /> If there are no men in the committee, there are &lt;math&gt;\dbinom{12}{1}&lt;/math&gt; ways to pick the women on the committee, for a total of &lt;math&gt;\dbinom{11}{0} \cdot \dbinom{12}{1}&lt;/math&gt;. Notice that &lt;math&gt;\dbinom{11}{0}&lt;/math&gt; is equal to &lt;math&gt;\dbinom{11}{11}&lt;/math&gt;, so the case where no men are picked can be grouped with the case where all men are picked. When all men are picked, all females must also be picked, for a total of &lt;math&gt;\dbinom{12}{12}&lt;/math&gt;. Therefore, these cases can be combined to &lt;cmath&gt;\dbinom{11}{0} \cdot \left(\dbinom{12}{1} + \dbinom{12}{12}\right)&lt;/cmath&gt; Since &lt;math&gt;\dbinom{12}{12} = \dbinom{12}{0}&lt;/math&gt;, and &lt;math&gt;\dbinom{12}{0} + \dbinom{12}{1} = \dbinom{13}{1}&lt;/math&gt;, we can further simplify this to &lt;cmath&gt;\dbinom{11}{0} \cdot \dbinom{13}{1}&lt;/cmath&gt;<br /> <br /> All other cases proceed similarly. For example, the case with one men or ten men is equal to &lt;math&gt;\dbinom{11}{1} \cdot \dbinom{13}{2}&lt;/math&gt;. Now, if we factor out a &lt;math&gt;13&lt;/math&gt;, then all cases except the first two have a factor of &lt;math&gt;121&lt;/math&gt;, so we can factor this out too to make our computation slightly easier. The first two cases (with &lt;math&gt;13&lt;/math&gt; factored out) give &lt;math&gt;1+66=67&lt;/math&gt;, and the rest gives &lt;math&gt;121(10+75+270+504) = 103,939&lt;/math&gt;. Adding the &lt;math&gt;67&lt;/math&gt; gives &lt;math&gt;104,006&lt;/math&gt;. Now, we can test for prime factors. We know there is a factor of &lt;math&gt;2&lt;/math&gt;, and the rest is &lt;math&gt;52,003&lt;/math&gt;. We can also factor out a &lt;math&gt;7&lt;/math&gt;, for &lt;math&gt;7,429&lt;/math&gt;, and the rest is &lt;math&gt;17 \cdot 19 \cdot 23&lt;/math&gt;. Adding up all the prime factors gives &lt;math&gt;2+7+13+17+19+23 = \boxed{081}&lt;/math&gt;.<br /> <br /> &lt;h3&gt;Video Solution:&lt;/h3&gt;<br /> <br /> https://www.youtube.com/watch?v=vWEBfVjmS1Q<br /> <br /> (Solves using both methods - Casework and Vandermonde's Identity)<br /> <br /> == Solution 3 (Vandermonde's identity) ==<br /> Applying Vandermonde's identity by setting &lt;math&gt;m=12&lt;/math&gt;, &lt;math&gt;n=11&lt;/math&gt;, and &lt;math&gt;r=11&lt;/math&gt;, we obtain &lt;math&gt;\binom{23}{11}\implies&lt;/math&gt; &lt;math&gt;\boxed{081}&lt;/math&gt;.<br /> ~Lcz<br /> <br /> &lt;h3&gt;Short Proof&lt;/h3&gt;<br /> Consider the following setup:<br /> &lt;asy&gt;<br /> size(1000, 100);<br /> for(int i=0; i&lt;23; ++i){<br /> dot((i, 0));<br /> }<br /> draw((10.5, -1.5)--(10.5, 1.5), dashed);<br /> &lt;/asy&gt;<br /> The dots to the left represent the men, and the dots to the right represent the women. Now, suppose we put a mark on &lt;math&gt;11&lt;/math&gt; people (the &lt;math&gt;*&lt;/math&gt;). Those to the left of the dashed line get to be &quot;in&quot; on the committee if they have a mark. Those on the right side of the dashed line are already on the committee, but if they're marked they get forcibly evicted from it. If there were &lt;math&gt;x&lt;/math&gt; people marked on the left, there ends up being &lt;math&gt;12-(11-x) = x+1&lt;/math&gt; people not marked on the right. Circles represent those in the committee.<br /> &lt;asy&gt;<br /> size(1000, 100);<br /> for(int i=0; i&lt;23; ++i){<br /> dot((i, 0));<br /> }<br /> for(int i=0; i&lt;23; ++i){<br /> if(i%2==0){<br /> if(i &gt;= 11){<br /> draw(circle((i, 0), 0.25));<br /> }<br /> continue;<br /> }<br /> label(&quot;$*$&quot;, (i,0.5), N);<br /> if(i &lt; 11){<br /> draw(circle((i, 0), 0.25));<br /> }<br /> }<br /> draw((10.5, -1.5)--(10.5, 1.5), dashed);<br /> &lt;/asy&gt;<br /> <br /> We have our bijection, so the number of ways will be &lt;math&gt;\binom{23}{11}&lt;/math&gt;.<br /> <br /> ~programjames1<br /> <br /> == Solution 4 ==<br /> Notice that the committee can consist of &lt;math&gt;k&lt;/math&gt; boys and &lt;math&gt;k+1&lt;/math&gt; girls. Summing over all possible &lt;math&gt;k&lt;/math&gt; gives <br /> &lt;cmath&gt;\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{11}{0}\binom{12}{1}+\binom{11}{1}\binom{12}{2}+\cdots + \binom{11}{11}\binom{12}{12}&lt;/cmath&gt;<br /> Using the identity &lt;math&gt;\binom{n}{k}=\binom{n}{n-k}&lt;/math&gt;, and Pascal's Identity &lt;math&gt;\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}&lt;/math&gt;, we get<br /> &lt;cmath&gt;\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{12}{12}+\binom{12}{1}\left(\binom{11}{0}+\binom{11}{1}\right)+\cdots &lt;/cmath&gt;<br /> &lt;cmath&gt;=\binom{12}{0}^2+\binom{12}{1}^2+\binom{12}{2}^2+\binom{12}{3}^2+\binom{12}{4}^2+\binom{12}{5}^2+\frac{\binom{12}{6}^2}{2}&lt;/cmath&gt;<br /> &lt;cmath&gt;=\frac{1}{2}\sum_{k=0}^{12}\binom{12}{k}^2&lt;/cmath&gt;<br /> Using the identity &lt;math&gt;\sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}&lt;/math&gt;, this simplifies to <br /> &lt;cmath&gt;\frac{1}{2}\cdot \binom{24}{12}=\frac{24\cdot 23\cdot 22\cdot 21\cdot 20\cdot 19\cdot 18\cdot 17\cdot 16\cdot 15\cdot 14\cdot 13}{2\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2}=2\cdot 7\cdot 13\cdot 17\cdot 19\cdot 23&lt;/cmath&gt;<br /> so the desired answer is &lt;math&gt;2+7+13+17+19+23=\boxed{081}&lt;/math&gt; ~ktong<br /> <br /> ==See Also==<br /> <br /> {{AIME box|year=2020|n=I|num-b=6|num-a=8}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_7&diff=123134 2020 AIME I Problems/Problem 7 2020-05-28T03:33:47Z <p>Avn: /* Solution 3 (Vandermonde's identity) */</p> <hr /> <div><br /> == Problem ==<br /> A club consisting of &lt;math&gt;11&lt;/math&gt; men and &lt;math&gt;12&lt;/math&gt; women needs to choose a committee from among its members so that the number of women on the committee is one more than the number of men on the committee. The committee could have as few as &lt;math&gt;1&lt;/math&gt; member or as many as &lt;math&gt;23&lt;/math&gt; members. Let &lt;math&gt;N&lt;/math&gt; be the number of such committees that can be formed. Find the sum of the prime numbers that divide &lt;math&gt;N.&lt;/math&gt;<br /> <br /> == Solution 1 ==<br /> We will be selecting women, but &lt;i&gt;not&lt;/i&gt; selecting men. We claim that the amount of women selected and the amount of men not selected adds to &lt;math&gt;12&lt;/math&gt;. This is easy to see: if &lt;math&gt;k&lt;/math&gt; women were chosen, then &lt;math&gt;k + (11 - k + 1) = 12&lt;/math&gt;. Therefore, we simply take &lt;math&gt;\binom{23}{12} \implies \boxed{081}&lt;/math&gt;. ~awang11's sol<br /> <br /> == Solution 2 (Bash) ==<br /> <br /> We casework on the amount of men on the committee. <br /> <br /> If there are no men in the committee, there are &lt;math&gt;\dbinom{12}{1}&lt;/math&gt; ways to pick the women on the committee, for a total of &lt;math&gt;\dbinom{11}{0} \cdot \dbinom{12}{1}&lt;/math&gt;. Notice that &lt;math&gt;\dbinom{11}{0}&lt;/math&gt; is equal to &lt;math&gt;\dbinom{11}{11}&lt;/math&gt;, so the case where no men are picked can be grouped with the case where all men are picked. When all men are picked, all females must also be picked, for a total of &lt;math&gt;\dbinom{12}{12}&lt;/math&gt;. Therefore, these cases can be combined to &lt;cmath&gt;\dbinom{11}{0} \cdot \left(\dbinom{12}{1} + \dbinom{12}{12}\right)&lt;/cmath&gt; Since &lt;math&gt;\dbinom{12}{12} = \dbinom{12}{0}&lt;/math&gt;, and &lt;math&gt;\dbinom{12}{0} + \dbinom{12}{1} = \dbinom{13}{1}&lt;/math&gt;, we can further simplify this to &lt;cmath&gt;\dbinom{11}{0} \cdot \dbinom{13}{1}&lt;/cmath&gt;<br /> <br /> All other cases proceed similarly. For example, the case with one men or ten men is equal to &lt;math&gt;\dbinom{11}{1} \cdot \dbinom{13}{2}&lt;/math&gt;. Now, if we factor out a &lt;math&gt;13&lt;/math&gt;, then all cases except the first two have a factor of &lt;math&gt;121&lt;/math&gt;, so we can factor this out too to make our computation slightly easier. The first two cases (with &lt;math&gt;13&lt;/math&gt; factored out) give &lt;math&gt;1+66=67&lt;/math&gt;, and the rest gives &lt;math&gt;121(10+75+270+504) = 103,939&lt;/math&gt;. Adding the &lt;math&gt;67&lt;/math&gt; gives &lt;math&gt;104,006&lt;/math&gt;. Now, we can test for prime factors. We know there is a factor of &lt;math&gt;2&lt;/math&gt;, and the rest is &lt;math&gt;52,003&lt;/math&gt;. We can also factor out a &lt;math&gt;7&lt;/math&gt;, for &lt;math&gt;7,429&lt;/math&gt;, and the rest is &lt;math&gt;17 \cdot 19 \cdot 23&lt;/math&gt;. Adding up all the prime factors gives &lt;math&gt;2+7+13+17+19+23 = \boxed{081}&lt;/math&gt;.<br /> <br /> == Solution 3 (Vandermonde's identity) ==<br /> Applying Vandermonde's identity by setting &lt;math&gt;m=12&lt;/math&gt;, &lt;math&gt;n=11&lt;/math&gt;, and &lt;math&gt;r=11&lt;/math&gt;, we obtain &lt;math&gt;\binom{23}{11}\implies&lt;/math&gt; &lt;math&gt;\boxed{081}&lt;/math&gt;.<br /> ~Lcz<br /> <br /> &lt;h3&gt;Short Proof&lt;/h3&gt;<br /> Consider the following setup:<br /> &lt;asy&gt;<br /> size(1000, 100);<br /> for(int i=0; i&lt;23; ++i){<br /> dot((i, 0));<br /> }<br /> draw((10.5, -1.5)--(10.5, 1.5), dashed);<br /> &lt;/asy&gt;<br /> The dots to the left represent the men, and the dots to the right represent the women. Now, suppose we put a mark on &lt;math&gt;11&lt;/math&gt; people (the &lt;math&gt;*&lt;/math&gt;). Those to the left of the dashed line get to be &quot;in&quot; on the committee if they have a mark. Those on the right side of the dashed line are already on the committee, but if they're marked they get forcibly evicted from it. If there were &lt;math&gt;x&lt;/math&gt; people marked on the left, there ends up being &lt;math&gt;12-(11-x) = x+1&lt;/math&gt; people not marked on the right. Circles represent those in the committee.<br /> &lt;asy&gt;<br /> size(1000, 100);<br /> for(int i=0; i&lt;23; ++i){<br /> dot((i, 0));<br /> }<br /> for(int i=0; i&lt;23; ++i){<br /> if(i%2==0){<br /> if(i &gt;= 11){<br /> draw(circle((i, 0), 0.25));<br /> }<br /> continue;<br /> }<br /> label(&quot;$*$&quot;, (i,0.5), N);<br /> if(i &lt; 11){<br /> draw(circle((i, 0), 0.25));<br /> }<br /> }<br /> draw((10.5, -1.5)--(10.5, 1.5), dashed);<br /> &lt;/asy&gt;<br /> <br /> We have our bijection, so the number of ways will be &lt;math&gt;\binom{23}{11}&lt;/math&gt;.<br /> <br /> ~programjames1<br /> <br /> == Solution 4 ==<br /> Notice that the committee can consist of &lt;math&gt;k&lt;/math&gt; boys and &lt;math&gt;k+1&lt;/math&gt; girls. Summing over all possible &lt;math&gt;k&lt;/math&gt; gives <br /> &lt;cmath&gt;\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{11}{0}\binom{12}{1}+\binom{11}{1}\binom{12}{2}+\cdots + \binom{11}{11}\binom{12}{12}&lt;/cmath&gt;<br /> Using the identity &lt;math&gt;\binom{n}{k}=\binom{n}{n-k}&lt;/math&gt;, and Pascal's Identity &lt;math&gt;\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}&lt;/math&gt;, we get<br /> &lt;cmath&gt;\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{12}{12}+\binom{12}{1}\left(\binom{11}{0}+\binom{11}{1}\right)+\cdots &lt;/cmath&gt;<br /> &lt;cmath&gt;=\binom{12}{0}^2+\binom{12}{1}^2+\binom{12}{2}^2+\binom{12}{3}^2+\binom{12}{4}^2+\binom{12}{5}^2+\frac{\binom{12}{6}^2}{2}&lt;/cmath&gt;<br /> &lt;cmath&gt;=\frac{1}{2}\sum_{k=0}^{12}\binom{12}{k}^2&lt;/cmath&gt;<br /> Using the identity &lt;math&gt;\sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}&lt;/math&gt;, this simplifies to <br /> &lt;cmath&gt;\frac{1}{2}\cdot \binom{24}{12}=\frac{24\cdot 23\cdot 22\cdot 21\cdot 20\cdot 19\cdot 18\cdot 17\cdot 16\cdot 15\cdot 14\cdot 13}{2\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2}=2\cdot 7\cdot 13\cdot 17\cdot 19\cdot 23&lt;/cmath&gt;<br /> so the desired answer is &lt;math&gt;2+7+13+17+19+23=\boxed{081}&lt;/math&gt; ~ktong<br /> <br /> ==See Also==<br /> <br /> {{AIME box|year=2020|n=I|num-b=6|num-a=8}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_7&diff=123133 2020 AIME I Problems/Problem 7 2020-05-28T03:32:58Z <p>Avn: /* Solution 3 (Vandermonde's identity) */</p> <hr /> <div><br /> == Problem ==<br /> A club consisting of &lt;math&gt;11&lt;/math&gt; men and &lt;math&gt;12&lt;/math&gt; women needs to choose a committee from among its members so that the number of women on the committee is one more than the number of men on the committee. The committee could have as few as &lt;math&gt;1&lt;/math&gt; member or as many as &lt;math&gt;23&lt;/math&gt; members. Let &lt;math&gt;N&lt;/math&gt; be the number of such committees that can be formed. Find the sum of the prime numbers that divide &lt;math&gt;N.&lt;/math&gt;<br /> <br /> == Solution 1 ==<br /> We will be selecting women, but &lt;i&gt;not&lt;/i&gt; selecting men. We claim that the amount of women selected and the amount of men not selected adds to &lt;math&gt;12&lt;/math&gt;. This is easy to see: if &lt;math&gt;k&lt;/math&gt; women were chosen, then &lt;math&gt;k + (11 - k + 1) = 12&lt;/math&gt;. Therefore, we simply take &lt;math&gt;\binom{23}{12} \implies \boxed{081}&lt;/math&gt;. ~awang11's sol<br /> <br /> == Solution 2 (Bash) ==<br /> <br /> We casework on the amount of men on the committee. <br /> <br /> If there are no men in the committee, there are &lt;math&gt;\dbinom{12}{1}&lt;/math&gt; ways to pick the women on the committee, for a total of &lt;math&gt;\dbinom{11}{0} \cdot \dbinom{12}{1}&lt;/math&gt;. Notice that &lt;math&gt;\dbinom{11}{0}&lt;/math&gt; is equal to &lt;math&gt;\dbinom{11}{11}&lt;/math&gt;, so the case where no men are picked can be grouped with the case where all men are picked. When all men are picked, all females must also be picked, for a total of &lt;math&gt;\dbinom{12}{12}&lt;/math&gt;. Therefore, these cases can be combined to &lt;cmath&gt;\dbinom{11}{0} \cdot \left(\dbinom{12}{1} + \dbinom{12}{12}\right)&lt;/cmath&gt; Since &lt;math&gt;\dbinom{12}{12} = \dbinom{12}{0}&lt;/math&gt;, and &lt;math&gt;\dbinom{12}{0} + \dbinom{12}{1} = \dbinom{13}{1}&lt;/math&gt;, we can further simplify this to &lt;cmath&gt;\dbinom{11}{0} \cdot \dbinom{13}{1}&lt;/cmath&gt;<br /> <br /> All other cases proceed similarly. For example, the case with one men or ten men is equal to &lt;math&gt;\dbinom{11}{1} \cdot \dbinom{13}{2}&lt;/math&gt;. Now, if we factor out a &lt;math&gt;13&lt;/math&gt;, then all cases except the first two have a factor of &lt;math&gt;121&lt;/math&gt;, so we can factor this out too to make our computation slightly easier. The first two cases (with &lt;math&gt;13&lt;/math&gt; factored out) give &lt;math&gt;1+66=67&lt;/math&gt;, and the rest gives &lt;math&gt;121(10+75+270+504) = 103,939&lt;/math&gt;. Adding the &lt;math&gt;67&lt;/math&gt; gives &lt;math&gt;104,006&lt;/math&gt;. Now, we can test for prime factors. We know there is a factor of &lt;math&gt;2&lt;/math&gt;, and the rest is &lt;math&gt;52,003&lt;/math&gt;. We can also factor out a &lt;math&gt;7&lt;/math&gt;, for &lt;math&gt;7,429&lt;/math&gt;, and the rest is &lt;math&gt;17 \cdot 19 \cdot 23&lt;/math&gt;. Adding up all the prime factors gives &lt;math&gt;2+7+13+17+19+23 = \boxed{081}&lt;/math&gt;.<br /> <br /> == Solution 3 (Vandermonde's identity) ==<br /> Applying Vandermonde's identity by setting &lt;math&gt;m=12&lt;/math&gt;, &lt;math&gt;n=11&lt;/math&gt;, and &lt;math&gt;r=11&lt;/math&gt;, we obtain &lt;math&gt;\binom{23}{11}\implies&lt;/math&gt; &lt;math&gt;\boxed{081}&lt;/math&gt;.<br /> ~Lcz<br /> <br /> &lt;h3&gt;Short Proof&lt;/h3&gt;<br /> Consider the following setup:<br /> &lt;asy&gt;<br /> size(1000, 100);<br /> for(int i=0; i&lt;23; ++i){<br /> dot((i, 0));<br /> }<br /> draw((10.5, -1.5)--(10.5, 1.5), dashed);<br /> &lt;/asy&gt;<br /> The dots to the left represent the men, and the dots to the right represent the women. Now, suppose we put a mark on &lt;math&gt;11&lt;/math&gt; people (the &lt;math&gt;*&lt;/math&gt;). Those to the left of the dashed line get to be &quot;in&quot; on the committee if they have a mark. Those on the right side of the dashed line are already on the committee, but if they're marked they get forcibly evicted from it. If there were &lt;math&gt;x&lt;/math&gt; people marked on the left, there ends up being &lt;math&gt;12-(11-x) = x+1&lt;/math&gt; people not marked on the right. Circles represent those in the committee.<br /> &lt;asy&gt;<br /> size(1000, 100);<br /> for(int i=0; i&lt;23; ++i){<br /> dot((i, 0));<br /> }<br /> for(int i=0; i&lt;23; ++i){<br /> if(i%2==0){<br /> if(i &gt;= 11){<br /> draw(circle((i, 0), 0.25));<br /> }<br /> continue;<br /> }<br /> label(&quot;$*$&quot;, (i,0.5), N);<br /> if(i &lt; 11){<br /> draw(circle((i, 0), 0.25));<br /> }<br /> }<br /> draw((10.5, -1.5)--(10.5, 1.5), dashed);<br /> &lt;/asy&gt;<br /> <br /> We have our bijection, so the number of ways will be &lt;math&gt;\binom{23}{11}&lt;/math&gt;.<br /> <br /> ~programjames1<br /> <br /> &lt;h3&gt;Video Solution&lt;/h3&gt;: <br /> <br /> https://www.youtube.com/watch?v=vWEBfVjmS1Q<br /> <br /> == Solution 4 ==<br /> Notice that the committee can consist of &lt;math&gt;k&lt;/math&gt; boys and &lt;math&gt;k+1&lt;/math&gt; girls. Summing over all possible &lt;math&gt;k&lt;/math&gt; gives <br /> &lt;cmath&gt;\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{11}{0}\binom{12}{1}+\binom{11}{1}\binom{12}{2}+\cdots + \binom{11}{11}\binom{12}{12}&lt;/cmath&gt;<br /> Using the identity &lt;math&gt;\binom{n}{k}=\binom{n}{n-k}&lt;/math&gt;, and Pascal's Identity &lt;math&gt;\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}&lt;/math&gt;, we get<br /> &lt;cmath&gt;\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{12}{12}+\binom{12}{1}\left(\binom{11}{0}+\binom{11}{1}\right)+\cdots &lt;/cmath&gt;<br /> &lt;cmath&gt;=\binom{12}{0}^2+\binom{12}{1}^2+\binom{12}{2}^2+\binom{12}{3}^2+\binom{12}{4}^2+\binom{12}{5}^2+\frac{\binom{12}{6}^2}{2}&lt;/cmath&gt;<br /> &lt;cmath&gt;=\frac{1}{2}\sum_{k=0}^{12}\binom{12}{k}^2&lt;/cmath&gt;<br /> Using the identity &lt;math&gt;\sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}&lt;/math&gt;, this simplifies to <br /> &lt;cmath&gt;\frac{1}{2}\cdot \binom{24}{12}=\frac{24\cdot 23\cdot 22\cdot 21\cdot 20\cdot 19\cdot 18\cdot 17\cdot 16\cdot 15\cdot 14\cdot 13}{2\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2}=2\cdot 7\cdot 13\cdot 17\cdot 19\cdot 23&lt;/cmath&gt;<br /> so the desired answer is &lt;math&gt;2+7+13+17+19+23=\boxed{081}&lt;/math&gt; ~ktong<br /> <br /> ==See Also==<br /> <br /> {{AIME box|year=2020|n=I|num-b=6|num-a=8}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_7&diff=123132 2020 AIME I Problems/Problem 7 2020-05-28T03:31:23Z <p>Avn: /* Solution 3 (Vandermonde's identity) */</p> <hr /> <div><br /> == Problem ==<br /> A club consisting of &lt;math&gt;11&lt;/math&gt; men and &lt;math&gt;12&lt;/math&gt; women needs to choose a committee from among its members so that the number of women on the committee is one more than the number of men on the committee. The committee could have as few as &lt;math&gt;1&lt;/math&gt; member or as many as &lt;math&gt;23&lt;/math&gt; members. Let &lt;math&gt;N&lt;/math&gt; be the number of such committees that can be formed. Find the sum of the prime numbers that divide &lt;math&gt;N.&lt;/math&gt;<br /> <br /> == Solution 1 ==<br /> We will be selecting women, but &lt;i&gt;not&lt;/i&gt; selecting men. We claim that the amount of women selected and the amount of men not selected adds to &lt;math&gt;12&lt;/math&gt;. This is easy to see: if &lt;math&gt;k&lt;/math&gt; women were chosen, then &lt;math&gt;k + (11 - k + 1) = 12&lt;/math&gt;. Therefore, we simply take &lt;math&gt;\binom{23}{12} \implies \boxed{081}&lt;/math&gt;. ~awang11's sol<br /> <br /> == Solution 2 (Bash) ==<br /> <br /> We casework on the amount of men on the committee. <br /> <br /> If there are no men in the committee, there are &lt;math&gt;\dbinom{12}{1}&lt;/math&gt; ways to pick the women on the committee, for a total of &lt;math&gt;\dbinom{11}{0} \cdot \dbinom{12}{1}&lt;/math&gt;. Notice that &lt;math&gt;\dbinom{11}{0}&lt;/math&gt; is equal to &lt;math&gt;\dbinom{11}{11}&lt;/math&gt;, so the case where no men are picked can be grouped with the case where all men are picked. When all men are picked, all females must also be picked, for a total of &lt;math&gt;\dbinom{12}{12}&lt;/math&gt;. Therefore, these cases can be combined to &lt;cmath&gt;\dbinom{11}{0} \cdot \left(\dbinom{12}{1} + \dbinom{12}{12}\right)&lt;/cmath&gt; Since &lt;math&gt;\dbinom{12}{12} = \dbinom{12}{0}&lt;/math&gt;, and &lt;math&gt;\dbinom{12}{0} + \dbinom{12}{1} = \dbinom{13}{1}&lt;/math&gt;, we can further simplify this to &lt;cmath&gt;\dbinom{11}{0} \cdot \dbinom{13}{1}&lt;/cmath&gt;<br /> <br /> All other cases proceed similarly. For example, the case with one men or ten men is equal to &lt;math&gt;\dbinom{11}{1} \cdot \dbinom{13}{2}&lt;/math&gt;. Now, if we factor out a &lt;math&gt;13&lt;/math&gt;, then all cases except the first two have a factor of &lt;math&gt;121&lt;/math&gt;, so we can factor this out too to make our computation slightly easier. The first two cases (with &lt;math&gt;13&lt;/math&gt; factored out) give &lt;math&gt;1+66=67&lt;/math&gt;, and the rest gives &lt;math&gt;121(10+75+270+504) = 103,939&lt;/math&gt;. Adding the &lt;math&gt;67&lt;/math&gt; gives &lt;math&gt;104,006&lt;/math&gt;. Now, we can test for prime factors. We know there is a factor of &lt;math&gt;2&lt;/math&gt;, and the rest is &lt;math&gt;52,003&lt;/math&gt;. We can also factor out a &lt;math&gt;7&lt;/math&gt;, for &lt;math&gt;7,429&lt;/math&gt;, and the rest is &lt;math&gt;17 \cdot 19 \cdot 23&lt;/math&gt;. Adding up all the prime factors gives &lt;math&gt;2+7+13+17+19+23 = \boxed{081}&lt;/math&gt;.<br /> <br /> == Solution 3 (Vandermonde's identity) ==<br /> Applying Vandermonde's identity by setting &lt;math&gt;m=12&lt;/math&gt;, &lt;math&gt;n=11&lt;/math&gt;, and &lt;math&gt;r=11&lt;/math&gt;, we obtain &lt;math&gt;\binom{23}{11}\implies&lt;/math&gt; &lt;math&gt;\boxed{081}&lt;/math&gt;.<br /> ~Lcz<br /> <br /> &lt;h3&gt;Short Proof&lt;/h3&gt;<br /> Consider the following setup:<br /> &lt;asy&gt;<br /> size(1000, 100);<br /> for(int i=0; i&lt;23; ++i){<br /> dot((i, 0));<br /> }<br /> draw((10.5, -1.5)--(10.5, 1.5), dashed);<br /> &lt;/asy&gt;<br /> The dots to the left represent the men, and the dots to the right represent the women. Now, suppose we put a mark on &lt;math&gt;11&lt;/math&gt; people (the &lt;math&gt;*&lt;/math&gt;). Those to the left of the dashed line get to be &quot;in&quot; on the committee if they have a mark. Those on the right side of the dashed line are already on the committee, but if they're marked they get forcibly evicted from it. If there were &lt;math&gt;x&lt;/math&gt; people marked on the left, there ends up being &lt;math&gt;12-(11-x) = x+1&lt;/math&gt; people not marked on the right. Circles represent those in the committee.<br /> &lt;asy&gt;<br /> size(1000, 100);<br /> for(int i=0; i&lt;23; ++i){<br /> dot((i, 0));<br /> }<br /> for(int i=0; i&lt;23; ++i){<br /> if(i%2==0){<br /> if(i &gt;= 11){<br /> draw(circle((i, 0), 0.25));<br /> }<br /> continue;<br /> }<br /> label(&quot;$*$&quot;, (i,0.5), N);<br /> if(i &lt; 11){<br /> draw(circle((i, 0), 0.25));<br /> }<br /> }<br /> draw((10.5, -1.5)--(10.5, 1.5), dashed);<br /> &lt;/asy&gt;<br /> <br /> We have our bijection, so the number of ways will be &lt;math&gt;\binom{23}{11}&lt;/math&gt;.<br /> <br /> ~programjames1<br /> <br /> Video Solution: <br /> <br /> https://www.youtube.com/watch?v=vWEBfVjmS1Q<br /> <br /> == Solution 4 ==<br /> Notice that the committee can consist of &lt;math&gt;k&lt;/math&gt; boys and &lt;math&gt;k+1&lt;/math&gt; girls. Summing over all possible &lt;math&gt;k&lt;/math&gt; gives <br /> &lt;cmath&gt;\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{11}{0}\binom{12}{1}+\binom{11}{1}\binom{12}{2}+\cdots + \binom{11}{11}\binom{12}{12}&lt;/cmath&gt;<br /> Using the identity &lt;math&gt;\binom{n}{k}=\binom{n}{n-k}&lt;/math&gt;, and Pascal's Identity &lt;math&gt;\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}&lt;/math&gt;, we get<br /> &lt;cmath&gt;\sum_{k=0}^{11}\binom{11}{k}\binom{12}{k+1}=\binom{12}{12}+\binom{12}{1}\left(\binom{11}{0}+\binom{11}{1}\right)+\cdots &lt;/cmath&gt;<br /> &lt;cmath&gt;=\binom{12}{0}^2+\binom{12}{1}^2+\binom{12}{2}^2+\binom{12}{3}^2+\binom{12}{4}^2+\binom{12}{5}^2+\frac{\binom{12}{6}^2}{2}&lt;/cmath&gt;<br /> &lt;cmath&gt;=\frac{1}{2}\sum_{k=0}^{12}\binom{12}{k}^2&lt;/cmath&gt;<br /> Using the identity &lt;math&gt;\sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}&lt;/math&gt;, this simplifies to <br /> &lt;cmath&gt;\frac{1}{2}\cdot \binom{24}{12}=\frac{24\cdot 23\cdot 22\cdot 21\cdot 20\cdot 19\cdot 18\cdot 17\cdot 16\cdot 15\cdot 14\cdot 13}{2\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2}=2\cdot 7\cdot 13\cdot 17\cdot 19\cdot 23&lt;/cmath&gt;<br /> so the desired answer is &lt;math&gt;2+7+13+17+19+23=\boxed{081}&lt;/math&gt; ~ktong<br /> <br /> ==See Also==<br /> <br /> {{AIME box|year=2020|n=I|num-b=6|num-a=8}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_6&diff=122663 2020 AIME I Problems/Problem 6 2020-05-20T05:06:56Z <p>Avn: /* Solution */</p> <hr /> <div>== Problem ==<br /> A flat board has a circular hole with radius &lt;math&gt;1&lt;/math&gt; and a circular hole with radius &lt;math&gt;2&lt;/math&gt; such that the distance between the centers of the two holes is &lt;math&gt;7.&lt;/math&gt; Two spheres with equal radii sit in the two holes such that the spheres are tangent to each other. The square of the radius of the spheres is &lt;math&gt;\tfrac{m}{n},&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m+n.&lt;/math&gt;<br /> <br /> == Solution ==<br /> &lt;asy&gt;<br /> size(10cm);<br /> pair A, B, C, D, O, P, H, L, X, Y;<br /> A = (-1, 0);<br /> B = (1, 0);<br /> H = (0, 0);<br /> C = (5, 0);<br /> D = (9, 0);<br /> L = (7, 0);<br /> O = (0, sqrt(160/13 - 1));<br /> P = (7, sqrt(160/13 - 4));<br /> X = (0, sqrt(160/13 - 4));<br /> Y = (O + P) / 2;<br /> <br /> draw(A -- O -- B -- cycle);<br /> draw(C -- P -- D -- cycle);<br /> draw(B -- C);<br /> draw(O -- P);<br /> draw(P -- X, dashed);<br /> draw(O -- H, dashed);<br /> draw(P -- L, dashed);<br /> <br /> draw(circle(O, sqrt(160/13)));<br /> draw(circle(P, sqrt(160/13)));<br /> path b = brace(L, H);<br /> draw(b);<br /> <br /> label(&quot;$R$&quot;, O -- Y, N);<br /> label(&quot;$R$&quot;, Y -- P, N);<br /> label(&quot;$R$&quot;, O -- A, NW);<br /> label(&quot;$R$&quot;, P -- D, NE);<br /> label(&quot;$1$&quot;, A -- H, N);<br /> label(&quot;$2$&quot;, L -- D, N);<br /> label(&quot;$7$&quot;, b, S);<br /> &lt;/asy&gt;<br /> <br /> Set the common radius to &lt;math&gt;r&lt;/math&gt;. First, take the cross section of the sphere sitting in the hole of radius 1. If we draw the perpendicular bisector of the chord (the hole) through the circle, this line goes through the center. Connect the center also to where the chord hits the circle, for a right triangle with hypotenuse &lt;math&gt;r&lt;/math&gt; and base &lt;math&gt;1&lt;/math&gt;. Therefore, the height of this circle outside of the hole is &lt;math&gt;\sqrt{r^2-1}&lt;/math&gt;.<br /> <br /> The other circle follows similarly for a height (outside the hole) of &lt;math&gt;\sqrt{r^2-4}&lt;/math&gt;. Now, if we take the cross section of the entire board, essentially making it 2-D, we can connect the centers of the two spheres, then form another right triangle with base &lt;math&gt;7&lt;/math&gt;, as given by the problem. The height of this triangle is the difference between the heights of the parts of the two spheres outside the holes, which is &lt;math&gt;\sqrt{r^2-1} - \sqrt{r^2-4}&lt;/math&gt;. Now we can set up an equation in terms of &lt;math&gt;r&lt;/math&gt; with the Pythagorean theorem: &lt;cmath&gt;(\sqrt{r^2-1} - \sqrt{r^2-4})^2 + 7^2 = (2r)^2.&lt;/cmath&gt; Simplifying a few times, &lt;cmath&gt;r^2 - 1 - 2\left(\sqrt{(r^2-1)(r^2-4)}\right) + r^2 - 4 + 49 = 4r^2&lt;/cmath&gt; &lt;cmath&gt;2r^2-44= -2\left(\sqrt{(r^2-1)(r^2-4)}\right)&lt;/cmath&gt; &lt;cmath&gt;22-r^2=\left(\sqrt{r^4 - 5r^2 + 4}\right)&lt;/cmath&gt; &lt;cmath&gt;r^4 -44r^2 + 484 = r^4 - 5r^2 + 4&lt;/cmath&gt; &lt;cmath&gt;39r^2=480&lt;/cmath&gt; &lt;cmath&gt;r^2=\frac{480}{39} = \frac{160}{13}.&lt;/cmath&gt; Therefore, our answer is &lt;math&gt;\boxed{173}&lt;/math&gt;.<br /> <br /> -molocyxu<br /> <br /> Video Solution: <br /> <br /> https://www.youtube.com/watch?v=qCTq8KhZfYQ<br /> <br /> ==See Also==<br /> <br /> {{AIME box|year=2020|n=I|num-b=5|num-a=7}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_5&diff=122619 2020 AIME I Problems/Problem 5 2020-05-19T02:07:09Z <p>Avn: /* Solution 1 */</p> <hr /> <div><br /> == Problem ==<br /> Six cards numbered &lt;math&gt;1&lt;/math&gt; through &lt;math&gt;6&lt;/math&gt; are to be lined up in a row. Find the number of arrangements of these six cards where one of the cards can be removed leaving the remaining five cards in either ascending or descending order.<br /> <br /> == Solution 1 ==<br /> Realize that any sequence that works (ascending) can be reversed for descending, so we can just take the amount of sequences that satisfy the ascending condition and multiply by two.<br /> <br /> If we choose any of the numbers &lt;math&gt;1&lt;/math&gt; through &lt;math&gt;6&lt;/math&gt;, there are five other spots to put them, so we get &lt;math&gt;6 \cdot 5 = 30&lt;/math&gt;. However, we overcount some cases. Take the example of &lt;math&gt;132456&lt;/math&gt;. We overcount this case because we can remove the &lt;math&gt;3&lt;/math&gt; or the &lt;math&gt;2&lt;/math&gt;. Therefore, any cases with two adjacent numbers swapped is overcounted, so we subtract &lt;math&gt;5&lt;/math&gt; cases (namely, &lt;math&gt;213456, 132456, 124356, 123546, 123465&lt;/math&gt;,) to get &lt;math&gt;30-5=25&lt;/math&gt;, but we have to add back one more for the original case, &lt;math&gt;123456&lt;/math&gt;. Therefore, there are &lt;math&gt;26&lt;/math&gt; cases. Multiplying by &lt;math&gt;2&lt;/math&gt; gives the desired answer, &lt;math&gt;\boxed{052}&lt;/math&gt;.<br /> <br /> -molocyxu<br /> <br /> Video Solution: <br /> <br /> https://www.youtube.com/watch?v=E6YJh7vsLPU<br /> <br /> == Solution 2 (Inspired by 2018 CMIMC combo round) ==<br /> <br /> Similar to above, a &lt;math&gt;1-1&lt;/math&gt; correspondence between ascending and descending is established by subtracting each number from &lt;math&gt;7&lt;/math&gt;.<br /> <br /> We note that the given condition is equivalent to &quot;cycling&quot; &lt;math&gt;123456&lt;/math&gt; for a contiguous subset of it. For example, <br /> <br /> &lt;math&gt;12(345)6 \rightarrow 125346, 124536&lt;/math&gt;<br /> <br /> It's not hard to see that no overcount is possible, and that the cycle is either &lt;math&gt;1&lt;/math&gt; &quot;right&quot; or &lt;math&gt;1&lt;/math&gt; &quot;left.&quot; Therefore, we consider how many elements we flip by. If we flip &lt;math&gt;1&lt;/math&gt; or &lt;math&gt;2&lt;/math&gt; such elements, then there is one way to cycle them. Otherwise, we have &lt;math&gt;2&lt;/math&gt; ways. Therefore, the total number of ascending is &lt;math&gt;1 + 5 + 2(4 + 3 + 2 + 1) = 26&lt;/math&gt;, and multiplying by two gives &lt;math&gt;\boxed{052}.&lt;/math&gt; ~awang11<br /> <br /> == Solution 3 ==<br /> Similarly to above, we find the number of ascending arrangements and multiply by 2. <br /> <br /> We can choose &lt;math&gt;5&lt;/math&gt; cards to be the ascending cards, therefore leaving &lt;math&gt;6&lt;/math&gt; places to place the remaining card. There are &lt;math&gt;\binom{6}{5}\cdot 6=36&lt;/math&gt; to do this. However, since the problem is asking for the number of arrangements, we overcount cases such as &lt;math&gt;123456&lt;/math&gt;. Notice that the only arrangements that overcount are &lt;math&gt;123456&lt;/math&gt; (case 1) or if two adjacent numbers of &lt;math&gt;123456&lt;/math&gt; are switched (case 2).<br /> <br /> &lt;math&gt;\text{Case 1: } &lt;/math&gt; This arrangement is counted &lt;math&gt;6&lt;/math&gt; times. Each time it is counted for any of the &lt;math&gt;5&lt;/math&gt; numbers selected. Therefore we need to subtract &lt;math&gt;5&lt;/math&gt; cases of overcounting.<br /> <br /> &lt;math&gt;\text{Case 2: }&lt;/math&gt; Each time &lt;math&gt;2&lt;/math&gt; adjacent numbers of switched, there is one overcount. For example, if we have &lt;math&gt;213456&lt;/math&gt;, both &lt;math&gt;1&lt;/math&gt; or &lt;math&gt;2&lt;/math&gt; could be removed. Since there are &lt;math&gt;5&lt;/math&gt; possible switches, we need to subtract &lt;math&gt;5&lt;/math&gt; cases of overcounting.<br /> <br /> Therefore, we have &lt;math&gt;36-5-5=26&lt;/math&gt; total arrangements of ascending numbers. We multiply by two (for descending) to get the answer of &lt;math&gt;\boxed{052}.&lt;/math&gt; -PCChess<br /> <br /> == Solution 4 (No overcounting) ==<br /> Like in previous solutions, we will count the number of ascending arrangements and multiply by 2. <br /> <br /> First, consider the arrangement 1-2-3-4-5-6. That gives us 1 arrangement which works. <br /> <br /> Next, we can switch two adjacent cards. There are 5 ways to pick two adjacent cards, so this gives us 5 arrangements.<br /> <br /> Now, we can &quot;cycle&quot; 3 adjacent cards. For example, 1-2-3 becomes 2-3-1 which becomes 3-1-2. There are 4 ways to pick a set of 3 adjacent cards, so this gives us 4x2=8 arrangements.<br /> <br /> Cycling 4 adjacent cards, we get the new arrangements 2-3-4-1 (which works,) 3-4-1-2 (which doesn't work,) and 4-1-2-3 (which does work.) We get 6 arrangements.<br /> <br /> Similarly, when cycling 5 cards, we find 2x2=4 arrangements, and when cycling 6 cards, we find 2x1=2 arrangements.<br /> <br /> Adding, we figure out that there are 1+5+8+6+4+2=26 ascending arrangements. Multiplying by 2, we get the answer &lt;math&gt;\boxed{052}.&lt;/math&gt; -i8Pie<br /> <br /> ==See Also==<br /> <br /> {{AIME box|year=2020|n=I|num-b=4|num-a=6}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_5&diff=122618 2020 AIME I Problems/Problem 5 2020-05-19T02:04:59Z <p>Avn: /* Solution 1 */</p> <hr /> <div><br /> == Problem ==<br /> Six cards numbered &lt;math&gt;1&lt;/math&gt; through &lt;math&gt;6&lt;/math&gt; are to be lined up in a row. Find the number of arrangements of these six cards where one of the cards can be removed leaving the remaining five cards in either ascending or descending order.<br /> <br /> == Solution 1 ==<br /> Realize that any sequence that works (ascending) can be reversed for descending, so we can just take the amount of sequences that satisfy the ascending condition and multiply by two.<br /> <br /> If we choose any of the numbers &lt;math&gt;1&lt;/math&gt; through &lt;math&gt;6&lt;/math&gt;, there are five other spots to put them, so we get &lt;math&gt;6 \cdot 5 = 30&lt;/math&gt;. However, we overcount some cases. Take the example of &lt;math&gt;132456&lt;/math&gt;. We overcount this case because we can remove the &lt;math&gt;3&lt;/math&gt; or the &lt;math&gt;2&lt;/math&gt;. Therefore, any cases with two adjacent numbers swapped is overcounted, so we subtract &lt;math&gt;5&lt;/math&gt; cases (namely, &lt;math&gt;213456, 132456, 124356, 123546, 123465&lt;/math&gt;,) to get &lt;math&gt;30-5=25&lt;/math&gt;, but we have to add back one more for the original case, &lt;math&gt;123456&lt;/math&gt;. Therefore, there are &lt;math&gt;26&lt;/math&gt; cases. Multiplying by &lt;math&gt;2&lt;/math&gt; gives the desired answer, &lt;math&gt;\boxed{052}&lt;/math&gt;.<br /> <br /> -molocyxu<br /> <br /> Video Solution: <br /> <br /> https://www.youtube.com/watch?v=E6YJh7vsLPU&amp;feature=youtu.be<br /> <br /> == Solution 2 (Inspired by 2018 CMIMC combo round) ==<br /> <br /> Similar to above, a &lt;math&gt;1-1&lt;/math&gt; correspondence between ascending and descending is established by subtracting each number from &lt;math&gt;7&lt;/math&gt;.<br /> <br /> We note that the given condition is equivalent to &quot;cycling&quot; &lt;math&gt;123456&lt;/math&gt; for a contiguous subset of it. For example, <br /> <br /> &lt;math&gt;12(345)6 \rightarrow 125346, 124536&lt;/math&gt;<br /> <br /> It's not hard to see that no overcount is possible, and that the cycle is either &lt;math&gt;1&lt;/math&gt; &quot;right&quot; or &lt;math&gt;1&lt;/math&gt; &quot;left.&quot; Therefore, we consider how many elements we flip by. If we flip &lt;math&gt;1&lt;/math&gt; or &lt;math&gt;2&lt;/math&gt; such elements, then there is one way to cycle them. Otherwise, we have &lt;math&gt;2&lt;/math&gt; ways. Therefore, the total number of ascending is &lt;math&gt;1 + 5 + 2(4 + 3 + 2 + 1) = 26&lt;/math&gt;, and multiplying by two gives &lt;math&gt;\boxed{052}.&lt;/math&gt; ~awang11<br /> <br /> == Solution 3 ==<br /> Similarly to above, we find the number of ascending arrangements and multiply by 2. <br /> <br /> We can choose &lt;math&gt;5&lt;/math&gt; cards to be the ascending cards, therefore leaving &lt;math&gt;6&lt;/math&gt; places to place the remaining card. There are &lt;math&gt;\binom{6}{5}\cdot 6=36&lt;/math&gt; to do this. However, since the problem is asking for the number of arrangements, we overcount cases such as &lt;math&gt;123456&lt;/math&gt;. Notice that the only arrangements that overcount are &lt;math&gt;123456&lt;/math&gt; (case 1) or if two adjacent numbers of &lt;math&gt;123456&lt;/math&gt; are switched (case 2).<br /> <br /> &lt;math&gt;\text{Case 1: } &lt;/math&gt; This arrangement is counted &lt;math&gt;6&lt;/math&gt; times. Each time it is counted for any of the &lt;math&gt;5&lt;/math&gt; numbers selected. Therefore we need to subtract &lt;math&gt;5&lt;/math&gt; cases of overcounting.<br /> <br /> &lt;math&gt;\text{Case 2: }&lt;/math&gt; Each time &lt;math&gt;2&lt;/math&gt; adjacent numbers of switched, there is one overcount. For example, if we have &lt;math&gt;213456&lt;/math&gt;, both &lt;math&gt;1&lt;/math&gt; or &lt;math&gt;2&lt;/math&gt; could be removed. Since there are &lt;math&gt;5&lt;/math&gt; possible switches, we need to subtract &lt;math&gt;5&lt;/math&gt; cases of overcounting.<br /> <br /> Therefore, we have &lt;math&gt;36-5-5=26&lt;/math&gt; total arrangements of ascending numbers. We multiply by two (for descending) to get the answer of &lt;math&gt;\boxed{052}.&lt;/math&gt; -PCChess<br /> <br /> == Solution 4 (No overcounting) ==<br /> Like in previous solutions, we will count the number of ascending arrangements and multiply by 2. <br /> <br /> First, consider the arrangement 1-2-3-4-5-6. That gives us 1 arrangement which works. <br /> <br /> Next, we can switch two adjacent cards. There are 5 ways to pick two adjacent cards, so this gives us 5 arrangements.<br /> <br /> Now, we can &quot;cycle&quot; 3 adjacent cards. For example, 1-2-3 becomes 2-3-1 which becomes 3-1-2. There are 4 ways to pick a set of 3 adjacent cards, so this gives us 4x2=8 arrangements.<br /> <br /> Cycling 4 adjacent cards, we get the new arrangements 2-3-4-1 (which works,) 3-4-1-2 (which doesn't work,) and 4-1-2-3 (which does work.) We get 6 arrangements.<br /> <br /> Similarly, when cycling 5 cards, we find 2x2=4 arrangements, and when cycling 6 cards, we find 2x1=2 arrangements.<br /> <br /> Adding, we figure out that there are 1+5+8+6+4+2=26 ascending arrangements. Multiplying by 2, we get the answer &lt;math&gt;\boxed{052}.&lt;/math&gt; -i8Pie<br /> <br /> ==See Also==<br /> <br /> {{AIME box|year=2020|n=I|num-b=4|num-a=6}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_4&diff=122017 2020 AIME I Problems/Problem 4 2020-05-04T22:00:09Z <p>Avn: /* Solution */</p> <hr /> <div><br /> == Problem ==<br /> Let &lt;math&gt;S&lt;/math&gt; be the set of positive integers &lt;math&gt;N&lt;/math&gt; with the property that the last four digits of &lt;math&gt;N&lt;/math&gt; are &lt;math&gt;2020,&lt;/math&gt; and when the last four digits are removed, the result is a divisor of &lt;math&gt;N.&lt;/math&gt; For example, &lt;math&gt;42,020&lt;/math&gt; is in &lt;math&gt;S&lt;/math&gt; because &lt;math&gt;4&lt;/math&gt; is a divisor of &lt;math&gt;42,020.&lt;/math&gt; Find the sum of all the digits of all the numbers in &lt;math&gt;S.&lt;/math&gt; For example, the number &lt;math&gt;42,020&lt;/math&gt; contributes &lt;math&gt;4+2+0+2+0=8&lt;/math&gt; to this total.<br /> <br /> == Solution ==<br /> <br /> We note that any number in &lt;math&gt;S&lt;/math&gt; can be expressed as &lt;math&gt;a(10,000) + 2,020&lt;/math&gt; for some integer &lt;math&gt;a&lt;/math&gt;. The problem requires that &lt;math&gt;a&lt;/math&gt; divides this number, and since we know &lt;math&gt;a&lt;/math&gt; divides &lt;math&gt;a(10,000)&lt;/math&gt;, we need that &lt;math&gt;a&lt;/math&gt; divides 2020. Each number contributes the sum of the digits of &lt;math&gt;a&lt;/math&gt;, as well as &lt;math&gt;2 + 0 + 2 +0 = 4&lt;/math&gt;. Since &lt;math&gt;2020&lt;/math&gt; can be prime factorized as &lt;math&gt;2^2 \cdot 5 \cdot 101&lt;/math&gt;, it has &lt;math&gt;(2+1)(1+1)(1+1) = 12&lt;/math&gt; factors. So if we sum all the digits of all possible &lt;math&gt;a&lt;/math&gt; values, and add &lt;math&gt;4 \cdot 12 = 48&lt;/math&gt;, we obtain the answer.<br /> <br /> Now we list out all factors of &lt;math&gt;2,020&lt;/math&gt;, or all possible values of &lt;math&gt;a&lt;/math&gt;. &lt;math&gt;1,2,4,5,10,20,101,202,404,505,1010,2020&lt;/math&gt;. If we add up these digits, we get &lt;math&gt;45&lt;/math&gt;, for a final answer of &lt;math&gt;45+48=\boxed{093}&lt;/math&gt;.<br /> <br /> -molocyxu<br /> <br /> Video solution: <br /> <br /> https://youtu.be/djWzRC-jGYw<br /> <br /> ==See Also==<br /> <br /> {{AIME box|year=2020|n=I|num-b=3|num-a=5}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_3&diff=121240 2020 AIME I Problems/Problem 3 2020-04-20T20:01:31Z <p>Avn: /* Solution */</p> <hr /> <div><br /> == Problem ==<br /> A positive integer &lt;math&gt;N&lt;/math&gt; has base-eleven representation &lt;math&gt;\underline{a}\kern 0.1em\underline{b}\kern 0.1em\underline{c}&lt;/math&gt; and base-eight representation &lt;math&gt;\underline1\kern 0.1em\underline{b}\kern 0.1em\underline{c}\kern 0.1em\underline{a},&lt;/math&gt; where &lt;math&gt;a,b,&lt;/math&gt; and &lt;math&gt;c&lt;/math&gt; represent (not necessarily distinct) digits. Find the least such &lt;math&gt;N&lt;/math&gt; expressed in base ten.<br /> <br /> == Solution ==<br /> From the given information, &lt;math&gt;121a+11b+c=512+64b+8c+a \implies 120a=512+53b+7c&lt;/math&gt;. Since &lt;math&gt;a&lt;/math&gt;, &lt;math&gt;b&lt;/math&gt;, and &lt;math&gt;c&lt;/math&gt; have to be positive, &lt;math&gt;a \geq 5&lt;/math&gt;. Since we need to minimize the value of &lt;math&gt;n&lt;/math&gt;, we want to minimize &lt;math&gt;a&lt;/math&gt;, so we have &lt;math&gt;a = 5&lt;/math&gt;. Then we know &lt;math&gt;88=53b+7c&lt;/math&gt;, and we can see the only solution is &lt;math&gt;b=1&lt;/math&gt;, &lt;math&gt;c=5&lt;/math&gt;. Finally, &lt;math&gt;515_{11} = 621_{10}&lt;/math&gt;, so our answer is &lt;math&gt;\boxed{621}&lt;/math&gt;.<br /> <br /> ~ JHawk0224<br /> <br /> Video Solution: <br /> <br /> https://youtu.be/hZSBUXCX5hI<br /> <br /> ==See Also==<br /> <br /> {{AIME box|year=2020|n=I|num-b = 2|num-a=4}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_2&diff=121182 2020 AIME I Problems/Problem 2 2020-04-20T15:37:51Z <p>Avn: /* Solution */</p> <hr /> <div><br /> == Problem ==<br /> There is a unique positive real number &lt;math&gt;x&lt;/math&gt; such that the three numbers &lt;math&gt;\log_8{2x}&lt;/math&gt;, &lt;math&gt;\log_4{x}&lt;/math&gt;, and &lt;math&gt;\log_2{x}&lt;/math&gt;, in that order, form a geometric progression with positive common ratio. The number &lt;math&gt;x&lt;/math&gt; can be written as &lt;math&gt;\frac{m}{n}&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m + n&lt;/math&gt;.<br /> <br /> == Solution ==<br /> Since these form a geometric series, &lt;math&gt;\frac{\log_2{x}}{\log_4{x}}&lt;/math&gt; is the common ratio. Rewriting this, we get &lt;math&gt;\frac{\log_x{4}}{\log_x{2}} = \log_2{4} = 2&lt;/math&gt; by base change formula. Therefore, the common ratio is 2. Now &lt;math&gt;\frac{\log_4{x}}{\log_8{2x}} = 2 \implies \log_4{x} = 2\log_8{2} + 2\log_8{x} \implies \frac{1}{2}\log_2{x} = \frac{2}{3} + \frac{2}{3}\log_2{x}&lt;/math&gt;<br /> <br /> &lt;math&gt;\implies -\frac{1}{6}\log_2{x} = \frac{2}{3} \implies \log_2{x} = -4 \implies x = \frac{1}{16}&lt;/math&gt;. Therefore, &lt;math&gt;1 + 16 = \boxed{017}&lt;/math&gt;.<br /> <br /> ~ JHawk0224<br /> <br /> See here for a video solution:<br /> <br /> https://youtu.be/nPL7nUXnRbo<br /> <br /> Another video solution: <br /> <br /> https://youtu.be/4FvYVfhhTaQ<br /> <br /> ==Solution 2==<br /> If we set &lt;math&gt;x=2^y&lt;/math&gt;, we can obtain three terms of a geometric sequence through logarithm properties. The three terms are &lt;cmath&gt;\frac{y+1}{3}, \frac{y}{2}, y.&lt;/cmath&gt; In a three-term geometric sequence, the middle term squared is equal to the product of the other two terms, so we obtain the following: &lt;cmath&gt;\frac{y^2+y}{3} = \frac{y^2}{4},&lt;/cmath&gt; which can be solved to reveal &lt;math&gt;y = -4&lt;/math&gt;. Therefore, &lt;math&gt;x = 2^{-4} = \frac{1}{16}&lt;/math&gt;, so our answer is &lt;math&gt;\boxed{017}&lt;/math&gt;.<br /> <br /> -molocyxu<br /> <br /> ==Solution 3==<br /> Let &lt;math&gt;r&lt;/math&gt; be the common ratio. We have &lt;cmath&gt; r = \frac{\log_4{(x)}}{\log_8{(2x)}} = \frac{\log_2{(x)}}{\log_4{(x)}}&lt;/cmath&gt;<br /> Hence we obtain &lt;cmath&gt; (\log_4{(x)})(\log_4{(x)}) = (\log_8{(2x)})(\log_2{(x)})&lt;/cmath&gt;<br /> Ideally we change everything to base &lt;math&gt;64&lt;/math&gt; and we can get: &lt;cmath&gt; (\log_{64}{(x^3)})(\log_{64}{(x^3)}) = (\log_{64}{(x^6)})(\log_{64}{(4x^2)})&lt;/cmath&gt;<br /> Now divide to get: &lt;cmath&gt;\frac{\log_{64}{(x^3)}}{\log_{64}{(4x^2)}} = \frac{\log_{64}{(x^6)}}{\log_{64}{(x^3)}}&lt;/cmath&gt;<br /> By change-of-base we obtain: &lt;cmath&gt;\log_{(4x^2)}{(x^3)} = \log_{(x^3)}{(x^6)} = 2&lt;/cmath&gt;<br /> Hence &lt;math&gt;(4x^2)^2 = x^3 \rightarrow 16x^4 = x^3 \rightarrow x = \frac{1}{16}&lt;/math&gt; and we have &lt;math&gt;1+16 = \boxed{017}&lt;/math&gt; as desired.<br /> <br /> ~skyscraper<br /> <br /> ==Solution 4 (Exponents &gt; Logarithms)==<br /> Let &lt;math&gt;r&lt;/math&gt; be the common ratio, and let &lt;math&gt;a&lt;/math&gt; be the starting term (&lt;math&gt;a=\log_{8}{(2x)}&lt;/math&gt;). We then have: &lt;cmath&gt;\log_{8}{(2x)}=a, \log_{4}{(x)}=ar, \log_{2}{(x)}=ar^2&lt;/cmath&gt; Rearranging these equations gives: &lt;cmath&gt;8^a=2x, 4^{ar}=x, 2^{ar^2}=x&lt;/cmath&gt;<br /> Deal with the last two equations first: Setting them equal gives: &lt;cmath&gt;4^{ar}=2^{ar^2} \Rightarrow 2^{2ar}=2^{ar^2}&lt;/cmath&gt; Using LTE results in: &lt;cmath&gt;2ar=ar^2 \Rightarrow r=2&lt;/cmath&gt; Using this value of &lt;math&gt;r&lt;/math&gt;, substitute into the first and second equations (or the first and third, it doesn't really matter) to get: &lt;cmath&gt;8^a=2x, 4^{2a}=x&lt;/cmath&gt; Changing these to a common base gives: &lt;cmath&gt;2^{3a}=2x, 2^{4a}=x&lt;/cmath&gt; Dividing the first equation by 2 on both sides yields: &lt;cmath&gt;2^{3a-1}=x&lt;/cmath&gt; Setting these equations equal to each other and applying LTE again gives: &lt;cmath&gt;3a-1=4a \Rightarrow a=-1&lt;/cmath&gt; Substituting this back into the first equation gives: &lt;cmath&gt;8^{-1}=2x \Rightarrow 2x=\frac{1}{8} \Rightarrow x=\frac{1}{16}&lt;/cmath&gt; Therefore, &lt;math&gt;m+n=1+16=\boxed{017}&lt;/math&gt;<br /> <br /> ~IAmTheHazard<br /> <br /> ==Solution 5==<br /> <br /> We can relate the logarithms as follows:<br /> <br /> &lt;cmath&gt;\frac{\log_4{x}}{\log_8{(2x)}}=\frac{\log_2{x}}{\log_4{x}}&lt;/cmath&gt;<br /> &lt;cmath&gt;\log_8{(2x)}\log_2{x}=\log_4{x}\log_4{x}&lt;/cmath&gt;<br /> <br /> Now we can convert all logarithm bases to &lt;math&gt;2&lt;/math&gt; using the identity &lt;math&gt;\log_a{b}=\log_{a^c}{b^c}&lt;/math&gt;:<br /> <br /> &lt;cmath&gt;\log_2{\sqrt{2x}}\log_2{x}=\log_2{\sqrt{x}}\log_2{\sqrt{x}}&lt;/cmath&gt;<br /> <br /> We can solve for &lt;math&gt;x&lt;/math&gt; as follows:<br /> <br /> &lt;cmath&gt;\frac{1}{3}\log_2{(2x)}\log_2{x}=\frac{1}{4}\log_2{x}\log_2{x}&lt;/cmath&gt;<br /> &lt;cmath&gt;\frac{1}{3}\log_2{(2x)}=\frac{1}{4}\log_2{x}&lt;/cmath&gt;<br /> &lt;cmath&gt;\frac{1}{3}\log_2{2}+\frac{1}{3}\log_2{x}=\frac{1}{4}\log_2{x}&lt;/cmath&gt;<br /> We get &lt;math&gt;x=\frac{1}{16}&lt;/math&gt;. Verifying that the common ratio is positive, we find the answer of &lt;math&gt;\boxed{017}&lt;/math&gt;.<br /> <br /> ~QIDb602<br /> <br /> <br /> ==Solution 6==<br /> <br /> If the numbers are in a geometric sequence, the middle term must be the geometric mean of the surrounding terms. We can rewrite the first two logarithmic expressions as &lt;math&gt;\frac{1+\log_2{x}}{3}&lt;/math&gt; and &lt;math&gt;\frac{1}{2}\log_2{x}&lt;/math&gt;, respectively. Therefore:<br /> &lt;cmath&gt;\frac{1}{2}\log_2{x}=\sqrt{\left(\frac{1+\log_2{x}}{3}\right)\left(\log_2{x}\right)}&lt;/cmath&gt;<br /> Let &lt;math&gt;n=\log_2{x}&lt;/math&gt;. We can rewrite the expression as:<br /> &lt;cmath&gt;\frac{n}{2}=\sqrt{\frac{n(n+1)}{3}}&lt;/cmath&gt;<br /> &lt;cmath&gt;\frac{n^2}{4}=\frac{n(n+1)}{3}&lt;/cmath&gt;<br /> &lt;cmath&gt;4n(n+1)=3n^2&lt;/cmath&gt;<br /> &lt;cmath&gt;4n^2+4n=3n^2&lt;/cmath&gt;<br /> &lt;cmath&gt;n^2+4n=0&lt;/cmath&gt;<br /> &lt;cmath&gt;n(n+4)=0&lt;/cmath&gt;<br /> &lt;cmath&gt;n=0 \text{ and } -4&lt;/cmath&gt;<br /> Zero does not work in this case, so we consider &lt;math&gt;n=-4&lt;/math&gt;: &lt;math&gt;\log_2{x}=-4 \rightarrow x=\frac{1}{16}&lt;/math&gt;. Therefore, &lt;math&gt;1+16=\boxed{017}&lt;/math&gt;.<br /> <br /> ~Bowser498<br /> <br /> See here for a video solution:<br /> <br /> https://youtu.be/nPL7nUXnRbo<br /> <br /> ==See Also==<br /> <br /> {{AIME box|year=2020|n=I|num-b=1|num-a=3}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_1&diff=121181 2020 AIME I Problems/Problem 1 2020-04-20T15:35:54Z <p>Avn: /* Solution 1 */</p> <hr /> <div><br /> == Problem ==<br /> In &lt;math&gt;\triangle ABC&lt;/math&gt; with &lt;math&gt;AB=AC,&lt;/math&gt; point &lt;math&gt;D&lt;/math&gt; lies strictly between &lt;math&gt;A&lt;/math&gt; and &lt;math&gt;C&lt;/math&gt; on side &lt;math&gt;\overline{AC},&lt;/math&gt; and point &lt;math&gt;E&lt;/math&gt; lies strictly between &lt;math&gt;A&lt;/math&gt; and &lt;math&gt;B&lt;/math&gt; on side &lt;math&gt;\overline{AB}&lt;/math&gt; such that &lt;math&gt;AE=ED=DB=BC.&lt;/math&gt; The degree measure of &lt;math&gt;\angle ABC&lt;/math&gt; is &lt;math&gt;\tfrac{m}{n},&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m+n.&lt;/math&gt;<br /> <br /> == Solution 1==<br /> &lt;asy&gt;<br /> size(10cm);<br /> pair A, B, C, D, F;<br /> A = (0, tan(3 * pi / 7));<br /> B = (1, 0);<br /> C = (-1, 0);<br /> F = rotate(90/7, A) * (A - (0, 2));<br /> D = rotate(900/7, F) * A;<br /> <br /> draw(A -- B -- C -- cycle);<br /> draw(F -- D);<br /> draw(D -- B);<br /> <br /> label(&quot;$A$&quot;, A, N);<br /> label(&quot;$B$&quot;, B, E);<br /> label(&quot;$C$&quot;, C, W);<br /> label(&quot;$D$&quot;, D, W);<br /> label(&quot;$E$&quot;, F, E);<br /> &lt;/asy&gt;<br /> <br /> If we set &lt;math&gt;\angle{BAC}&lt;/math&gt; to &lt;math&gt;x&lt;/math&gt;, we can find all other angles through these two properties:<br /> 1. Angles in a triangle sum to &lt;math&gt;180^{\circ}&lt;/math&gt;.<br /> 2. The base angles of an isoceles triangle are congruent.<br /> <br /> Now we angle chase. &lt;math&gt;\angle{ADE}=\angle{EAD}=x&lt;/math&gt;, &lt;math&gt;\angle{AED} = 180-2x&lt;/math&gt;, &lt;math&gt;\angle{BED}=\angle{EBD}=2x&lt;/math&gt;, &lt;math&gt;\angle{EDB} = 180-4x&lt;/math&gt;, &lt;math&gt;\angle{BDC} = \angle{BCD} = 3x&lt;/math&gt;, &lt;math&gt;\angle{CBD} = 180-6x&lt;/math&gt;. Since &lt;math&gt;AB = AC&lt;/math&gt; as given by the problem, &lt;math&gt;\angle{ABC} = \angle{ACB}&lt;/math&gt;, so &lt;math&gt;180-4x=3x&lt;/math&gt;. Therefore, &lt;math&gt;x = 180/7^{\circ}&lt;/math&gt;, and our desired angle is &lt;cmath&gt;180-4\left(\frac{180}{7}\right) = \frac{540}{7}&lt;/cmath&gt; for an answer of &lt;math&gt;\boxed{547}&lt;/math&gt;.<br /> <br /> See here for a video solution: https://youtu.be/4e8Hk04Ax_E<br /> <br /> ==Solution 2==<br /> Let &lt;math&gt;\angle{BAC}&lt;/math&gt; be &lt;math&gt;x&lt;/math&gt; in degrees. &lt;math&gt;\angle{ADE}=x&lt;/math&gt;.<br /> By Exterior Angle Theorem on triangle &lt;math&gt;AED&lt;/math&gt;, &lt;math&gt;\angle{BED}=2x&lt;/math&gt;.<br /> By Exterior Angle Theorem on triangle &lt;math&gt;ADB&lt;/math&gt;, &lt;math&gt;\angle{BDC}=3x&lt;/math&gt;.<br /> This tells us &lt;math&gt;\angle{BCA}=\angle{ABC}=3x&lt;/math&gt; and &lt;math&gt;3x+3x+x=180&lt;/math&gt;.<br /> Thus &lt;math&gt;x=\frac{180}{7}&lt;/math&gt; and we want &lt;math&gt;\angle{ABC}=3x=\frac{540}{7}&lt;/math&gt; to get an answer of &lt;math&gt;\boxed{547}&lt;/math&gt;.<br /> <br /> <br /> https://artofproblemsolving.com/wiki/index.php/1961_AHSME_Problems/Problem_25<br /> (Almost Mirrored)<br /> <br /> See here for a video solution:<br /> <br /> https://youtu.be/4XkA0DwuqYk<br /> <br /> ==See Also==<br /> <br /> {{AIME box|year=2020|n=I|before=First Problem|num-a=2}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_1&diff=121180 2020 AIME I Problems/Problem 1 2020-04-20T15:31:49Z <p>Avn: /* Solution 1 */</p> <hr /> <div><br /> == Problem ==<br /> In &lt;math&gt;\triangle ABC&lt;/math&gt; with &lt;math&gt;AB=AC,&lt;/math&gt; point &lt;math&gt;D&lt;/math&gt; lies strictly between &lt;math&gt;A&lt;/math&gt; and &lt;math&gt;C&lt;/math&gt; on side &lt;math&gt;\overline{AC},&lt;/math&gt; and point &lt;math&gt;E&lt;/math&gt; lies strictly between &lt;math&gt;A&lt;/math&gt; and &lt;math&gt;B&lt;/math&gt; on side &lt;math&gt;\overline{AB}&lt;/math&gt; such that &lt;math&gt;AE=ED=DB=BC.&lt;/math&gt; The degree measure of &lt;math&gt;\angle ABC&lt;/math&gt; is &lt;math&gt;\tfrac{m}{n},&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m+n.&lt;/math&gt;<br /> <br /> == Solution 1==<br /> &lt;asy&gt;<br /> size(10cm);<br /> pair A, B, C, D, F;<br /> A = (0, tan(3 * pi / 7));<br /> B = (1, 0);<br /> C = (-1, 0);<br /> F = rotate(90/7, A) * (A - (0, 2));<br /> D = rotate(900/7, F) * A;<br /> <br /> draw(A -- B -- C -- cycle);<br /> draw(F -- D);<br /> draw(D -- B);<br /> <br /> label(&quot;$A$&quot;, A, N);<br /> label(&quot;$B$&quot;, B, E);<br /> label(&quot;$C$&quot;, C, W);<br /> label(&quot;$D$&quot;, D, W);<br /> label(&quot;$E$&quot;, F, E);<br /> &lt;/asy&gt;<br /> <br /> If we set &lt;math&gt;\angle{BAC}&lt;/math&gt; to &lt;math&gt;x&lt;/math&gt;, we can find all other angles through these two properties:<br /> 1. Angles in a triangle sum to &lt;math&gt;180^{\circ}&lt;/math&gt;.<br /> 2. The base angles of an isoceles triangle are congruent.<br /> <br /> Now we angle chase. &lt;math&gt;\angle{ADE}=\angle{EAD}=x&lt;/math&gt;, &lt;math&gt;\angle{AED} = 180-2x&lt;/math&gt;, &lt;math&gt;\angle{BED}=\angle{EBD}=2x&lt;/math&gt;, &lt;math&gt;\angle{EDB} = 180-4x&lt;/math&gt;, &lt;math&gt;\angle{BDC} = \angle{BCD} = 3x&lt;/math&gt;, &lt;math&gt;\angle{CBD} = 180-6x&lt;/math&gt;. Since &lt;math&gt;AB = AC&lt;/math&gt; as given by the problem, &lt;math&gt;\angle{ABC} = \angle{ACB}&lt;/math&gt;, so &lt;math&gt;180-4x=3x&lt;/math&gt;. Therefore, &lt;math&gt;x = 180/7^{\circ}&lt;/math&gt;, and our desired angle is &lt;cmath&gt;180-4\left(\frac{180}{7}\right) = \frac{540}{7}&lt;/cmath&gt; for an answer of &lt;math&gt;\boxed{547}&lt;/math&gt;.<br /> <br /> See here for a video solution: https://www.youtube.com/watch?v=4e8Hk04Ax_E&amp;t=131s<br /> <br /> ==Solution 2==<br /> Let &lt;math&gt;\angle{BAC}&lt;/math&gt; be &lt;math&gt;x&lt;/math&gt; in degrees. &lt;math&gt;\angle{ADE}=x&lt;/math&gt;.<br /> By Exterior Angle Theorem on triangle &lt;math&gt;AED&lt;/math&gt;, &lt;math&gt;\angle{BED}=2x&lt;/math&gt;.<br /> By Exterior Angle Theorem on triangle &lt;math&gt;ADB&lt;/math&gt;, &lt;math&gt;\angle{BDC}=3x&lt;/math&gt;.<br /> This tells us &lt;math&gt;\angle{BCA}=\angle{ABC}=3x&lt;/math&gt; and &lt;math&gt;3x+3x+x=180&lt;/math&gt;.<br /> Thus &lt;math&gt;x=\frac{180}{7}&lt;/math&gt; and we want &lt;math&gt;\angle{ABC}=3x=\frac{540}{7}&lt;/math&gt; to get an answer of &lt;math&gt;\boxed{547}&lt;/math&gt;.<br /> <br /> <br /> https://artofproblemsolving.com/wiki/index.php/1961_AHSME_Problems/Problem_25<br /> (Almost Mirrored)<br /> <br /> See here for a video solution:<br /> <br /> https://youtu.be/4XkA0DwuqYk<br /> <br /> ==See Also==<br /> <br /> {{AIME box|year=2020|n=I|before=First Problem|num-a=2}}<br /> {{MAA Notice}}</div> Avn https://artofproblemsolving.com/wiki/index.php?title=1991_AJHSME_Problems/Problem_20&diff=85261 1991 AJHSME Problems/Problem 20 2017-04-18T04:02:59Z <p>Avn: /* Solution */</p> <hr /> <div>==Problem==<br /> <br /> In the addition problem, each digit has been replaced by a letter. If different letters represent different digits then &lt;math&gt;C=&lt;/math&gt;<br /> <br /> &lt;asy&gt;<br /> unitsize(18);<br /> draw((-1,0)--(3,0));<br /> draw((-3/4,1/2)--(-1/4,1/2)); draw((-1/2,1/4)--(-1/2,3/4));<br /> label(&quot;$A$&quot;,(0.5,2.1),N); label(&quot;$B$&quot;,(1.5,2.1),N); label(&quot;$C$&quot;,(2.5,2.1),N);<br /> label(&quot;$A$&quot;,(1.5,1.1),N); label(&quot;$B$&quot;,(2.5,1.1),N); label(&quot;$A$&quot;,(2.5,0.1),N);<br /> label(&quot;$3$&quot;,(0.5,-.1),S); label(&quot;$0$&quot;,(1.5,-.1),S); label(&quot;$0$&quot;,(2.5,-.1),S);<br /> &lt;/asy&gt;<br /> <br /> &lt;math&gt;\text{(A)}\ 1 \qquad \text{(B)}\ 3 \qquad \text{(C)}\ 5 \qquad \text{(D)}\ 7 \qquad \text{(E)}\ 9&lt;/math&gt;<br /> <br /> ==Solution==<br /> <br /> From this we have <br /> &lt;cmath&gt;111A+11B+C=300.&lt;/cmath&gt;<br /> Clearly, &lt;math&gt;A&lt;3&lt;/math&gt;. Since &lt;math&gt;B,C\leq 9&lt;/math&gt;, <br /> &lt;cmath&gt;111A &gt; 201 \Rightarrow A\geq 2.&lt;/cmath&gt;<br /> Thus, &lt;math&gt;A=2&lt;/math&gt; and &lt;math&gt;11B+C=78&lt;/math&gt;. From here it becomes clear that &lt;math&gt;B=7&lt;/math&gt; and &lt;math&gt;C=1\rightarrow \boxed{\text{A}}&lt;/math&gt;.<br /> <br /> ==Solution==<br /> <br /> Using logic, &lt;math&gt;a+b+c= 10&lt;/math&gt;, therefore &lt;math&gt;b+a+1&lt;/math&gt;(from the carry over)&lt;math&gt;= 10&lt;/math&gt;.<br /> so b+a=9<br /> A+1=3<br /> <br /> Thus, &lt;math&gt;A=2&lt;/math&gt; and &lt;math&gt;11B+C=78&lt;/math&gt;. From here it becomes clear that &lt;math&gt;B=7&lt;/math&gt; and &lt;math&gt;C=1\rightarrow \boxed{\text{A}}&lt;/math&gt;.<br /> <br /> ==See Also==<br /> <br /> {{AJHSME box|year=1991|num-b=19|num-a=21}}<br /> [[Category:Introductory Algebra Problems]]<br /> {{MAA Notice}}</div> Avn