https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Totoro.selsel&feedformat=atom AoPS Wiki - User contributions [en] 2022-06-29T07:13:20Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2020_AMC_12B_Problems/Problem_17&diff=132138 2020 AMC 12B Problems/Problem 17 2020-08-19T03:42:47Z <p>Totoro.selsel: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> How many polynomials of the form &lt;math&gt;x^5 + ax^4 + bx^3 + cx^2 + dx + 2020&lt;/math&gt;, where &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; are real numbers, have the property that whenever &lt;math&gt;r&lt;/math&gt; is a root, so is &lt;math&gt;\frac{-1+i\sqrt{3}}{2} \cdot r&lt;/math&gt;? (Note that &lt;math&gt;i=\sqrt{-1}&lt;/math&gt;)<br /> <br /> &lt;math&gt;\textbf{(A) } 0 \qquad \textbf{(B) }1 \qquad \textbf{(C) } 2 \qquad \textbf{(D) } 3 \qquad \textbf{(E) } 4&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> Let &lt;math&gt;P(x) = x^5+ax^4+bx^3+cx^2+dx+2020&lt;/math&gt;. We first notice that &lt;math&gt;\frac{-1+i\sqrt{3}}{2} = e^{i\frac{2\pi}{3}}&lt;/math&gt;. That is because of Euler's Formula : &lt;math&gt;e^{ix} = cos(x) + i \cdot sin(x)&lt;/math&gt;. &lt;math&gt;\frac{-1+i\sqrt{3}}{2}&lt;/math&gt; = &lt;math&gt;-\frac{1}{2} + i \cdot \frac {sqrt{3}}{2}&lt;/math&gt; = &lt;math&gt;cos(120) + i \cdot sin(120)&lt;/math&gt; = &lt;math&gt;e^{i \cdot 120(degrees)}&lt;/math&gt; = &lt;math&gt;e^{i \frac{2}{3} \pi (radians)}&lt;/math&gt;. In order &lt;math&gt;r&lt;/math&gt; to be a root of &lt;math&gt;P&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt; must also be a root of P, meaning that 3 of the roots of &lt;math&gt;P&lt;/math&gt; must be &lt;math&gt;r&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt;, &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt;. However, since &lt;math&gt;P&lt;/math&gt; is degree 5, there must be two additional roots. Let one of these roots be &lt;math&gt;w&lt;/math&gt;, if &lt;math&gt;w&lt;/math&gt; is a root, then &lt;math&gt;we^{i\frac{2\pi}{3}}&lt;/math&gt; and &lt;math&gt;we^{i\frac{4\pi}{3}}&lt;/math&gt; must also be roots. However, &lt;math&gt;P&lt;/math&gt; is a fifth degree polynomial, and can therefore only have &lt;math&gt;5&lt;/math&gt; roots. This implies that &lt;math&gt;w&lt;/math&gt; is either &lt;math&gt;r&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt;, or &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt;. Thus we know that the polynomial &lt;math&gt;P&lt;/math&gt; can be written in the form &lt;math&gt;(x-r)^m(x-re^{i\frac{2\pi}{3}})^n(x-re^{i\frac{4\pi}{3}})^p&lt;/math&gt;. Moreover, by Vieta's, we know that there is only one possible value for the magnitude of &lt;math&gt;r&lt;/math&gt; as &lt;math&gt;||r||^5 = 2020&lt;/math&gt;, meaning that the amount of possible polynomials &lt;math&gt;P&lt;/math&gt; is equivalent to the possible sets &lt;math&gt;(m,n,p)&lt;/math&gt;. In order for the coefficients of the polynomial to all be real, &lt;math&gt;n = p&lt;/math&gt; due to &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt; and &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt; being conjugates and since &lt;math&gt;m+n+p = 5&lt;/math&gt;, (as the polynomial is 5th degree) we have two possible solutions for &lt;math&gt;(m, n, p)&lt;/math&gt; which are &lt;math&gt;(1,2,2)&lt;/math&gt; and &lt;math&gt;(3,1,1)&lt;/math&gt; yielding two possible polynomials. The answer is thus &lt;math&gt;\boxed{\textbf{(C) } 2}&lt;/math&gt;.<br /> <br /> ~Murtagh<br /> <br /> ==Solution 2==<br /> <br /> <br /> Let &lt;math&gt;x_1=r&lt;/math&gt;, then &lt;math&gt;x_2=(-1+i\sqrt{3})/2 r&lt;/math&gt;, x_3=〖((-1+i√3)/2)〗^2 r=(-1-i√3)/2 r, x_4=〖((-1+i√3)/2)〗^3 r=r which means x_4 will be back to x_1<br /> Now we have 3 different roots of the polynomial, x_(1 ) 〖,x〗_2, and x_3. next we gonna prove that all 5 roots of the polynomial must be chosen from those 3 roots. Let us assume that there has one root x_4=p which is different from the three roots we already know, then there must be another two roots, x_5=〖((-1+i√3)/2)〗^2 p=(-1-i√3)/2 p and x_6=〖((-1+i√3)/2)〗^3 p=p, different from all known roots. So we got 6 different roots for the polynomial, which is impossible. Therefore the assumption of the different root is wrong.<br /> The polynomial then can be written like f(x)=〖(x-x_1)〗^m 〖(x-x_2)〗^n 〖(x-x_3)〗^q,m,n,q are non-negative integers and m+n+q=5. Since a,b,c and d are real numbers, n must be equal to q. Therefore (m,n,q) can only be (1,2,2) or (3,1,1), so the answer is (C) 2<br /> <br /> ~Yelong_Li<br /> <br /> ==See Also==<br /> <br /> {{AMC12 box|year=2020|ab=B|num-b=16|num-a=18}}<br /> {{MAA Notice}}</div> Totoro.selsel https://artofproblemsolving.com/wiki/index.php?title=2020_AMC_12B_Problems/Problem_17&diff=132137 2020 AMC 12B Problems/Problem 17 2020-08-19T03:37:04Z <p>Totoro.selsel: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> How many polynomials of the form &lt;math&gt;x^5 + ax^4 + bx^3 + cx^2 + dx + 2020&lt;/math&gt;, where &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; are real numbers, have the property that whenever &lt;math&gt;r&lt;/math&gt; is a root, so is &lt;math&gt;\frac{-1+i\sqrt{3}}{2} \cdot r&lt;/math&gt;? (Note that &lt;math&gt;i=\sqrt{-1}&lt;/math&gt;)<br /> <br /> &lt;math&gt;\textbf{(A) } 0 \qquad \textbf{(B) }1 \qquad \textbf{(C) } 2 \qquad \textbf{(D) } 3 \qquad \textbf{(E) } 4&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> Let &lt;math&gt;P(x) = x^5+ax^4+bx^3+cx^2+dx+2020&lt;/math&gt;. We first notice that &lt;math&gt;\frac{-1+i\sqrt{3}}{2} = e^{i\frac{2\pi}{3}}&lt;/math&gt;. That is because of Euler's Formula : &lt;math&gt;e^{ix} = cos(x) + i \cdot sin(x)&lt;/math&gt;. &lt;math&gt;\frac{-1+i\sqrt{3}}{2}&lt;/math&gt; = &lt;math&gt;-\frac{1}{2} + i \cdot \frac {sqrt{3}}{2}&lt;/math&gt; = &lt;math&gt;cos(120) + i \cdot sin(120)&lt;/math&gt; = &lt;math&gt;e^{i \cdot 120(degrees)}&lt;/math&gt; = &lt;math&gt;e^{i \frac{2}{3} \pi (radians)}&lt;/math&gt;. In order &lt;math&gt;r&lt;/math&gt; to be a root of &lt;math&gt;P&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt; must also be a root of P, meaning that 3 of the roots of &lt;math&gt;P&lt;/math&gt; must be &lt;math&gt;r&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt;, &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt;. However, since &lt;math&gt;P&lt;/math&gt; is degree 5, there must be two additional roots. Let one of these roots be &lt;math&gt;w&lt;/math&gt;, if &lt;math&gt;w&lt;/math&gt; is a root, then &lt;math&gt;we^{i\frac{2\pi}{3}}&lt;/math&gt; and &lt;math&gt;we^{i\frac{4\pi}{3}}&lt;/math&gt; must also be roots. However, &lt;math&gt;P&lt;/math&gt; is a fifth degree polynomial, and can therefore only have &lt;math&gt;5&lt;/math&gt; roots. This implies that &lt;math&gt;w&lt;/math&gt; is either &lt;math&gt;r&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt;, or &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt;. Thus we know that the polynomial &lt;math&gt;P&lt;/math&gt; can be written in the form &lt;math&gt;(x-r)^m(x-re^{i\frac{2\pi}{3}})^n(x-re^{i\frac{4\pi}{3}})^p&lt;/math&gt;. Moreover, by Vieta's, we know that there is only one possible value for the magnitude of &lt;math&gt;r&lt;/math&gt; as &lt;math&gt;||r||^5 = 2020&lt;/math&gt;, meaning that the amount of possible polynomials &lt;math&gt;P&lt;/math&gt; is equivalent to the possible sets &lt;math&gt;(m,n,p)&lt;/math&gt;. In order for the coefficients of the polynomial to all be real, &lt;math&gt;n = p&lt;/math&gt; due to &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt; and &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt; being conjugates and since &lt;math&gt;m+n+p = 5&lt;/math&gt;, (as the polynomial is 5th degree) we have two possible solutions for &lt;math&gt;(m, n, p)&lt;/math&gt; which are &lt;math&gt;(1,2,2)&lt;/math&gt; and &lt;math&gt;(3,1,1)&lt;/math&gt; yielding two possible polynomials. The answer is thus &lt;math&gt;\boxed{\textbf{(C) } 2}&lt;/math&gt;.<br /> <br /> ~Murtagh (edited by totoro.selsel)<br /> <br /> ==Solution 2==<br /> <br /> <br /> Let &lt;math&gt;x_1=r&lt;/math&gt;, then &lt;math&gt;x_2=(-1+i\sqrt{3})/2 r&lt;/math&gt;, x_3=〖((-1+i√3)/2)〗^2 r=(-1-i√3)/2 r, x_4=〖((-1+i√3)/2)〗^3 r=r which means x_4 will be back to x_1<br /> Now we have 3 different roots of the polynomial, x_(1 ) 〖,x〗_2, and x_3. next we gonna prove that all 5 roots of the polynomial must be chosen from those 3 roots. Let us assume that there has one root x_4=p which is different from the three roots we already know, then there must be another two roots, x_5=〖((-1+i√3)/2)〗^2 p=(-1-i√3)/2 p and x_6=〖((-1+i√3)/2)〗^3 p=p, different from all known roots. So we got 6 different roots for the polynomial, which is impossible. Therefore the assumption of the different root is wrong.<br /> The polynomial then can be written like f(x)=〖(x-x_1)〗^m 〖(x-x_2)〗^n 〖(x-x_3)〗^q,m,n,q are non-negative integers and m+n+q=5. Since a,b,c and d are real numbers, n must be equal to q. Therefore (m,n,q) can only be (1,2,2) or (3,1,1), so the answer is (C) 2<br /> <br /> ~Yelong_Li<br /> <br /> ==See Also==<br /> <br /> {{AMC12 box|year=2020|ab=B|num-b=16|num-a=18}}<br /> {{MAA Notice}}</div> Totoro.selsel https://artofproblemsolving.com/wiki/index.php?title=2020_AMC_12B_Problems/Problem_17&diff=132136 2020 AMC 12B Problems/Problem 17 2020-08-19T03:36:35Z <p>Totoro.selsel: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> How many polynomials of the form &lt;math&gt;x^5 + ax^4 + bx^3 + cx^2 + dx + 2020&lt;/math&gt;, where &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; are real numbers, have the property that whenever &lt;math&gt;r&lt;/math&gt; is a root, so is &lt;math&gt;\frac{-1+i\sqrt{3}}{2} \cdot r&lt;/math&gt;? (Note that &lt;math&gt;i=\sqrt{-1}&lt;/math&gt;)<br /> <br /> &lt;math&gt;\textbf{(A) } 0 \qquad \textbf{(B) }1 \qquad \textbf{(C) } 2 \qquad \textbf{(D) } 3 \qquad \textbf{(E) } 4&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> Let &lt;math&gt;P(x) = x^5+ax^4+bx^3+cx^2+dx+2020&lt;/math&gt;. We first notice that &lt;math&gt;\frac{-1+i\sqrt{3}}{2} = e^{i\frac{2\pi}{3}}&lt;/math&gt;. That is because of Euler's Formula : &lt;math&gt;e^{ix} = cos(x) + i \cdot sin(x)&lt;/math&gt;. &lt;math&gt;\frac{-1+i\sqrt{3}}{2}&lt;/math&gt; = &lt;math&gt;-\frac{1}{2} + i \cdot \frac {sqrt(3)}{2}&lt;/math&gt; = &lt;math&gt;cos(120) + i \cdot sin(120)&lt;/math&gt; = &lt;math&gt;e^{i \cdot 120(degrees)}&lt;/math&gt; = &lt;math&gt;e^{i \frac{2}{3} \pi (radians)}&lt;/math&gt;. In order &lt;math&gt;r&lt;/math&gt; to be a root of &lt;math&gt;P&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt; must also be a root of P, meaning that 3 of the roots of &lt;math&gt;P&lt;/math&gt; must be &lt;math&gt;r&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt;, &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt;. However, since &lt;math&gt;P&lt;/math&gt; is degree 5, there must be two additional roots. Let one of these roots be &lt;math&gt;w&lt;/math&gt;, if &lt;math&gt;w&lt;/math&gt; is a root, then &lt;math&gt;we^{i\frac{2\pi}{3}}&lt;/math&gt; and &lt;math&gt;we^{i\frac{4\pi}{3}}&lt;/math&gt; must also be roots. However, &lt;math&gt;P&lt;/math&gt; is a fifth degree polynomial, and can therefore only have &lt;math&gt;5&lt;/math&gt; roots. This implies that &lt;math&gt;w&lt;/math&gt; is either &lt;math&gt;r&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt;, or &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt;. Thus we know that the polynomial &lt;math&gt;P&lt;/math&gt; can be written in the form &lt;math&gt;(x-r)^m(x-re^{i\frac{2\pi}{3}})^n(x-re^{i\frac{4\pi}{3}})^p&lt;/math&gt;. Moreover, by Vieta's, we know that there is only one possible value for the magnitude of &lt;math&gt;r&lt;/math&gt; as &lt;math&gt;||r||^5 = 2020&lt;/math&gt;, meaning that the amount of possible polynomials &lt;math&gt;P&lt;/math&gt; is equivalent to the possible sets &lt;math&gt;(m,n,p)&lt;/math&gt;. In order for the coefficients of the polynomial to all be real, &lt;math&gt;n = p&lt;/math&gt; due to &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt; and &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt; being conjugates and since &lt;math&gt;m+n+p = 5&lt;/math&gt;, (as the polynomial is 5th degree) we have two possible solutions for &lt;math&gt;(m, n, p)&lt;/math&gt; which are &lt;math&gt;(1,2,2)&lt;/math&gt; and &lt;math&gt;(3,1,1)&lt;/math&gt; yielding two possible polynomials. The answer is thus &lt;math&gt;\boxed{\textbf{(C) } 2}&lt;/math&gt;.<br /> <br /> ~Murtagh (edited by totoro.selsel)<br /> <br /> ==Solution 2==<br /> <br /> <br /> Let &lt;math&gt;x_1=r&lt;/math&gt;, then &lt;math&gt;x_2=(-1+i\sqrt{3})/2 r&lt;/math&gt;, x_3=〖((-1+i√3)/2)〗^2 r=(-1-i√3)/2 r, x_4=〖((-1+i√3)/2)〗^3 r=r which means x_4 will be back to x_1<br /> Now we have 3 different roots of the polynomial, x_(1 ) 〖,x〗_2, and x_3. next we gonna prove that all 5 roots of the polynomial must be chosen from those 3 roots. Let us assume that there has one root x_4=p which is different from the three roots we already know, then there must be another two roots, x_5=〖((-1+i√3)/2)〗^2 p=(-1-i√3)/2 p and x_6=〖((-1+i√3)/2)〗^3 p=p, different from all known roots. So we got 6 different roots for the polynomial, which is impossible. Therefore the assumption of the different root is wrong.<br /> The polynomial then can be written like f(x)=〖(x-x_1)〗^m 〖(x-x_2)〗^n 〖(x-x_3)〗^q,m,n,q are non-negative integers and m+n+q=5. Since a,b,c and d are real numbers, n must be equal to q. Therefore (m,n,q) can only be (1,2,2) or (3,1,1), so the answer is (C) 2<br /> <br /> ~Yelong_Li<br /> <br /> ==See Also==<br /> <br /> {{AMC12 box|year=2020|ab=B|num-b=16|num-a=18}}<br /> {{MAA Notice}}</div> Totoro.selsel https://artofproblemsolving.com/wiki/index.php?title=2020_AMC_12B_Problems/Problem_17&diff=132133 2020 AMC 12B Problems/Problem 17 2020-08-19T03:36:19Z <p>Totoro.selsel: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> How many polynomials of the form &lt;math&gt;x^5 + ax^4 + bx^3 + cx^2 + dx + 2020&lt;/math&gt;, where &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; are real numbers, have the property that whenever &lt;math&gt;r&lt;/math&gt; is a root, so is &lt;math&gt;\frac{-1+i\sqrt{3}}{2} \cdot r&lt;/math&gt;? (Note that &lt;math&gt;i=\sqrt{-1}&lt;/math&gt;)<br /> <br /> &lt;math&gt;\textbf{(A) } 0 \qquad \textbf{(B) }1 \qquad \textbf{(C) } 2 \qquad \textbf{(D) } 3 \qquad \textbf{(E) } 4&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> Let &lt;math&gt;P(x) = x^5+ax^4+bx^3+cx^2+dx+2020&lt;/math&gt;. We first notice that &lt;math&gt;\frac{-1+i\sqrt{3}}{2} = e^{i\frac{2\pi}{3}}&lt;/math&gt;. That is because of Euler's Formula : &lt;math&gt;e^{ix} = cos(x) + i \cdot sin(x)&lt;/math&gt;. &lt;math&gt;\frac{-1+i\sqrt{3}}{2}&lt;/math&gt; = &lt;math&gt;-\frac{1}{2} + i \cdot \frac {sqrt(3)}{2}&lt;/math&gt; = &lt;math&gt;cos(120) + i \cdot sin(120)&lt;/math&gt; = &lt;math&gt;e^{i \cdot 120(degrees)}&lt;/math&gt; = &lt;math&gt;e^{i \frac{2}{3} \pi (radians)}&lt;/math&gt; .In order &lt;math&gt;r&lt;/math&gt; to be a root of &lt;math&gt;P&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt; must also be a root of P, meaning that 3 of the roots of &lt;math&gt;P&lt;/math&gt; must be &lt;math&gt;r&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt;, &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt;. However, since &lt;math&gt;P&lt;/math&gt; is degree 5, there must be two additional roots. Let one of these roots be &lt;math&gt;w&lt;/math&gt;, if &lt;math&gt;w&lt;/math&gt; is a root, then &lt;math&gt;we^{i\frac{2\pi}{3}}&lt;/math&gt; and &lt;math&gt;we^{i\frac{4\pi}{3}}&lt;/math&gt; must also be roots. However, &lt;math&gt;P&lt;/math&gt; is a fifth degree polynomial, and can therefore only have &lt;math&gt;5&lt;/math&gt; roots. This implies that &lt;math&gt;w&lt;/math&gt; is either &lt;math&gt;r&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt;, or &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt;. Thus we know that the polynomial &lt;math&gt;P&lt;/math&gt; can be written in the form &lt;math&gt;(x-r)^m(x-re^{i\frac{2\pi}{3}})^n(x-re^{i\frac{4\pi}{3}})^p&lt;/math&gt;. Moreover, by Vieta's, we know that there is only one possible value for the magnitude of &lt;math&gt;r&lt;/math&gt; as &lt;math&gt;||r||^5 = 2020&lt;/math&gt;, meaning that the amount of possible polynomials &lt;math&gt;P&lt;/math&gt; is equivalent to the possible sets &lt;math&gt;(m,n,p)&lt;/math&gt;. In order for the coefficients of the polynomial to all be real, &lt;math&gt;n = p&lt;/math&gt; due to &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt; and &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt; being conjugates and since &lt;math&gt;m+n+p = 5&lt;/math&gt;, (as the polynomial is 5th degree) we have two possible solutions for &lt;math&gt;(m, n, p)&lt;/math&gt; which are &lt;math&gt;(1,2,2)&lt;/math&gt; and &lt;math&gt;(3,1,1)&lt;/math&gt; yielding two possible polynomials. The answer is thus &lt;math&gt;\boxed{\textbf{(C) } 2}&lt;/math&gt;.<br /> <br /> ~Murtagh (edited by totoro.selsel)<br /> <br /> ==Solution 2==<br /> <br /> <br /> Let &lt;math&gt;x_1=r&lt;/math&gt;, then &lt;math&gt;x_2=(-1+i\sqrt{3})/2 r&lt;/math&gt;, x_3=〖((-1+i√3)/2)〗^2 r=(-1-i√3)/2 r, x_4=〖((-1+i√3)/2)〗^3 r=r which means x_4 will be back to x_1<br /> Now we have 3 different roots of the polynomial, x_(1 ) 〖,x〗_2, and x_3. next we gonna prove that all 5 roots of the polynomial must be chosen from those 3 roots. Let us assume that there has one root x_4=p which is different from the three roots we already know, then there must be another two roots, x_5=〖((-1+i√3)/2)〗^2 p=(-1-i√3)/2 p and x_6=〖((-1+i√3)/2)〗^3 p=p, different from all known roots. So we got 6 different roots for the polynomial, which is impossible. Therefore the assumption of the different root is wrong.<br /> The polynomial then can be written like f(x)=〖(x-x_1)〗^m 〖(x-x_2)〗^n 〖(x-x_3)〗^q,m,n,q are non-negative integers and m+n+q=5. Since a,b,c and d are real numbers, n must be equal to q. Therefore (m,n,q) can only be (1,2,2) or (3,1,1), so the answer is (C) 2<br /> <br /> ~Yelong_Li<br /> <br /> ==See Also==<br /> <br /> {{AMC12 box|year=2020|ab=B|num-b=16|num-a=18}}<br /> {{MAA Notice}}</div> Totoro.selsel https://artofproblemsolving.com/wiki/index.php?title=2020_AMC_12B_Problems/Problem_17&diff=132131 2020 AMC 12B Problems/Problem 17 2020-08-19T03:35:59Z <p>Totoro.selsel: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> How many polynomials of the form &lt;math&gt;x^5 + ax^4 + bx^3 + cx^2 + dx + 2020&lt;/math&gt;, where &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; are real numbers, have the property that whenever &lt;math&gt;r&lt;/math&gt; is a root, so is &lt;math&gt;\frac{-1+i\sqrt{3}}{2} \cdot r&lt;/math&gt;? (Note that &lt;math&gt;i=\sqrt{-1}&lt;/math&gt;)<br /> <br /> &lt;math&gt;\textbf{(A) } 0 \qquad \textbf{(B) }1 \qquad \textbf{(C) } 2 \qquad \textbf{(D) } 3 \qquad \textbf{(E) } 4&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> Let &lt;math&gt;P(x) = x^5+ax^4+bx^3+cx^2+dx+2020&lt;/math&gt;. We first notice that &lt;math&gt;\frac{-1+i\sqrt{3}}{2} = e^{i\frac{2\pi}{3}}&lt;/math&gt;. That is because of Euler's Formula : &lt;math&gt;e^{ix} = cos(x) + i \cdot sin(x)&lt;/math&gt;. &lt;math&gt;\frac{-1+i\sqrt{3}}{2}&lt;/math&gt; = &lt;math&gt;-\frac{1}{2} + i \cdot \frac {sqrt(3)}{2}&lt;/math&gt; = &lt;math&gt;cos(120) + i \cdot sin(120)&lt;/math&gt; = &lt;math&gt;e^{i \cdot 120(degrees)&lt;/math&gt; = &lt;math&gt;e^{i \frac{2}{3} \pi (radians)}&lt;/math&gt; .In order &lt;math&gt;r&lt;/math&gt; to be a root of &lt;math&gt;P&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt; must also be a root of P, meaning that 3 of the roots of &lt;math&gt;P&lt;/math&gt; must be &lt;math&gt;r&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt;, &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt;. However, since &lt;math&gt;P&lt;/math&gt; is degree 5, there must be two additional roots. Let one of these roots be &lt;math&gt;w&lt;/math&gt;, if &lt;math&gt;w&lt;/math&gt; is a root, then &lt;math&gt;we^{i\frac{2\pi}{3}}&lt;/math&gt; and &lt;math&gt;we^{i\frac{4\pi}{3}}&lt;/math&gt; must also be roots. However, &lt;math&gt;P&lt;/math&gt; is a fifth degree polynomial, and can therefore only have &lt;math&gt;5&lt;/math&gt; roots. This implies that &lt;math&gt;w&lt;/math&gt; is either &lt;math&gt;r&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt;, or &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt;. Thus we know that the polynomial &lt;math&gt;P&lt;/math&gt; can be written in the form &lt;math&gt;(x-r)^m(x-re^{i\frac{2\pi}{3}})^n(x-re^{i\frac{4\pi}{3}})^p&lt;/math&gt;. Moreover, by Vieta's, we know that there is only one possible value for the magnitude of &lt;math&gt;r&lt;/math&gt; as &lt;math&gt;||r||^5 = 2020&lt;/math&gt;, meaning that the amount of possible polynomials &lt;math&gt;P&lt;/math&gt; is equivalent to the possible sets &lt;math&gt;(m,n,p)&lt;/math&gt;. In order for the coefficients of the polynomial to all be real, &lt;math&gt;n = p&lt;/math&gt; due to &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt; and &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt; being conjugates and since &lt;math&gt;m+n+p = 5&lt;/math&gt;, (as the polynomial is 5th degree) we have two possible solutions for &lt;math&gt;(m, n, p)&lt;/math&gt; which are &lt;math&gt;(1,2,2)&lt;/math&gt; and &lt;math&gt;(3,1,1)&lt;/math&gt; yielding two possible polynomials. The answer is thus &lt;math&gt;\boxed{\textbf{(C) } 2}&lt;/math&gt;.<br /> <br /> ~Murtagh (edited by totoro.selsel)<br /> <br /> ==Solution 2==<br /> <br /> <br /> Let &lt;math&gt;x_1=r&lt;/math&gt;, then &lt;math&gt;x_2=(-1+i\sqrt{3})/2 r&lt;/math&gt;, x_3=〖((-1+i√3)/2)〗^2 r=(-1-i√3)/2 r, x_4=〖((-1+i√3)/2)〗^3 r=r which means x_4 will be back to x_1<br /> Now we have 3 different roots of the polynomial, x_(1 ) 〖,x〗_2, and x_3. next we gonna prove that all 5 roots of the polynomial must be chosen from those 3 roots. Let us assume that there has one root x_4=p which is different from the three roots we already know, then there must be another two roots, x_5=〖((-1+i√3)/2)〗^2 p=(-1-i√3)/2 p and x_6=〖((-1+i√3)/2)〗^3 p=p, different from all known roots. So we got 6 different roots for the polynomial, which is impossible. Therefore the assumption of the different root is wrong.<br /> The polynomial then can be written like f(x)=〖(x-x_1)〗^m 〖(x-x_2)〗^n 〖(x-x_3)〗^q,m,n,q are non-negative integers and m+n+q=5. Since a,b,c and d are real numbers, n must be equal to q. Therefore (m,n,q) can only be (1,2,2) or (3,1,1), so the answer is (C) 2<br /> <br /> ~Yelong_Li<br /> <br /> ==See Also==<br /> <br /> {{AMC12 box|year=2020|ab=B|num-b=16|num-a=18}}<br /> {{MAA Notice}}</div> Totoro.selsel https://artofproblemsolving.com/wiki/index.php?title=2020_AMC_12B_Problems/Problem_17&diff=132129 2020 AMC 12B Problems/Problem 17 2020-08-19T03:35:35Z <p>Totoro.selsel: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> How many polynomials of the form &lt;math&gt;x^5 + ax^4 + bx^3 + cx^2 + dx + 2020&lt;/math&gt;, where &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; are real numbers, have the property that whenever &lt;math&gt;r&lt;/math&gt; is a root, so is &lt;math&gt;\frac{-1+i\sqrt{3}}{2} \cdot r&lt;/math&gt;? (Note that &lt;math&gt;i=\sqrt{-1}&lt;/math&gt;)<br /> <br /> &lt;math&gt;\textbf{(A) } 0 \qquad \textbf{(B) }1 \qquad \textbf{(C) } 2 \qquad \textbf{(D) } 3 \qquad \textbf{(E) } 4&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> Let &lt;math&gt;P(x) = x^5+ax^4+bx^3+cx^2+dx+2020&lt;/math&gt;. We first notice that &lt;math&gt;\frac{-1+i\sqrt{3}}{2} = e^{i\frac{2\pi}{3}}&lt;/math&gt;. That is because of Euler's Formula : &lt;math&gt;e^{ix} = cos(x) + i \cdot sin(x)&lt;/math&gt;. &lt;math&gt;\frac{-1+i\sqrt{3}}{2}&lt;/math&gt; = &lt;math&gt;-\frac{1}{2} + i \cdot \frac {sqrt(3)}{2}&lt;/math&gt; = &lt;math&gt;cos(120) + i \cdot sin(120)&lt;/math&gt; = &lt;math&gt;e^{i \cdot 120(degrees)&lt;/math&gt; = &lt;math&gt;e^{i \frac{2}{3} \pi (radians)&lt;/math&gt; .In order &lt;math&gt;r&lt;/math&gt; to be a root of &lt;math&gt;P&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt; must also be a root of P, meaning that 3 of the roots of &lt;math&gt;P&lt;/math&gt; must be &lt;math&gt;r&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt;, &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt;. However, since &lt;math&gt;P&lt;/math&gt; is degree 5, there must be two additional roots. Let one of these roots be &lt;math&gt;w&lt;/math&gt;, if &lt;math&gt;w&lt;/math&gt; is a root, then &lt;math&gt;we^{i\frac{2\pi}{3}}&lt;/math&gt; and &lt;math&gt;we^{i\frac{4\pi}{3}}&lt;/math&gt; must also be roots. However, &lt;math&gt;P&lt;/math&gt; is a fifth degree polynomial, and can therefore only have &lt;math&gt;5&lt;/math&gt; roots. This implies that &lt;math&gt;w&lt;/math&gt; is either &lt;math&gt;r&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt;, or &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt;. Thus we know that the polynomial &lt;math&gt;P&lt;/math&gt; can be written in the form &lt;math&gt;(x-r)^m(x-re^{i\frac{2\pi}{3}})^n(x-re^{i\frac{4\pi}{3}})^p&lt;/math&gt;. Moreover, by Vieta's, we know that there is only one possible value for the magnitude of &lt;math&gt;r&lt;/math&gt; as &lt;math&gt;||r||^5 = 2020&lt;/math&gt;, meaning that the amount of possible polynomials &lt;math&gt;P&lt;/math&gt; is equivalent to the possible sets &lt;math&gt;(m,n,p)&lt;/math&gt;. In order for the coefficients of the polynomial to all be real, &lt;math&gt;n = p&lt;/math&gt; due to &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt; and &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt; being conjugates and since &lt;math&gt;m+n+p = 5&lt;/math&gt;, (as the polynomial is 5th degree) we have two possible solutions for &lt;math&gt;(m, n, p)&lt;/math&gt; which are &lt;math&gt;(1,2,2)&lt;/math&gt; and &lt;math&gt;(3,1,1)&lt;/math&gt; yielding two possible polynomials. The answer is thus &lt;math&gt;\boxed{\textbf{(C) } 2}&lt;/math&gt;.<br /> <br /> ~Murtagh (edited by totoro.selsel)<br /> <br /> ==Solution 2==<br /> <br /> <br /> Let &lt;math&gt;x_1=r&lt;/math&gt;, then &lt;math&gt;x_2=(-1+i\sqrt{3})/2 r&lt;/math&gt;, x_3=〖((-1+i√3)/2)〗^2 r=(-1-i√3)/2 r, x_4=〖((-1+i√3)/2)〗^3 r=r which means x_4 will be back to x_1<br /> Now we have 3 different roots of the polynomial, x_(1 ) 〖,x〗_2, and x_3. next we gonna prove that all 5 roots of the polynomial must be chosen from those 3 roots. Let us assume that there has one root x_4=p which is different from the three roots we already know, then there must be another two roots, x_5=〖((-1+i√3)/2)〗^2 p=(-1-i√3)/2 p and x_6=〖((-1+i√3)/2)〗^3 p=p, different from all known roots. So we got 6 different roots for the polynomial, which is impossible. Therefore the assumption of the different root is wrong.<br /> The polynomial then can be written like f(x)=〖(x-x_1)〗^m 〖(x-x_2)〗^n 〖(x-x_3)〗^q,m,n,q are non-negative integers and m+n+q=5. Since a,b,c and d are real numbers, n must be equal to q. Therefore (m,n,q) can only be (1,2,2) or (3,1,1), so the answer is (C) 2<br /> <br /> ~Yelong_Li<br /> <br /> ==See Also==<br /> <br /> {{AMC12 box|year=2020|ab=B|num-b=16|num-a=18}}<br /> {{MAA Notice}}</div> Totoro.selsel https://artofproblemsolving.com/wiki/index.php?title=2020_AMC_12B_Problems/Problem_17&diff=132128 2020 AMC 12B Problems/Problem 17 2020-08-19T03:34:51Z <p>Totoro.selsel: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> How many polynomials of the form &lt;math&gt;x^5 + ax^4 + bx^3 + cx^2 + dx + 2020&lt;/math&gt;, where &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; are real numbers, have the property that whenever &lt;math&gt;r&lt;/math&gt; is a root, so is &lt;math&gt;\frac{-1+i\sqrt{3}}{2} \cdot r&lt;/math&gt;? (Note that &lt;math&gt;i=\sqrt{-1}&lt;/math&gt;)<br /> <br /> &lt;math&gt;\textbf{(A) } 0 \qquad \textbf{(B) }1 \qquad \textbf{(C) } 2 \qquad \textbf{(D) } 3 \qquad \textbf{(E) } 4&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> Let &lt;math&gt;P(x) = x^5+ax^4+bx^3+cx^2+dx+2020&lt;/math&gt;. We first notice that &lt;math&gt;\frac{-1+i\sqrt{3}}{2} = e^{i\frac{2\pi}{3}}&lt;/math&gt;. That is because of Euler's Formula : &lt;math&gt;e^{ix} = cos(x) + i \cdot sin(x)&lt;/math&gt;. &lt;math&gt;\frac{-1+i\sqrt{3}}{2} = - \frac{1}{2} + i \cdot \frac {sqrt(3)}{2} = cos(120) + i \cdot sin(120) = e^{i \cdot 120(degrees) = e^{i \frac{2}{3} \pi (radians)&lt;/math&gt; .In order &lt;math&gt;r&lt;/math&gt; to be a root of &lt;math&gt;P&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt; must also be a root of P, meaning that 3 of the roots of &lt;math&gt;P&lt;/math&gt; must be &lt;math&gt;r&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt;, &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt;. However, since &lt;math&gt;P&lt;/math&gt; is degree 5, there must be two additional roots. Let one of these roots be &lt;math&gt;w&lt;/math&gt;, if &lt;math&gt;w&lt;/math&gt; is a root, then &lt;math&gt;we^{i\frac{2\pi}{3}}&lt;/math&gt; and &lt;math&gt;we^{i\frac{4\pi}{3}}&lt;/math&gt; must also be roots. However, &lt;math&gt;P&lt;/math&gt; is a fifth degree polynomial, and can therefore only have &lt;math&gt;5&lt;/math&gt; roots. This implies that &lt;math&gt;w&lt;/math&gt; is either &lt;math&gt;r&lt;/math&gt;, &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt;, or &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt;. Thus we know that the polynomial &lt;math&gt;P&lt;/math&gt; can be written in the form &lt;math&gt;(x-r)^m(x-re^{i\frac{2\pi}{3}})^n(x-re^{i\frac{4\pi}{3}})^p&lt;/math&gt;. Moreover, by Vieta's, we know that there is only one possible value for the magnitude of &lt;math&gt;r&lt;/math&gt; as &lt;math&gt;||r||^5 = 2020&lt;/math&gt;, meaning that the amount of possible polynomials &lt;math&gt;P&lt;/math&gt; is equivalent to the possible sets &lt;math&gt;(m,n,p)&lt;/math&gt;. In order for the coefficients of the polynomial to all be real, &lt;math&gt;n = p&lt;/math&gt; due to &lt;math&gt;re^{i\frac{2\pi}{3}}&lt;/math&gt; and &lt;math&gt;re^{i\frac{4\pi}{3}}&lt;/math&gt; being conjugates and since &lt;math&gt;m+n+p = 5&lt;/math&gt;, (as the polynomial is 5th degree) we have two possible solutions for &lt;math&gt;(m, n, p)&lt;/math&gt; which are &lt;math&gt;(1,2,2)&lt;/math&gt; and &lt;math&gt;(3,1,1)&lt;/math&gt; yielding two possible polynomials. The answer is thus &lt;math&gt;\boxed{\textbf{(C) } 2}&lt;/math&gt;.<br /> <br /> ~Murtagh (edited by totoro.selsel)<br /> <br /> ==Solution 2==<br /> <br /> <br /> Let &lt;math&gt;x_1=r&lt;/math&gt;, then &lt;math&gt;x_2=(-1+i\sqrt{3})/2 r&lt;/math&gt;, x_3=〖((-1+i√3)/2)〗^2 r=(-1-i√3)/2 r, x_4=〖((-1+i√3)/2)〗^3 r=r which means x_4 will be back to x_1<br /> Now we have 3 different roots of the polynomial, x_(1 ) 〖,x〗_2, and x_3. next we gonna prove that all 5 roots of the polynomial must be chosen from those 3 roots. Let us assume that there has one root x_4=p which is different from the three roots we already know, then there must be another two roots, x_5=〖((-1+i√3)/2)〗^2 p=(-1-i√3)/2 p and x_6=〖((-1+i√3)/2)〗^3 p=p, different from all known roots. So we got 6 different roots for the polynomial, which is impossible. Therefore the assumption of the different root is wrong.<br /> The polynomial then can be written like f(x)=〖(x-x_1)〗^m 〖(x-x_2)〗^n 〖(x-x_3)〗^q,m,n,q are non-negative integers and m+n+q=5. Since a,b,c and d are real numbers, n must be equal to q. Therefore (m,n,q) can only be (1,2,2) or (3,1,1), so the answer is (C) 2<br /> <br /> ~Yelong_Li<br /> <br /> ==See Also==<br /> <br /> {{AMC12 box|year=2020|ab=B|num-b=16|num-a=18}}<br /> {{MAA Notice}}</div> Totoro.selsel https://artofproblemsolving.com/wiki/index.php?title=2017_AMC_10A_Problems/Problem_15&diff=115575 2017 AMC 10A Problems/Problem 15 2020-01-26T04:28:11Z <p>Totoro.selsel: /* Problem */</p> <hr /> <div>==Problem==<br /> Chloe chooses a real number uniformly at random from the interval &lt;math&gt;[0, 2017]&lt;/math&gt;. Independently, Laurent chooses a real number uniformly at random from the interval &lt;math&gt;[0, 4034]&lt;/math&gt;. What is the probability that Laurent's number is greater than Chloe's number? (Assume they cannot be equal)<br /> &lt;math&gt; \mathrm{\textbf{(A)} \ }\frac{1}{2}\qquad \mathrm{\textbf{(B)} \ } \frac{2}{3}\qquad \mathrm{\textbf{(C)} \ } \frac{3}{4}\qquad \mathrm{\textbf{(D)} \ } \frac{5}{6}\qquad \mathrm{\textbf{(E)} \ }\frac{7}{8}&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> Denote &quot;winning&quot; to mean &quot;picking a greater number&quot;.<br /> There is a &lt;math&gt;\frac{1}{2}&lt;/math&gt; chance that Laurent chooses a number in the interval &lt;math&gt;[2017, 4034]&lt;/math&gt;. In this case, Chloé cannot possibly win, since the maximum number she can pick is &lt;math&gt;2017&lt;/math&gt;. Otherwise, if Laurent picks a number in the interval &lt;math&gt;[0, 2017]&lt;/math&gt;, with probability &lt;math&gt;\frac{1}{2}&lt;/math&gt;, then the two people are symmetric, and each has a &lt;math&gt;\frac{1}{2}&lt;/math&gt; chance of winning. Then, the total probability is &lt;math&gt;\frac{1}{2}*1 + \frac{1}{2}*\frac{1}{2} = \boxed{\textbf{(C)}\ \frac{3}{4}}&lt;/math&gt;<br /> <br /> ==Solution 2==<br /> We can use geometric probability to solve this.<br /> Suppose a point &lt;math&gt;(x,y)&lt;/math&gt; lies in the &lt;math&gt;xy&lt;/math&gt;-plane. Let &lt;math&gt;x&lt;/math&gt; be Chloe's number and &lt;math&gt;y&lt;/math&gt; be Laurent's number. Then obviously we want &lt;math&gt;y&gt;x&lt;/math&gt;, which basically gives us a region above a line. We know that Chloe's number is in the interval &lt;math&gt;[0,2017]&lt;/math&gt; and Laurent's number is in the interval &lt;math&gt;[0,4034]&lt;/math&gt;, so we can create a rectangle in the plane, whose length is &lt;math&gt;2017&lt;/math&gt; and whose width is &lt;math&gt;4034&lt;/math&gt;. Drawing it out, we see that it is easier to find the probability that Chloe's number is greater than Laurent's number and subtract this probability from &lt;math&gt;1&lt;/math&gt;. The probability that Chloe's number is larger than Laurent's number is simply the area of the region under the line &lt;math&gt;y&gt;x&lt;/math&gt;, which is &lt;math&gt;\frac{2017 \cdot 2017}{2}&lt;/math&gt;. Instead of bashing this out we know that the rectangle has area &lt;math&gt;2017 \cdot 4034&lt;/math&gt;. So the probability that Laurent has a smaller number is &lt;math&gt;\frac{2017 \cdot 2017}{2 \cdot 2017 \cdot 4034}&lt;/math&gt;. Simplifying the expression yields &lt;math&gt;\frac{1}{4}&lt;/math&gt; and so &lt;math&gt;1-\frac{1}{4}= \boxed{\textbf{(C)}\ \frac{3}{4}}&lt;/math&gt;.<br /> <br /> ==Solution 3==<br /> Scale down by &lt;math&gt;2017&lt;/math&gt; to get that Chloe picks from &lt;math&gt;[0,1]&lt;/math&gt; and Laurent picks from &lt;math&gt;[0,2]&lt;/math&gt;. There are an infinite number of cases for the number that Chloe picks, but they are all centered around the average of &lt;math&gt;0.5&lt;/math&gt;. Therefore, Laurent has a range of &lt;math&gt;0.5&lt;/math&gt; to &lt;math&gt;2&lt;/math&gt; to pick from, on average, which is a length of &lt;math&gt;2-0.5=1.5&lt;/math&gt; out of a total length of &lt;math&gt;2-0=2&lt;/math&gt;. Therefore, the probability is &lt;math&gt;1.5/2=15/20=\boxed{\frac{3}{4} \space \text{(C)}}&lt;/math&gt;<br /> ==Video Solution==<br /> A video solution for this can be found here: https://www.youtube.com/watch?v=PQFNwW1XFaQ<br /> <br /> ==Video Solution 2==<br /> https://youtu.be/s4vnGlwwHHw<br /> <br /> ==See Also==<br /> {{AMC10 box|year=2017|ab=A|num-b=14|num-a=16}}<br /> {{MAA Notice}}<br /> <br /> [[Category:Introductory Probability Problems]]</div> Totoro.selsel https://artofproblemsolving.com/wiki/index.php?title=2017_AMC_10A_Problems/Problem_15&diff=115574 2017 AMC 10A Problems/Problem 15 2020-01-26T04:27:04Z <p>Totoro.selsel: /* Problem */</p> <hr /> <div>==Problem==<br /> Chloe chooses a real number uniformly at random from the interval &lt;math&gt;[0, 2017]&lt;/math&gt;. Independently, Laurent chooses a real number uniformly at random from the interval &lt;math&gt;[0, 4034]&lt;/math&gt;. What is the probability that Laurent's number is greater than Chloe's number? (Assume they cannot be equal)<br /> e<br /> &lt;math&gt; \mathrm{\textbf{(A)} \ }\frac{1}{2}\qquad \mathrm{\textbf{(B)} \ } \frac{2}{3}\qquad \mathrm{\textbf{(C)} \ } \frac{3}{4}\qquad \mathrm{\textbf{(D)} \ } \frac{5}{6}\qquad \mathrm{\textbf{(E)} \ }\frac{7}{8}&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> Denote &quot;winning&quot; to mean &quot;picking a greater number&quot;.<br /> There is a &lt;math&gt;\frac{1}{2}&lt;/math&gt; chance that Laurent chooses a number in the interval &lt;math&gt;[2017, 4034]&lt;/math&gt;. In this case, Chloé cannot possibly win, since the maximum number she can pick is &lt;math&gt;2017&lt;/math&gt;. Otherwise, if Laurent picks a number in the interval &lt;math&gt;[0, 2017]&lt;/math&gt;, with probability &lt;math&gt;\frac{1}{2}&lt;/math&gt;, then the two people are symmetric, and each has a &lt;math&gt;\frac{1}{2}&lt;/math&gt; chance of winning. Then, the total probability is &lt;math&gt;\frac{1}{2}*1 + \frac{1}{2}*\frac{1}{2} = \boxed{\textbf{(C)}\ \frac{3}{4}}&lt;/math&gt;<br /> <br /> ==Solution 2==<br /> We can use geometric probability to solve this.<br /> Suppose a point &lt;math&gt;(x,y)&lt;/math&gt; lies in the &lt;math&gt;xy&lt;/math&gt;-plane. Let &lt;math&gt;x&lt;/math&gt; be Chloe's number and &lt;math&gt;y&lt;/math&gt; be Laurent's number. Then obviously we want &lt;math&gt;y&gt;x&lt;/math&gt;, which basically gives us a region above a line. We know that Chloe's number is in the interval &lt;math&gt;[0,2017]&lt;/math&gt; and Laurent's number is in the interval &lt;math&gt;[0,4034]&lt;/math&gt;, so we can create a rectangle in the plane, whose length is &lt;math&gt;2017&lt;/math&gt; and whose width is &lt;math&gt;4034&lt;/math&gt;. Drawing it out, we see that it is easier to find the probability that Chloe's number is greater than Laurent's number and subtract this probability from &lt;math&gt;1&lt;/math&gt;. The probability that Chloe's number is larger than Laurent's number is simply the area of the region under the line &lt;math&gt;y&gt;x&lt;/math&gt;, which is &lt;math&gt;\frac{2017 \cdot 2017}{2}&lt;/math&gt;. Instead of bashing this out we know that the rectangle has area &lt;math&gt;2017 \cdot 4034&lt;/math&gt;. So the probability that Laurent has a smaller number is &lt;math&gt;\frac{2017 \cdot 2017}{2 \cdot 2017 \cdot 4034}&lt;/math&gt;. Simplifying the expression yields &lt;math&gt;\frac{1}{4}&lt;/math&gt; and so &lt;math&gt;1-\frac{1}{4}= \boxed{\textbf{(C)}\ \frac{3}{4}}&lt;/math&gt;.<br /> <br /> ==Solution 3==<br /> Scale down by &lt;math&gt;2017&lt;/math&gt; to get that Chloe picks from &lt;math&gt;[0,1]&lt;/math&gt; and Laurent picks from &lt;math&gt;[0,2]&lt;/math&gt;. There are an infinite number of cases for the number that Chloe picks, but they are all centered around the average of &lt;math&gt;0.5&lt;/math&gt;. Therefore, Laurent has a range of &lt;math&gt;0.5&lt;/math&gt; to &lt;math&gt;2&lt;/math&gt; to pick from, on average, which is a length of &lt;math&gt;2-0.5=1.5&lt;/math&gt; out of a total length of &lt;math&gt;2-0=2&lt;/math&gt;. Therefore, the probability is &lt;math&gt;1.5/2=15/20=\boxed{\frac{3}{4} \space \text{(C)}}&lt;/math&gt;<br /> ==Video Solution==<br /> A video solution for this can be found here: https://www.youtube.com/watch?v=PQFNwW1XFaQ<br /> <br /> ==Video Solution 2==<br /> https://youtu.be/s4vnGlwwHHw<br /> <br /> ==See Also==<br /> {{AMC10 box|year=2017|ab=A|num-b=14|num-a=16}}<br /> {{MAA Notice}}<br /> <br /> [[Category:Introductory Probability Problems]]</div> Totoro.selsel https://artofproblemsolving.com/wiki/index.php?title=2017_AMC_10A_Problems/Problem_22&diff=115572 2017 AMC 10A Problems/Problem 22 2020-01-26T03:57:36Z <p>Totoro.selsel: /* Video Solution */</p> <hr /> <div>==Problem==<br /> <br /> Sides &lt;math&gt;\overline{AB}&lt;/math&gt; and &lt;math&gt;\overline{AC}&lt;/math&gt; of equilateral triangle &lt;math&gt;ABC&lt;/math&gt; are tangent to a circle at points &lt;math&gt;B&lt;/math&gt; and &lt;math&gt;C&lt;/math&gt; respectively. What fraction of the area of &lt;math&gt;\triangle ABC&lt;/math&gt; lies outside the circle?<br /> <br /> &lt;math&gt;\textbf{(A) } \frac{4\sqrt{3}\pi}{27}-\frac{1}{3}\qquad \textbf{(B) } \frac{\sqrt{3}}{2}-\frac{\pi}{8}\qquad \textbf{(C) } \frac{1}{2} \qquad \textbf{(D) } \sqrt{3}-\frac{2\sqrt{3}\pi}{9}\qquad \textbf{(E) } \frac{4}{3}-\frac{4\sqrt{3}\pi}{27}&lt;/math&gt;<br /> <br /> ==Solution==<br /> &lt;asy&gt;<br /> real sqrt3 = 1.73205080757;<br /> draw(Circle((4, 4), 4));<br /> draw((4-2*sqrt3,6)--(4,4)--(4+2*sqrt3,6)--(4-2*sqrt3,6)--(4,12)--(4+2*sqrt3,6));<br /> label(&quot;A&quot;, (4, 12.4));<br /> label(&quot;B&quot;, (-.3, 6.3));<br /> label(&quot;C&quot;, (8.3, 6.3));<br /> label(&quot;O&quot;, (4, 3.4));<br /> &lt;/asy&gt;<br /> Let the radius of the circle be &lt;math&gt;r&lt;/math&gt;, and let its center be &lt;math&gt;O&lt;/math&gt;. Since &lt;math&gt;\overline{AB}&lt;/math&gt; and &lt;math&gt;\overline{AC}&lt;/math&gt; are tangent to circle &lt;math&gt;O&lt;/math&gt;, then &lt;math&gt;\angle OBA = \angle OCA = 90^{\circ}&lt;/math&gt;, so &lt;math&gt;\angle BOC = 120^{\circ}&lt;/math&gt;. Therefore, since &lt;math&gt;\overline{OB}&lt;/math&gt; and &lt;math&gt;\overline{OC}&lt;/math&gt; are equal to &lt;math&gt;r&lt;/math&gt;, then (pick your favorite method) &lt;math&gt;\overline{BC} = r\sqrt{3}&lt;/math&gt;. The area of the equilateral triangle is &lt;math&gt;\frac{(r\sqrt{3})^2 \sqrt{3}}4 = \frac{3r^2 \sqrt{3}}4&lt;/math&gt;, and the area of the sector we are subtracting from it is &lt;math&gt;\frac 13 \pi r^2 - \frac 12 r \cdot r \cdot \frac{\sqrt{3}}2 = \frac{\pi r^2}3 -\frac{r^2 \sqrt{3}}4&lt;/math&gt;. The area outside of the circle is &lt;math&gt; \frac{3r^2 \sqrt{3}}4-\left(\frac{\pi r^2}3 -\frac{r^2 \sqrt{3}}4\right) = r^2 \sqrt{3} - \frac{\pi r^2}3&lt;/math&gt;. Therefore, the answer is &lt;cmath&gt;\frac{r^2 \sqrt{3} - \frac{\pi r^2}3}{\frac{3r^2 \sqrt{3}}4} = \boxed{\textbf{(E) } \frac 43 - \frac{4\sqrt 3 \pi}{27}}&lt;/cmath&gt;<br /> <br /> ==Video Solution==<br /> https://www.youtube.com/watch?v=GnJDNtjd57k&amp;feature=youtu.be<br /> <br /> ==See Also==<br /> {{AMC10 box|year=2017|ab=A|num-b=21|num-a=23}}<br /> {{MAA Notice}}<br /> <br /> [[Category:Introductory Geometry Problems]]</div> Totoro.selsel https://artofproblemsolving.com/wiki/index.php?title=Euclidean_algorithm&diff=110865 Euclidean algorithm 2019-11-04T02:34:50Z <p>Totoro.selsel: /* hi :) */</p> <hr /> <div>The '''Euclidean algorithm''' (also known as the '''Euclidean division algorithm''' or '''Euclid's algorithm''') is an algorithm that finds the [[greatest common divisor]] (GCD) of two elements of a [[Euclidean domain]], the most common of which is the [[nonnegative]] [[integer]]s &lt;math&gt;\mathbb{Z}{\geq 0}&lt;/math&gt;, without [[factoring]] them.<br /> <br /> ==Main idea and Informal Description==<br /> The basic idea is to repeatedly use the fact that &lt;math&gt;\gcd({a,b}) \equiv \gcd({b,a - b})&lt;/math&gt;<br /> <br /> If we have two non-negative integers &lt;math&gt;a,b&lt;/math&gt; with &lt;math&gt;a|b&lt;/math&gt; and &lt;math&gt;b\ne0&lt;/math&gt;, then the greatest common divisor is &lt;math&gt;{a}&lt;/math&gt;. If &lt;math&gt;a\ge b&gt;0&lt;/math&gt;, then the set of common divisors of &lt;math&gt;{a}&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; is the same as the set of common divisors of &lt;math&gt;b&lt;/math&gt; and &lt;math&gt;r&lt;/math&gt; where &lt;math&gt;r&lt;/math&gt; is the [[remainder]] of division of &lt;math&gt;{a}&lt;/math&gt; by &lt;math&gt;b&lt;/math&gt;. Indeed, we have &lt;math&gt;a=mb+r&lt;/math&gt; with some integer &lt;math&gt;m&lt;/math&gt;, so, if &lt;math&gt;{d}&lt;/math&gt; divides both &lt;math&gt;{a}&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt;, it must divide both &lt;math&gt;{a}&lt;/math&gt; and &lt;math&gt;mb&lt;/math&gt; and, thereby, their difference &lt;math&gt;r&lt;/math&gt;. Similarly, if &lt;math&gt;{d}&lt;/math&gt; divides both &lt;math&gt;b&lt;/math&gt; and &lt;math&gt;r&lt;/math&gt;, it should divide &lt;math&gt;{a}&lt;/math&gt; as well. Thus, the greatest common divisors of &lt;math&gt;{a}&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; and of &lt;math&gt;b&lt;/math&gt; and &lt;math&gt;r&lt;/math&gt; coincide: &lt;math&gt;GCD(a,b)=GCD(b,r)&lt;/math&gt;. But the pair &lt;math&gt;(b,r)&lt;/math&gt; consists of smaller numbers than the pair &lt;math&gt;(a,b)&lt;/math&gt;! So, we reduced our task to a simpler one. And we can do this reduction again and again until the smaller number becomes &lt;math&gt;0&lt;/math&gt;.<br /> <br /> == General Form ==<br /> Start with any two elements &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; of a [[Euclidean Domain]]<br /> <br /> * If &lt;math&gt;b=0&lt;/math&gt;, then &lt;math&gt;\gcd(a,b)=a&lt;/math&gt;.<br /> * Otherwise take the remainder when &lt;math&gt;{a}&lt;/math&gt; is divided by &lt;math&gt;a \pmod{b}&lt;/math&gt;, and find &lt;math&gt;\gcd(a,a \bmod {b})&lt;/math&gt;.<br /> * Repeat this until the remainder is 0.&lt;br&gt;<br /> <br /> &lt;math&gt;a \pmod{b} \equiv r_1&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;b \pmod {r_1} \equiv r_2&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt; \vdots&lt;/math&gt; &lt;br&gt;<br /> &lt;math&gt;r_{n-1} \pmod r_n \equiv 0&lt;/math&gt;&lt;br&gt;<br /> Then &lt;math&gt;\gcd({a,b}) = r_n&lt;/math&gt;&lt;br&gt;<br /> <br /> Usually the Euclidean algorithm is written down just as a chain of divisions with remainder:<br /> <br /> for &lt;math&gt;r_{k+1} &lt; r_k &lt; r_{k-1}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;a = b \cdot q_1+r_1&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;b = r_1 \cdot q_2 + r_2&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;r_1 = r_2 \cdot q_3 + r_3&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;\vdots&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;r_{n-1} = r_n \cdot q_{n+1} +0&lt;/math&gt;&lt;br&gt;<br /> and so &lt;math&gt;\gcd({a,b}) = r_n&lt;/math&gt;&lt;br&gt;<br /> <br /> == Example ==<br /> To see how it works, just take an example. Say &lt;math&gt;a = 93, b=42&lt;/math&gt;. &lt;br/&gt;<br /> We have &lt;math&gt;93 \equiv 9 \pmod{42}&lt;/math&gt;, so &lt;math&gt;\gcd(93,42) = \gcd(42,9)&lt;/math&gt;. &lt;br/&gt; <br /> Similarly, &lt;math&gt;42 \equiv 6 \pmod{9}&lt;/math&gt;, so &lt;math&gt;\gcd(42,9) = \gcd(9,6)&lt;/math&gt;. &lt;br/&gt;<br /> Continuing, &lt;math&gt;9 \equiv 3 \pmod{6}&lt;/math&gt;, so &lt;math&gt;\gcd(9,6) = \gcd(6,3)&lt;/math&gt;. &lt;br/&gt;<br /> Then &lt;math&gt;6 \equiv 0 \pmod{3}&lt;/math&gt;, so &lt;math&gt;\gcd(6,3) = \gcd(3,0) = 3&lt;/math&gt;. &lt;br/&gt;<br /> Thus &lt;math&gt;\gcd(93,42) = 3&lt;/math&gt;.<br /> <br /> * &lt;math&gt;93 = 2 \cdot 42 + 9 \qquad (1)&lt;/math&gt;<br /> * &lt;math&gt;42 = 4 \cdot 9 + 6 \qquad (2)&lt;/math&gt;<br /> * &lt;math&gt;9 = 1 \cdot 6 + 3 \qquad (3)&lt;/math&gt;<br /> * &lt;math&gt;6 = 2 \cdot 3 + 0 \qquad (4)&lt;/math&gt;<br /> <br /> == Extended Euclidean Algorithm ==<br /> An added bonus of the Euclidean algorithm is the &quot;linear representation&quot; of the greatest common divisor. This allows us to write &lt;math&gt;\gcd(a,b)=ax+by&lt;/math&gt;, where &lt;math&gt;x,y&lt;/math&gt; are some elements from the same [[Euclidean Domain]] as &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; that can be determined using the algorithm. We can work backwards from whichever step is the most convenient.<br /> <br /> Continuing the previous example, our goal is to find &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; such that &lt;math&gt;93a + 42b = \gcd(93,42) = 3.&lt;/math&gt; We can work backwards from equation &lt;math&gt;(3)&lt;/math&gt; since &lt;math&gt;3&lt;/math&gt; appears there:<br /> <br /> &lt;math&gt;3 = 9 - 1 \cdot 6&lt;/math&gt;<br /> <br /> We currently have &lt;math&gt;3&lt;/math&gt; as a linear combination of &lt;math&gt;6&lt;/math&gt; and &lt;math&gt;9&lt;/math&gt;. Our goal is to replace &lt;math&gt;6&lt;/math&gt; and &lt;math&gt;9&lt;/math&gt; so that we have a linear combination of &lt;math&gt;42&lt;/math&gt; and &lt;math&gt;93&lt;/math&gt; only. We start by rearranging &lt;math&gt;(2)&lt;/math&gt; to &lt;math&gt;6 = 42 - 4 \cdot 9&lt;/math&gt; so we can substitute &lt;math&gt;6&lt;/math&gt; to express &lt;math&gt;3&lt;/math&gt; as a linear combination of &lt;math&gt;9&lt;/math&gt; and &lt;math&gt;42&lt;/math&gt;:<br /> <br /> &lt;math&gt;3 = 9 - 1 \cdot (42 - 4 \cdot 9)&lt;/math&gt; &lt;br&gt;<br /> &lt;math&gt;3 = -1 \cdot 42 + 5 \cdot 9.&lt;/math&gt; &lt;br&gt;<br /> <br /> Continuing, we rearrange &lt;math&gt;(1)&lt;/math&gt; to substitute &lt;math&gt;9 = 93 - 2 \cdot 42&lt;/math&gt;:<br /> <br /> &lt;math&gt;3 = -1 \cdot 42 + 5 \cdot (93 - 2 \cdot 42)&lt;/math&gt; &lt;br&gt;<br /> &lt;math&gt;3 = -11 \cdot 42 + 5 \cdot 93. \qquad (5)&lt;/math&gt; &lt;br&gt;<br /> <br /> We have found one linear combination. To find others, since &lt;math&gt;42 \cdot 93 - 93 \cdot 42 = 0&lt;/math&gt;, dividing both sides by &lt;math&gt;\gcd(93,42) = 3&lt;/math&gt; gives &lt;math&gt;14 \cdot 93 - 31 \cdot 42 = 0&lt;/math&gt;. We can add &lt;math&gt;k&lt;/math&gt; times this equation to &lt;math&gt;(5)&lt;/math&gt;, so we can write &lt;math&gt;3&lt;/math&gt; as a linear combination of &lt;math&gt;93&lt;/math&gt; and &lt;math&gt;42&lt;/math&gt;<br /> <br /> &lt;math&gt;3 = (14k + 5) \cdot 93 + (-31k - 11) \cdot 42&lt;/math&gt;<br /> <br /> for any integer &lt;math&gt;k&lt;/math&gt;.<br /> <br /> == Problems ==<br /> ===Introductory===<br /> ===Intermediate===<br /> * [[1985 AIME Problems/Problem 13]]<br /> * [[1959 IMO Problems/Problem 1]] (Note: this problem is widely regarded as the easiest problem ever asked in the IMO)<br /> <br /> ===Olympiad===<br /> <br /> ==See Also==<br /> *[[Divisibility]]<br /> <br /> [[Category:Algorithms]]<br /> [[Category:Number theory]]</div> Totoro.selsel https://artofproblemsolving.com/wiki/index.php?title=Euclidean_algorithm&diff=110863 Euclidean algorithm 2019-11-04T02:34:31Z <p>Totoro.selsel: /* Olympiad */</p> <hr /> <div>The '''Euclidean algorithm''' (also known as the '''Euclidean division algorithm''' or '''Euclid's algorithm''') is an algorithm that finds the [[greatest common divisor]] (GCD) of two elements of a [[Euclidean domain]], the most common of which is the [[nonnegative]] [[integer]]s &lt;math&gt;\mathbb{Z}{\geq 0}&lt;/math&gt;, without [[factoring]] them.<br /> <br /> ==Main idea and Informal Description==<br /> The basic idea is to repeatedly use the fact that &lt;math&gt;\gcd({a,b}) \equiv \gcd({b,a - b})&lt;/math&gt;<br /> <br /> If we have two non-negative integers &lt;math&gt;a,b&lt;/math&gt; with &lt;math&gt;a|b&lt;/math&gt; and &lt;math&gt;b\ne0&lt;/math&gt;, then the greatest common divisor is &lt;math&gt;{a}&lt;/math&gt;. If &lt;math&gt;a\ge b&gt;0&lt;/math&gt;, then the set of common divisors of &lt;math&gt;{a}&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; is the same as the set of common divisors of &lt;math&gt;b&lt;/math&gt; and &lt;math&gt;r&lt;/math&gt; where &lt;math&gt;r&lt;/math&gt; is the [[remainder]] of division of &lt;math&gt;{a}&lt;/math&gt; by &lt;math&gt;b&lt;/math&gt;. Indeed, we have &lt;math&gt;a=mb+r&lt;/math&gt; with some integer &lt;math&gt;m&lt;/math&gt;, so, if &lt;math&gt;{d}&lt;/math&gt; divides both &lt;math&gt;{a}&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt;, it must divide both &lt;math&gt;{a}&lt;/math&gt; and &lt;math&gt;mb&lt;/math&gt; and, thereby, their difference &lt;math&gt;r&lt;/math&gt;. Similarly, if &lt;math&gt;{d}&lt;/math&gt; divides both &lt;math&gt;b&lt;/math&gt; and &lt;math&gt;r&lt;/math&gt;, it should divide &lt;math&gt;{a}&lt;/math&gt; as well. Thus, the greatest common divisors of &lt;math&gt;{a}&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; and of &lt;math&gt;b&lt;/math&gt; and &lt;math&gt;r&lt;/math&gt; coincide: &lt;math&gt;GCD(a,b)=GCD(b,r)&lt;/math&gt;. But the pair &lt;math&gt;(b,r)&lt;/math&gt; consists of smaller numbers than the pair &lt;math&gt;(a,b)&lt;/math&gt;! So, we reduced our task to a simpler one. And we can do this reduction again and again until the smaller number becomes &lt;math&gt;0&lt;/math&gt;.<br /> <br /> == General Form ==<br /> Start with any two elements &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; of a [[Euclidean Domain]]<br /> <br /> * If &lt;math&gt;b=0&lt;/math&gt;, then &lt;math&gt;\gcd(a,b)=a&lt;/math&gt;.<br /> * Otherwise take the remainder when &lt;math&gt;{a}&lt;/math&gt; is divided by &lt;math&gt;a \pmod{b}&lt;/math&gt;, and find &lt;math&gt;\gcd(a,a \bmod {b})&lt;/math&gt;.<br /> * Repeat this until the remainder is 0.&lt;br&gt;<br /> <br /> &lt;math&gt;a \pmod{b} \equiv r_1&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;b \pmod {r_1} \equiv r_2&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt; \vdots&lt;/math&gt; &lt;br&gt;<br /> &lt;math&gt;r_{n-1} \pmod r_n \equiv 0&lt;/math&gt;&lt;br&gt;<br /> Then &lt;math&gt;\gcd({a,b}) = r_n&lt;/math&gt;&lt;br&gt;<br /> <br /> Usually the Euclidean algorithm is written down just as a chain of divisions with remainder:<br /> <br /> for &lt;math&gt;r_{k+1} &lt; r_k &lt; r_{k-1}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;a = b \cdot q_1+r_1&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;b = r_1 \cdot q_2 + r_2&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;r_1 = r_2 \cdot q_3 + r_3&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;\vdots&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;r_{n-1} = r_n \cdot q_{n+1} +0&lt;/math&gt;&lt;br&gt;<br /> and so &lt;math&gt;\gcd({a,b}) = r_n&lt;/math&gt;&lt;br&gt;<br /> <br /> == Example ==<br /> To see how it works, just take an example. Say &lt;math&gt;a = 93, b=42&lt;/math&gt;. &lt;br/&gt;<br /> We have &lt;math&gt;93 \equiv 9 \pmod{42}&lt;/math&gt;, so &lt;math&gt;\gcd(93,42) = \gcd(42,9)&lt;/math&gt;. &lt;br/&gt; <br /> Similarly, &lt;math&gt;42 \equiv 6 \pmod{9}&lt;/math&gt;, so &lt;math&gt;\gcd(42,9) = \gcd(9,6)&lt;/math&gt;. &lt;br/&gt;<br /> Continuing, &lt;math&gt;9 \equiv 3 \pmod{6}&lt;/math&gt;, so &lt;math&gt;\gcd(9,6) = \gcd(6,3)&lt;/math&gt;. &lt;br/&gt;<br /> Then &lt;math&gt;6 \equiv 0 \pmod{3}&lt;/math&gt;, so &lt;math&gt;\gcd(6,3) = \gcd(3,0) = 3&lt;/math&gt;. &lt;br/&gt;<br /> Thus &lt;math&gt;\gcd(93,42) = 3&lt;/math&gt;.<br /> <br /> * &lt;math&gt;93 = 2 \cdot 42 + 9 \qquad (1)&lt;/math&gt;<br /> * &lt;math&gt;42 = 4 \cdot 9 + 6 \qquad (2)&lt;/math&gt;<br /> * &lt;math&gt;9 = 1 \cdot 6 + 3 \qquad (3)&lt;/math&gt;<br /> * &lt;math&gt;6 = 2 \cdot 3 + 0 \qquad (4)&lt;/math&gt;<br /> <br /> == Extended Euclidean Algorithm ==<br /> An added bonus of the Euclidean algorithm is the &quot;linear representation&quot; of the greatest common divisor. This allows us to write &lt;math&gt;\gcd(a,b)=ax+by&lt;/math&gt;, where &lt;math&gt;x,y&lt;/math&gt; are some elements from the same [[Euclidean Domain]] as &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; that can be determined using the algorithm. We can work backwards from whichever step is the most convenient.<br /> <br /> Continuing the previous example, our goal is to find &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; such that &lt;math&gt;93a + 42b = \gcd(93,42) = 3.&lt;/math&gt; We can work backwards from equation &lt;math&gt;(3)&lt;/math&gt; since &lt;math&gt;3&lt;/math&gt; appears there:<br /> <br /> &lt;math&gt;3 = 9 - 1 \cdot 6&lt;/math&gt;<br /> <br /> We currently have &lt;math&gt;3&lt;/math&gt; as a linear combination of &lt;math&gt;6&lt;/math&gt; and &lt;math&gt;9&lt;/math&gt;. Our goal is to replace &lt;math&gt;6&lt;/math&gt; and &lt;math&gt;9&lt;/math&gt; so that we have a linear combination of &lt;math&gt;42&lt;/math&gt; and &lt;math&gt;93&lt;/math&gt; only. We start by rearranging &lt;math&gt;(2)&lt;/math&gt; to &lt;math&gt;6 = 42 - 4 \cdot 9&lt;/math&gt; so we can substitute &lt;math&gt;6&lt;/math&gt; to express &lt;math&gt;3&lt;/math&gt; as a linear combination of &lt;math&gt;9&lt;/math&gt; and &lt;math&gt;42&lt;/math&gt;:<br /> <br /> &lt;math&gt;3 = 9 - 1 \cdot (42 - 4 \cdot 9)&lt;/math&gt; &lt;br&gt;<br /> &lt;math&gt;3 = -1 \cdot 42 + 5 \cdot 9.&lt;/math&gt; &lt;br&gt;<br /> <br /> Continuing, we rearrange &lt;math&gt;(1)&lt;/math&gt; to substitute &lt;math&gt;9 = 93 - 2 \cdot 42&lt;/math&gt;:<br /> <br /> &lt;math&gt;3 = -1 \cdot 42 + 5 \cdot (93 - 2 \cdot 42)&lt;/math&gt; &lt;br&gt;<br /> &lt;math&gt;3 = -11 \cdot 42 + 5 \cdot 93. \qquad (5)&lt;/math&gt; &lt;br&gt;<br /> <br /> We have found one linear combination. To find others, since &lt;math&gt;42 \cdot 93 - 93 \cdot 42 = 0&lt;/math&gt;, dividing both sides by &lt;math&gt;\gcd(93,42) = 3&lt;/math&gt; gives &lt;math&gt;14 \cdot 93 - 31 \cdot 42 = 0&lt;/math&gt;. We can add &lt;math&gt;k&lt;/math&gt; times this equation to &lt;math&gt;(5)&lt;/math&gt;, so we can write &lt;math&gt;3&lt;/math&gt; as a linear combination of &lt;math&gt;93&lt;/math&gt; and &lt;math&gt;42&lt;/math&gt;<br /> <br /> &lt;math&gt;3 = (14k + 5) \cdot 93 + (-31k - 11) \cdot 42&lt;/math&gt;<br /> <br /> for any integer &lt;math&gt;k&lt;/math&gt;.<br /> <br /> == Problems ==<br /> ===Introductory===<br /> ===Intermediate===<br /> * [[1985 AIME Problems/Problem 13]]<br /> * [[1959 IMO Problems/Problem 1]] (Note: this problem is widely regarded as the easiest problem ever asked in the IMO)<br /> <br /> ===hi :) ===<br /> <br /> ==See Also==<br /> *[[Divisibility]]<br /> <br /> [[Category:Algorithms]]<br /> [[Category:Number theory]]</div> Totoro.selsel https://artofproblemsolving.com/wiki/index.php?title=2018_AMC_8_Problems/Problem_19&diff=110744 2018 AMC 8 Problems/Problem 19 2019-11-01T02:44:13Z <p>Totoro.selsel: /* Solution 2 */</p> <hr /> <div>=Problem 19=<br /> In a sign pyramid a cell gets a &quot;+&quot; if the two cells below it have the same sign, and it gets a &quot;-&quot; if the two cells below it have different signs. The diagram below illustrates a sign pyramid with four levels. How many possible ways are there to fill the four cells in the bottom row to produce a &quot;+&quot; at the top of the pyramid?<br /> <br /> &lt;asy&gt;<br /> unitsize(2cm);<br /> path box = (-0.5,-0.2)--(-0.5,0.2)--(0.5,0.2)--(0.5,-0.2)--cycle;<br /> draw(box); label(&quot;$+$&quot;,(0,0));<br /> draw(shift(1,0)*box); label(&quot;$-$&quot;,(1,0));<br /> draw(shift(2,0)*box); label(&quot;$+$&quot;,(2,0));<br /> draw(shift(3,0)*box); label(&quot;$-$&quot;,(3,0));<br /> draw(shift(0.5,0.4)*box); label(&quot;$-$&quot;,(0.5,0.4));<br /> draw(shift(1.5,0.4)*box); label(&quot;$-$&quot;,(1.5,0.4));<br /> draw(shift(2.5,0.4)*box); label(&quot;$-$&quot;,(2.5,0.4));<br /> draw(shift(1,0.8)*box); label(&quot;$+$&quot;,(1,0.8));<br /> draw(shift(2,0.8)*box); label(&quot;$+$&quot;,(2,0.8));<br /> draw(shift(1.5,1.2)*box); label(&quot;$+$&quot;,(1.5,1.2));<br /> &lt;/asy&gt;<br /> <br /> &lt;math&gt;\textbf{(A) } 2 \qquad \textbf{(B) } 4 \qquad \textbf{(C) } 8 \qquad \textbf{(D) } 12 \qquad \textbf{(E) } 16&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> Instead of + and -, let us use 1 and 0, respectively. If we let &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; be the values of the four cells on the bottom row, then the three cells on the next row are equal to &lt;math&gt;a+b&lt;/math&gt;, &lt;math&gt;b+c&lt;/math&gt;, and &lt;math&gt;c+d&lt;/math&gt; taken modulo 2 (this is exactly the same as finding &lt;math&gt;a \text{ XOR } b&lt;/math&gt;, and so on). The two cells on the next row are &lt;math&gt;a+2b+c&lt;/math&gt; and &lt;math&gt;b+2c+d&lt;/math&gt; taken modulo 2, and lastly, the cell on the top row gets &lt;math&gt;a+3b+3c+d \pmod{2}&lt;/math&gt;.<br /> <br /> Thus, we are looking for the number of assignments of 0's and 1's for &lt;math&gt;a&lt;/math&gt;, &lt;math&gt;b&lt;/math&gt;, &lt;math&gt;c&lt;/math&gt;, &lt;math&gt;d&lt;/math&gt; such that &lt;math&gt;a+3b+3c+d \equiv 1 \pmod{2}&lt;/math&gt;, or in other words, is odd. As &lt;math&gt;3 \equiv 1 \pmod{2}&lt;/math&gt;, this is the same as finding the number of assignments such that &lt;math&gt;a+b+c+d \equiv 1 \pmod{2}&lt;/math&gt;. Notice that, no matter what &lt;math&gt;a&lt;/math&gt;, &lt;math&gt;b&lt;/math&gt;, and &lt;math&gt;c&lt;/math&gt; are, this uniquely determines &lt;math&gt;d&lt;/math&gt;. There are &lt;math&gt;2^3 = 8&lt;/math&gt; ways to assign 0's and 1's arbitrarily to &lt;math&gt;a&lt;/math&gt;, &lt;math&gt;b&lt;/math&gt;, and &lt;math&gt;c&lt;/math&gt;, so the answer is &lt;math&gt;\boxed{\textbf{(C) } 8}&lt;/math&gt;.<br /> <br /> ==Solution 2==<br /> The sign of the next row on the pyramid depends on previous row. There are two options for the previous row, - or +. There are three rows to the pyramid that depend on what the top row is. Therefore, the ways you can make a + on the top is 2^3=8, which is C.<br /> -totoro.selsel<br /> <br /> ==See Also==<br /> <br /> {{AMC8 box|year=2018|num-b=18|num-a=20}}<br /> <br /> {{MAA Notice}}</div> Totoro.selsel