https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Hakkapeliitta&feedformat=atom AoPS Wiki - User contributions [en] 2021-04-21T02:30:02Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2008_AMC_12A_Problems/Problem_17&diff=49345 2008 AMC 12A Problems/Problem 17 2012-11-07T04:30:11Z <p>Hakkapeliitta: </p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;a_1,a_2,\ldots&lt;/math&gt; be a sequence determined by the rule &lt;math&gt;a_n=a_{n-1}/2&lt;/math&gt; if &lt;math&gt;a_{n-1}&lt;/math&gt; is even and &lt;math&gt;a_n=3a_{n-1}+1&lt;/math&gt; if &lt;math&gt;a_{n-1}&lt;/math&gt; is odd. For how many positive integers &lt;math&gt;a_1 \le 2008&lt;/math&gt; is it true that &lt;math&gt;a_1&lt;/math&gt; is less than each of &lt;math&gt;a_2&lt;/math&gt;, &lt;math&gt;a_3&lt;/math&gt;, and &lt;math&gt;a_4&lt;/math&gt;? <br /> <br /> &lt;math&gt;\mathrm{(A)}\ 250\qquad\mathrm{(B)}\ 251\qquad\mathrm{(C)}\ 501\qquad\mathrm{(D)}\ 502\qquad\mathrm{(E)} 1004&lt;/math&gt;<br /> <br /> ==Solution==<br /> All positive integers can be expressed as &lt;math&gt;4n&lt;/math&gt;, &lt;math&gt;4n+1&lt;/math&gt;, &lt;math&gt;4n+2&lt;/math&gt;, or &lt;math&gt;4n+3&lt;/math&gt;, where &lt;math&gt;n&lt;/math&gt; is a nonnegative integer. <br /> <br /> *If &lt;math&gt;a_1=4n&lt;/math&gt;, then &lt;math&gt;a_2=\frac{4n}{2}=2n&lt;a_1&lt;/math&gt;. <br /> <br /> *If &lt;math&gt;a_1=4n+1&lt;/math&gt;, then &lt;math&gt;a_2=3(4n+1)+1=12n+4&lt;/math&gt;, &lt;math&gt;a_3=\frac{12n+4}{2}=6n+2&lt;/math&gt;, and &lt;math&gt;a_4=\frac{6n+2}{2}=3n+1&lt;a_1&lt;/math&gt;.<br /> <br /> *If &lt;math&gt;a_1=4n+2&lt;/math&gt;, then &lt;math&gt;a_2=2n+1&lt;a_1&lt;/math&gt;. <br /> <br /> *If &lt;math&gt;a_1=4n+3&lt;/math&gt;, then &lt;math&gt;a_2=3(4n+3)+1=12n+10&lt;/math&gt;, &lt;math&gt;a_3=\frac{12n+10}{2}=6n+5&lt;/math&gt;, and &lt;math&gt;a_4=3(6n+5)+1=18n+16&lt;/math&gt;.<br /> <br /> Since &lt;math&gt;12n+10, 6n+5, 18n+16 &gt; 4n+3&lt;/math&gt;, every positive integer &lt;math&gt;a_1=4n+3&lt;/math&gt; will satisfy &lt;math&gt;a_1&lt;a_2,a_3,a_4&lt;/math&gt;. <br /> <br /> Since one fourth of the positive integers &lt;math&gt;a_1 \le 2008&lt;/math&gt; can be expressed as &lt;math&gt;4n+3&lt;/math&gt;, where &lt;math&gt;n&lt;/math&gt; is a nonnegative integer, the answer is &lt;math&gt;\frac{1}{4}\cdot 2008 = 502 \Rightarrow D&lt;/math&gt;.<br /> <br /> <br /> ==Alternate Solution==<br /> After checking the first few &lt;math&gt;a_n&lt;/math&gt; such as &lt;math&gt;1&lt;/math&gt;, &lt;math&gt;2&lt;/math&gt; through &lt;math&gt;7&lt;/math&gt;, we can see that the only &lt;math&gt;a_1&lt;/math&gt; that satisfy the conditions are odd numbers that when tripled and added 1 to, are double an odd number. For example, for &lt;math&gt;a_n=3&lt;/math&gt;, we notice the sequence yields &lt;math&gt;10&lt;/math&gt;, &lt;math&gt;5&lt;/math&gt;, and &lt;math&gt;16&lt;/math&gt;, a valid sequence.<br /> <br /> So we can set up an equation, &lt;math&gt;3x + 1 = 2(2k - 1)&lt;/math&gt; where x is equal to &lt;math&gt;a_1&lt;/math&gt;. Rearranging the equation yields &lt;math&gt;(3x + 3)/4 = k&lt;/math&gt;. Experimenting yields that every 4th &lt;math&gt;x&lt;/math&gt; after 3 creates an integer, and thus satisfies the sequence condition. So the number of valid solutions is equal to &lt;math&gt;2008/4 = 502 \Rightarrow D&lt;/math&gt;.<br /> ==See Also==<br /> {{AMC12 box|year=2008|ab=A|num-b=16|num-a=18}}<br /> [[Collatz Problem]]</div> Hakkapeliitta https://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_8&diff=48246 2010 AMC 12B Problems/Problem 8 2012-09-09T04:01:43Z <p>Hakkapeliitta: </p> <hr /> <div>== Problem 8 ==<br /> Every high school in the city of Euclid sent a team of &lt;math&gt;3&lt;/math&gt; students to a math contest. Each participant in the contest received a different score. Andrea's score was the median among all students, and hers was the highest score on her team. Andrea's teammates Beth and Carla placed &lt;math&gt;37&lt;/math&gt;&lt;sup&gt;th&lt;/sup&gt; and &lt;math&gt;64&lt;/math&gt;&lt;sup&gt;th&lt;/sup&gt;, respectively. How many schools are in the city?<br /> <br /> &lt;math&gt;\textbf{(A)}\ 22 \qquad \textbf{(B)}\ 23 \qquad \textbf{(C)}\ 24 \qquad \textbf{(D)}\ 25 \qquad \textbf{(E)}\ 26&lt;/math&gt;<br /> <br /> == Solution ==<br /> There are &lt;math&gt;x&lt;/math&gt; schools. This means that there are &lt;math&gt;3x&lt;/math&gt; people. Because no one's score was the same as another person's score, that means that there could only have been &lt;math&gt;1&lt;/math&gt; median score. This implies that &lt;math&gt;x&lt;/math&gt; is an odd number. &lt;math&gt;x&lt;/math&gt; cannot be less than &lt;math&gt;23&lt;/math&gt;, because there wouldn't be a &lt;math&gt;64&lt;/math&gt;th place if there were. &lt;math&gt;x&lt;/math&gt; cannot be greater than &lt;math&gt;23&lt;/math&gt; either, because that would tie Andrea and Beth or Andrea's place would be worse than Beth's. Thus, the only possible answer is &lt;math&gt;23 \Rightarrow \boxed{B}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AMC12 box|year=2010|num-b=7|num-a=9|ab=B}}</div> Hakkapeliitta https://artofproblemsolving.com/wiki/index.php?title=2012_AIME_I_Problems/Problem_3&diff=48007 2012 AIME I Problems/Problem 3 2012-08-21T17:33:58Z <p>Hakkapeliitta: </p> <hr /> <div>== Problem 3 ==<br /> Nine people sit down for dinner where there are three choices of meals. Three people order the beef meal, three order the chicken meal, and three order the fish meal. The waiter serves the nine meals in random order. Find the number of ways in which the waiter could serve the meal types to the nine people so that exactly one person receives the type of meal ordered by that person.<br /> <br /> ==Solution==<br /> Call a beef meal &lt;math&gt;B,&lt;/math&gt; a chicken meal &lt;math&gt;C,&lt;/math&gt; and a fish meal &lt;math&gt;F.&lt;/math&gt; Now say the nine people order meals &lt;math&gt;BBBCCCFFF&lt;/math&gt; respectively and say that the person who receives the correct meal is the first person. We will solve for this case and then multiply by &lt;math&gt;9&lt;/math&gt; to account for the &lt;math&gt;9&lt;/math&gt; different ways in which the person to receive the correct meal could be picked. Note, this implies that the dishes are indistinguishable, though the people aren't. For example, two people who order chicken are separate, though if they receive fish, there is only 1 way to order them.<br /> <br /> The problem we must solve is to distribute meals &lt;math&gt;BBCCCFFF&lt;/math&gt; to orders &lt;math&gt;BBCCCFFF&lt;/math&gt; with no matches. The two people who ordered &lt;math&gt;B&lt;/math&gt;'s can either both get &lt;math&gt;C&lt;/math&gt;'s, both get &lt;math&gt;F&lt;/math&gt;'s, or get one &lt;math&gt;C&lt;/math&gt; and one &lt;math&gt;F.&lt;/math&gt; We proceed with casework.<br /> <br /> &lt;UL&gt;<br /> &lt;LI&gt; If the two &lt;math&gt;B&lt;/math&gt; people both get &lt;math&gt;C&lt;/math&gt;'s, then the three &lt;math&gt;F&lt;/math&gt; meals left to distribute must all go to the &lt;math&gt;C&lt;/math&gt; people. The &lt;math&gt;F&lt;/math&gt; people then get &lt;math&gt;BBC&lt;/math&gt; in some order, which gives three possibilities. The indistinguishability is easier to see here, as we distribute the &lt;math&gt;F&lt;/math&gt; meals to the &lt;math&gt;C&lt;/math&gt; people, and there is only 1 way to order this, as all three meals are the same.&lt;/LI&gt;<br /> <br /> &lt;LI&gt; If the two &lt;math&gt;B&lt;/math&gt; people both get &lt;math&gt;F&lt;/math&gt;'s, the situation is identical to the above and three possibilities arise. &lt;/LI&gt;<br /> <br /> &lt;LI&gt; If the two &lt;math&gt;B&lt;/math&gt; people get &lt;math&gt;CF&lt;/math&gt; in some order, then the &lt;math&gt;C&lt;/math&gt; people must get &lt;math&gt;FFB&lt;/math&gt; and the &lt;math&gt;F&lt;/math&gt; people must get &lt;math&gt;CCB.&lt;/math&gt; This gives &lt;math&gt;2 \cdot 3 \cdot 3 = 18&lt;/math&gt; possibilities. &lt;/LI&gt;<br /> &lt;/UL&gt;<br /> <br /> Summing across the cases we see there are &lt;math&gt;24&lt;/math&gt; possibilities, so the answer is &lt;math&gt;9 \cdot 24 = \boxed{216.}&lt;/math&gt;<br /> <br /> == See also ==<br /> {{AIME box|year=2012|n=I|num-b=2|num-a=4}}</div> Hakkapeliitta https://artofproblemsolving.com/wiki/index.php?title=2012_AIME_I_Problems/Problem_3&diff=47861 2012 AIME I Problems/Problem 3 2012-08-10T05:20:56Z <p>Hakkapeliitta: /* Solution */</p> <hr /> <div>== Problem 3 ==<br /> Nine people sit down for dinner where there are three choices of meals. Three people order the beef meal, three order the chicken meal, and three order the fish meal. The waiter serves the nine meals in random order. Find the number of ways in which the waiter could serve the meal types to the nine people so that exactly one person receives the type of meal ordered by that person.<br /> <br /> ==Solution==<br /> Call a beef meal &lt;math&gt;B,&lt;/math&gt; a chicken meal &lt;math&gt;C,&lt;/math&gt; and a fish meal &lt;math&gt;F.&lt;/math&gt; Now say the nine people order meals &lt;math&gt;BBBCCCFFF&lt;/math&gt; respectively and say that the person who receives the correct meal is the first person. We will solve for this case and then multiply by &lt;math&gt;9&lt;/math&gt; to account for the &lt;math&gt;9&lt;/math&gt; different ways in which the person to receive the correct meal could be picked. Note, this implies that the dishes are indistinguishable, though the people are. For example, two people who order chicken are separate, though if they receive fish, there is only 1 way to order them.<br /> <br /> The problem we must solve is to distribute meals &lt;math&gt;BBCCCFFF&lt;/math&gt; to orders &lt;math&gt;BBCCCFFF&lt;/math&gt; with no matches. The two people who ordered &lt;math&gt;B&lt;/math&gt;'s can either both get &lt;math&gt;C&lt;/math&gt;'s, both get &lt;math&gt;F&lt;/math&gt;'s, or get one &lt;math&gt;C&lt;/math&gt; and one &lt;math&gt;F.&lt;/math&gt; We proceed with casework.<br /> <br /> &lt;UL&gt;<br /> &lt;LI&gt; If the two &lt;math&gt;B&lt;/math&gt; people both get &lt;math&gt;C&lt;/math&gt;'s, then the three &lt;math&gt;F&lt;/math&gt; meals left to distribute must all go to the &lt;math&gt;C&lt;/math&gt; people. The &lt;math&gt;F&lt;/math&gt; people then get &lt;math&gt;BBC&lt;/math&gt; in some order, which gives three possibilities. The indistinguishability is easier to see here, as we distribute the &lt;math&gt;F&lt;/math&gt; meals to the &lt;math&gt;C&lt;/math&gt; people, and there is only 1 way to order this, as all three meals are the same.&lt;/LI&gt;<br /> <br /> &lt;LI&gt; If the two &lt;math&gt;B&lt;/math&gt; people both get &lt;math&gt;F&lt;/math&gt;'s, the situation is identical to the above and three possibilities arise. &lt;/LI&gt;<br /> <br /> &lt;LI&gt; If the two &lt;math&gt;B&lt;/math&gt; people get &lt;math&gt;CF&lt;/math&gt; in some order, then the &lt;math&gt;C&lt;/math&gt; people must get &lt;math&gt;FFB&lt;/math&gt; and the &lt;math&gt;F&lt;/math&gt; people must get &lt;math&gt;CCB.&lt;/math&gt; This gives &lt;math&gt;2 \cdot 3 \cdot 3 = 18&lt;/math&gt; possibilities. &lt;/LI&gt;<br /> &lt;/UL&gt;<br /> <br /> Summing across the cases we see there are &lt;math&gt;24&lt;/math&gt; possibilities, so the answer is &lt;math&gt;9 \cdot 24 = \boxed{216.}&lt;/math&gt;<br /> <br /> == See also ==<br /> {{AIME box|year=2012|n=I|num-b=2|num-a=4}}</div> Hakkapeliitta https://artofproblemsolving.com/wiki/index.php?title=2012_AIME_I_Problems/Problem_3&diff=47860 2012 AIME I Problems/Problem 3 2012-08-10T05:19:10Z <p>Hakkapeliitta: /* Solution */</p> <hr /> <div>== Problem 3 ==<br /> Nine people sit down for dinner where there are three choices of meals. Three people order the beef meal, three order the chicken meal, and three order the fish meal. The waiter serves the nine meals in random order. Find the number of ways in which the waiter could serve the meal types to the nine people so that exactly one person receives the type of meal ordered by that person.<br /> <br /> ==Solution==<br /> Call a beef meal &lt;math&gt;B,&lt;/math&gt; a chicken meal &lt;math&gt;C,&lt;/math&gt; and a fish meal &lt;math&gt;F.&lt;/math&gt; Now say the nine people order meals &lt;math&gt;BBBCCCFFF&lt;/math&gt; respectively and say that the person who receives the correct meal is the first person. We will solve for this case and then multiply by &lt;math&gt;9&lt;/math&gt; to account for the &lt;math&gt;9&lt;/math&gt; different ways in which the person to receive the correct meal could be picked. Note, this implies that the dishes are indistinguishable, though the people are. For example, two people who order chicken are separate, though if they receive fish, there is only 1 way to order them.<br /> <br /> The problem we must solve is to distribute meals &lt;math&gt;BBCCCFFF&lt;/math&gt; to orders &lt;math&gt;BBCCCFFF&lt;/math&gt; with no matches. The two people who ordered &lt;math&gt;B&lt;/math&gt;'s can either both get &lt;math&gt;C&lt;/math&gt;'s, both get &lt;math&gt;F&lt;/math&gt;'s, or get one &lt;math&gt;C&lt;/math&gt; and one &lt;math&gt;F.&lt;/math&gt; We proceed with casework.<br /> <br /> &lt;UL&gt;<br /> &lt;LI&gt; If the two &lt;math&gt;B&lt;/math&gt; people both get &lt;math&gt;C&lt;/math&gt;'s, then the three &lt;math&gt;F&lt;/math&gt; meals left to distribute must all go to the &lt;math&gt;C&lt;/math&gt; people. The &lt;math&gt;F&lt;/math&gt; people then get &lt;math&gt;BBC&lt;/math&gt; in some order, which gives three possibilities. &lt;/LI&gt;<br /> <br /> &lt;LI&gt; If the two &lt;math&gt;B&lt;/math&gt; people both get &lt;math&gt;F&lt;/math&gt;'s, the situation is identical to the above and three possibilities arise. &lt;/LI&gt;<br /> <br /> &lt;LI&gt; If the two &lt;math&gt;B&lt;/math&gt; people get &lt;math&gt;CF&lt;/math&gt; in some order, then the &lt;math&gt;C&lt;/math&gt; people must get &lt;math&gt;FFB&lt;/math&gt; and the &lt;math&gt;F&lt;/math&gt; people must get &lt;math&gt;CCB.&lt;/math&gt; This gives &lt;math&gt;2 \cdot 3 \cdot 3 = 18&lt;/math&gt; possibilities. &lt;/LI&gt;<br /> &lt;/UL&gt;<br /> <br /> Summing across the cases we see there are &lt;math&gt;24&lt;/math&gt; possibilities, so the answer is &lt;math&gt;9 \cdot 24 = \boxed{216.}&lt;/math&gt;<br /> <br /> == See also ==<br /> {{AIME box|year=2012|n=I|num-b=2|num-a=4}}</div> Hakkapeliitta https://artofproblemsolving.com/wiki/index.php?title=2009_AMC_12A_Problems/Problem_16&diff=47819 2009 AMC 12A Problems/Problem 16 2012-08-05T17:59:15Z <p>Hakkapeliitta: </p> <hr /> <div>== Problem ==<br /> A circle with center &lt;math&gt;C&lt;/math&gt; is tangent to the positive &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;y&lt;/math&gt;-axes and externally tangent to the circle centered at &lt;math&gt;(3,0)&lt;/math&gt; with radius &lt;math&gt;1&lt;/math&gt;. What is the sum of all possible radii of the circle with center &lt;math&gt;C&lt;/math&gt;?<br /> <br /> &lt;math&gt;\textbf{(A)}\ 3 \qquad \textbf{(B)}\ 4 \qquad \textbf{(C)}\ 6 \qquad \textbf{(D)}\ 8 \qquad \textbf{(E)}\ 9&lt;/math&gt;<br /> <br /> == Solution ==<br /> <br /> Let &lt;math&gt;r&lt;/math&gt; be the radius of our circle. For it to be tangent to the positive &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;y&lt;/math&gt; axes, we must have &lt;math&gt;C=(r,r)&lt;/math&gt;. For the circle to be externally tangent to the circle centered at &lt;math&gt;(3,0)&lt;/math&gt; with radius &lt;math&gt;1&lt;/math&gt;, the distance between &lt;math&gt;C&lt;/math&gt; and &lt;math&gt;(3,0)&lt;/math&gt; must be exactly &lt;math&gt;r+1&lt;/math&gt;.<br /> <br /> By the [[Pythagorean theorem]] the distance between &lt;math&gt;(r,r)&lt;/math&gt; and &lt;math&gt;(3,0)&lt;/math&gt; is &lt;math&gt;\sqrt{ (r-3)^2 + r^2 }&lt;/math&gt;, hence we get the equation &lt;math&gt;(r-3)^2 + r^2 = (r+1)^2&lt;/math&gt;.<br /> <br /> Simplifying, we obtain &lt;math&gt;r^2 - 8r + 8 = 0&lt;/math&gt;. By [[Vieta's formulas]] the sum of the two roots of this equation is &lt;math&gt;\boxed{8}&lt;/math&gt;.<br /> <br /> (We should actually solve for &lt;math&gt;r&lt;/math&gt; to verify that there are two distinct positive roots. In this case we get &lt;math&gt;r=4\pm 2\sqrt 2&lt;/math&gt;. This is generally a good rule of thumb, but is not necessary as all of the available answers are integers, and the equation obviously doesn't factor as integers.)<br /> <br /> &lt;asy&gt;<br /> unitsize(0.5cm);<br /> defaultpen(0.8);<br /> filldraw( Circle( (3,0), 1 ), lightgray, black );<br /> draw( (0,0) -- (15,0), Arrow );<br /> draw( (0,0) -- (0,15), Arrow );<br /> draw( (0,0) -- (15,15), dashed );<br /> real r1 = 4 - 2*sqrt(2), r2 = 4 + 2*sqrt(2);<br /> pair S1=(r1,r1), S2=(r2,r2);<br /> dot(S1); dot(S2); dot((3,0));<br /> draw( Circle(S1,r1) );<br /> draw( Circle(S2,r2) );<br /> &lt;/asy&gt;<br /> <br /> == See Also ==<br /> <br /> {{AMC12 box|year=2009|ab=A|num-b=15|num-a=17}}</div> Hakkapeliitta https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_I_Problems/Problem_7&diff=47777 2011 AIME I Problems/Problem 7 2012-08-01T22:41:42Z <p>Hakkapeliitta: /* Solution 2 */</p> <hr /> <div>== Problem 7 ==<br /> Find the number of positive integers &lt;math&gt;m&lt;/math&gt; for which there exist nonnegative integers &lt;math&gt;x_0&lt;/math&gt;, &lt;math&gt;x_1&lt;/math&gt; , &lt;math&gt;\dots&lt;/math&gt; , &lt;math&gt;x_{2011}&lt;/math&gt; such that<br /> &lt;cmath&gt;m^{x_0} = \sum_{k = 1}^{2011} m^{x_k}.&lt;/cmath&gt;<br /> <br /> ==Solution==<br /> Let &lt;math&gt;P(m) = m^{x_0} - m^{x_1} -m^{x_2} - .... - m^{x_{2011}}&lt;/math&gt;. The problem then becomes finding the number of positive integer roots &lt;math&gt;m&lt;/math&gt; for which &lt;math&gt;P(m) = 0&lt;/math&gt; and &lt;math&gt;x_0, x_1, ..., x_{2011}&lt;/math&gt; are nonnegative integers. We plug in &lt;math&gt;m = 1&lt;/math&gt; and see that &lt;math&gt;P(1) = 1 - 1 - 1... -1 = 1-2011 = -2010&lt;/math&gt;. Now, we can say that &lt;math&gt;P(m) = (m-1)Q(m) - 2010&lt;/math&gt; for some polynomial &lt;math&gt;Q(m)&lt;/math&gt; with integer coefficients. Then if &lt;math&gt;P(m) = 0&lt;/math&gt;, &lt;math&gt;(m-1)Q(m) = 2010&lt;/math&gt;. Thus, if &lt;math&gt;P(m) = 0&lt;/math&gt;, then &lt;math&gt;m-1 | 2010&lt;/math&gt; .<br /> Now, we need to show that for all &lt;math&gt;m-1 | 2010&lt;/math&gt;, &lt;math&gt; m^{x_{0}}=\sum_{k = 1}^{2011}m^{x_{k}}. &lt;/math&gt;. We try with the first few &lt;math&gt;m&lt;/math&gt; that satisfy this.<br /> For &lt;math&gt;m = 2&lt;/math&gt;, we see we can satisfy this if &lt;math&gt;x_0 = 2010&lt;/math&gt;, &lt;math&gt;x_1 = 2009&lt;/math&gt;, &lt;math&gt;x_2 = 2008&lt;/math&gt;, &lt;math&gt;\cdots&lt;/math&gt; , &lt;math&gt;x_{2008} = 2&lt;/math&gt;, &lt;math&gt;x_{2009} = 1&lt;/math&gt;, &lt;math&gt; x_{2010} = 0&lt;/math&gt;, &lt;math&gt;x_{2011} = 0&lt;/math&gt;, because &lt;math&gt;2^{2009} + 2^{2008} + \cdots + 2^1 + 2^0 +2^ 0 = 2^{2009} + 2^{2008} + \cdots + 2^1 + 2^1 = \cdots&lt;/math&gt; (based on the idea &lt;math&gt;2^n + 2^n = 2^{n+1}&lt;/math&gt;, leading to a chain of substitutions of this kind) &lt;math&gt;= 2^{2009} + 2^{2008} + 2^{2008} = 2^{2009} + 2^{2009} = '''2^{2010}'''&lt;/math&gt;. Thus &lt;math&gt;2&lt;/math&gt; is a possible value of &lt;math&gt;m&lt;/math&gt;. For other values, for example &lt;math&gt;m = 3&lt;/math&gt;, we can use the same strategy, with &lt;math&gt;x_{2011} = x_{2010} = x_{2009} = 0&lt;/math&gt;, &lt;math&gt;x_{2008} = x_{2007} = 1&lt;/math&gt;, &lt;math&gt;x_{2006} = x_{2005} = 2&lt;/math&gt;, &lt;math&gt;\cdots&lt;/math&gt;, &lt;math&gt;x_2 = x_1 = 1004&lt;/math&gt; and &lt;math&gt;x_0 = 1005&lt;/math&gt;, because <br /> &lt;math&gt;3^0 + 3^0 + 3^0 +3^1+3^1+3^2+3^2+\cdots+3^{1004} +3^{1004} = 3^1+3^1+3^1+3^2+3^2+\cdots+3^{1004} +3^{1004} = 3^2+3^2+3^2+\cdots+3^{1004} +3^{1004} = \cdots&lt;/math&gt;<br /> &lt;math&gt;=3^{1004} +3^{1004}+3^{1004} = '''3^{1005}'''&lt;/math&gt;.<br /> It's clearly seen we can use the same strategy for all &lt;math&gt;m-1 |2010&lt;/math&gt;. We count all positive &lt;math&gt;m&lt;/math&gt; satisfying &lt;math&gt;m-1 |2010&lt;/math&gt;, and see there are &lt;math&gt;\boxed{016}&lt;/math&gt;<br /> <br /> ==Solution 2==<br /> One notices that &lt;math&gt;m-1 \mid 2010&lt;/math&gt; if and only if there exist non-negative integers &lt;math&gt;x_0,x_1,\ldots,x_{2011}&lt;/math&gt; such that &lt;math&gt;m^{x_0} = \sum_{k=1}^{2011}m^{x_k}&lt;/math&gt;.<br /> <br /> To prove the forward case, we proceed by directly finding &lt;math&gt;x_0,x_1,\ldots,x_{2011}&lt;/math&gt;. Suppose &lt;math&gt;m&lt;/math&gt; is an integer such that &lt;math&gt;m^{x_0} = \sum_{k=1}^{2011}m^{x_k}&lt;/math&gt;. We will count how many &lt;math&gt;x_k = 0&lt;/math&gt;, how many &lt;math&gt;x_k = 1&lt;/math&gt;, etc. Suppose the number of &lt;math&gt;x_k = 0&lt;/math&gt; is non-zero. Then, there must be at least &lt;math&gt;m&lt;/math&gt; such &lt;math&gt;x_k&lt;/math&gt; since &lt;math&gt;m&lt;/math&gt; divides all the remaining terms, so &lt;math&gt;m&lt;/math&gt; must also divide the sum of all the &lt;math&gt;m^0&lt;/math&gt; terms. Thus, if we let &lt;math&gt;x_k = 0&lt;/math&gt; for &lt;math&gt;k = 1,2,\ldots,m&lt;/math&gt;, we have,<br /> &lt;cmath&gt;m^{x_0} = m + \sum_{k=m+1}^{2011}m^{x_k}.&lt;/cmath&gt;<br /> Well clearly, &lt;math&gt;m^{x_0}&lt;/math&gt; is greater than &lt;math&gt;m&lt;/math&gt;, so &lt;math&gt;m^2 \mid m^{x_0}&lt;/math&gt;. &lt;math&gt;m^2&lt;/math&gt; will also divide every term, &lt;math&gt;m^{x_k}&lt;/math&gt;, where &lt;math&gt;x_k \geq 2&lt;/math&gt;. So, all the terms, &lt;math&gt;m^{x_k}&lt;/math&gt;, where &lt;math&gt;x_k &lt; 2&lt;/math&gt; must sum to a multiple of &lt;math&gt;m^2&lt;/math&gt;. If there are exactly &lt;math&gt;m&lt;/math&gt; terms where &lt;math&gt;x_k = 0&lt;/math&gt;, then we must have at least &lt;math&gt;m-1&lt;/math&gt; terms where &lt;math&gt;x_k = 1&lt;/math&gt;. Suppose there are exactly &lt;math&gt;m-1&lt;/math&gt; such terms and &lt;math&gt;x_k = 1&lt;/math&gt; for &lt;math&gt;k = m+1,m+2,2m-1&lt;/math&gt;. Now, we have,<br /> &lt;cmath&gt;m^{x_0} = m^2 + \sum_{k=2m}^{2011}m^{x_k}.&lt;/cmath&gt;<br /> One can repeat this process for successive powers of &lt;math&gt;m&lt;/math&gt; until the number of terms reaches 2011. Since there are &lt;math&gt;m + j(m-1)&lt;/math&gt; terms after the &lt;math&gt;j&lt;/math&gt;th power, we will only hit exactly 2011 terms if &lt;math&gt;m-1&lt;/math&gt; is a factor of 2010. To see this, <br /> &lt;cmath&gt;m+j(m-1) = 2011 \Rightarrow m-1+j(m-1) &amp;= 2010 \Rightarrow (m-1)(j+1) = 2010.&lt;/cmath&gt;<br /> Thus, when &lt;math&gt;j = 2010/(m-1) - 1&lt;/math&gt; (which is an integer since &lt;math&gt;m-1 \mid 2010&lt;/math&gt; by assumption, there are exactly 2011 terms. To see that these terms sum to a power of &lt;math&gt;m&lt;/math&gt;, we realize that the sum is a geometric series:<br /> &lt;cmath&gt;1 + (m-1) + (m-1)m+(m-1)m^2 + \cdots + (m-1)m^j &amp;= 1+(m-1)\frac{m^{j+1}-1}{m-1} = m^{j+1}.&lt;/cmath&gt;<br /> Thus, we have found a solution for the case &lt;math&gt;m-1 \mid 2010&lt;/math&gt;.<br /> <br /> Now, for the reverse case, we use the formula &lt;cmath&gt;x^k-1 = (x-1)(x^{k-1}+x^{k-2}+\cdots+1).&lt;/cmath&gt; Suppose &lt;math&gt;m^{x_0} = \sum_{k=1}^{2011}m^{x^k}&lt;/math&gt; has a solution. Subtract 2011 from both sides to get &lt;cmath&gt;m^{x_0}-1-2010 = \sum_{k=1}^{2011}(m^{x^k}-1).&lt;/cmath&gt; Now apply the formula to get &lt;cmath&gt;(m-1)a_0-2010 = \sum_{k=1}^{2011}[(m-1)a_k],&lt;/cmath&gt; where &lt;math&gt;a_k&lt;/math&gt; are some integers. Rearranging this equation, we find &lt;cmath&gt;(m-1)A = 2010,&lt;/cmath&gt; where &lt;math&gt;A = a_0 - \sum_{k=1}^{2011}a_k&lt;/math&gt;. Thus, if &lt;math&gt;m&lt;/math&gt; is a solution, then &lt;math&gt;m-1 \mid 2010&lt;/math&gt;. <br /> <br /> So, there is one positive integer solution corresponding to each factor of 2010. Since &lt;math&gt;2010 = 2\cdot 3\cdot 5\cdot 67&lt;/math&gt;, the number of solutions is &lt;math&gt;2^4 = \boxed{016}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=2011|n=I|num-b=6|num-a=8}}<br /> * [[AIME Problems and Solutions]]<br /> * [[American Invitational Mathematics Examination]]<br /> * [[Mathematics competition resources]]</div> Hakkapeliitta https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_I_Problems/Problem_7&diff=47776 2011 AIME I Problems/Problem 7 2012-08-01T22:41:14Z <p>Hakkapeliitta: /* Solution */</p> <hr /> <div>== Problem 7 ==<br /> Find the number of positive integers &lt;math&gt;m&lt;/math&gt; for which there exist nonnegative integers &lt;math&gt;x_0&lt;/math&gt;, &lt;math&gt;x_1&lt;/math&gt; , &lt;math&gt;\dots&lt;/math&gt; , &lt;math&gt;x_{2011}&lt;/math&gt; such that<br /> &lt;cmath&gt;m^{x_0} = \sum_{k = 1}^{2011} m^{x_k}.&lt;/cmath&gt;<br /> <br /> ==Solution==<br /> Let &lt;math&gt;P(m) = m^{x_0} - m^{x_1} -m^{x_2} - .... - m^{x_{2011}}&lt;/math&gt;. The problem then becomes finding the number of positive integer roots &lt;math&gt;m&lt;/math&gt; for which &lt;math&gt;P(m) = 0&lt;/math&gt; and &lt;math&gt;x_0, x_1, ..., x_{2011}&lt;/math&gt; are nonnegative integers. We plug in &lt;math&gt;m = 1&lt;/math&gt; and see that &lt;math&gt;P(1) = 1 - 1 - 1... -1 = 1-2011 = -2010&lt;/math&gt;. Now, we can say that &lt;math&gt;P(m) = (m-1)Q(m) - 2010&lt;/math&gt; for some polynomial &lt;math&gt;Q(m)&lt;/math&gt; with integer coefficients. Then if &lt;math&gt;P(m) = 0&lt;/math&gt;, &lt;math&gt;(m-1)Q(m) = 2010&lt;/math&gt;. Thus, if &lt;math&gt;P(m) = 0&lt;/math&gt;, then &lt;math&gt;m-1 | 2010&lt;/math&gt; .<br /> Now, we need to show that for all &lt;math&gt;m-1 | 2010&lt;/math&gt;, &lt;math&gt; m^{x_{0}}=\sum_{k = 1}^{2011}m^{x_{k}}. &lt;/math&gt;. We try with the first few &lt;math&gt;m&lt;/math&gt; that satisfy this.<br /> For &lt;math&gt;m = 2&lt;/math&gt;, we see we can satisfy this if &lt;math&gt;x_0 = 2010&lt;/math&gt;, &lt;math&gt;x_1 = 2009&lt;/math&gt;, &lt;math&gt;x_2 = 2008&lt;/math&gt;, &lt;math&gt;\cdots&lt;/math&gt; , &lt;math&gt;x_{2008} = 2&lt;/math&gt;, &lt;math&gt;x_{2009} = 1&lt;/math&gt;, &lt;math&gt; x_{2010} = 0&lt;/math&gt;, &lt;math&gt;x_{2011} = 0&lt;/math&gt;, because &lt;math&gt;2^{2009} + 2^{2008} + \cdots + 2^1 + 2^0 +2^ 0 = 2^{2009} + 2^{2008} + \cdots + 2^1 + 2^1 = \cdots&lt;/math&gt; (based on the idea &lt;math&gt;2^n + 2^n = 2^{n+1}&lt;/math&gt;, leading to a chain of substitutions of this kind) &lt;math&gt;= 2^{2009} + 2^{2008} + 2^{2008} = 2^{2009} + 2^{2009} = '''2^{2010}'''&lt;/math&gt;. Thus &lt;math&gt;2&lt;/math&gt; is a possible value of &lt;math&gt;m&lt;/math&gt;. For other values, for example &lt;math&gt;m = 3&lt;/math&gt;, we can use the same strategy, with &lt;math&gt;x_{2011} = x_{2010} = x_{2009} = 0&lt;/math&gt;, &lt;math&gt;x_{2008} = x_{2007} = 1&lt;/math&gt;, &lt;math&gt;x_{2006} = x_{2005} = 2&lt;/math&gt;, &lt;math&gt;\cdots&lt;/math&gt;, &lt;math&gt;x_2 = x_1 = 1004&lt;/math&gt; and &lt;math&gt;x_0 = 1005&lt;/math&gt;, because <br /> &lt;math&gt;3^0 + 3^0 + 3^0 +3^1+3^1+3^2+3^2+\cdots+3^{1004} +3^{1004} = 3^1+3^1+3^1+3^2+3^2+\cdots+3^{1004} +3^{1004} = 3^2+3^2+3^2+\cdots+3^{1004} +3^{1004} = \cdots&lt;/math&gt;<br /> &lt;math&gt;=3^{1004} +3^{1004}+3^{1004} = '''3^{1005}'''&lt;/math&gt;.<br /> It's clearly seen we can use the same strategy for all &lt;math&gt;m-1 |2010&lt;/math&gt;. We count all positive &lt;math&gt;m&lt;/math&gt; satisfying &lt;math&gt;m-1 |2010&lt;/math&gt;, and see there are &lt;math&gt;\boxed{016}&lt;/math&gt;<br /> <br /> ==Solution 2==<br /> One notices that &lt;math&gt;m-1 \mid 2010&lt;/math&gt; if and only if there exist non-negative integers &lt;math&gt;x_0,x_1,\ldots,x_{2011}&lt;/math&gt; such that &lt;math&gt;m^{x_0} = \sum_{k=1}^{2011}m^{x_k}&lt;/math&gt;.<br /> <br /> To prove the forward case, we proceed by directly finding &lt;math&gt;x_0,x_1,\ldots,x_{2011}&lt;/math&gt;. Suppose &lt;math&gt;m&lt;/math&gt; is an integer such that &lt;math&gt;m^{x_0} = \sum_{k=1}^{2011}m^{x_k}&lt;/math&gt;. We will count how many &lt;math&gt;x_k = 0&lt;/math&gt;, how many &lt;math&gt;x_k = 1&lt;/math&gt;, etc. Suppose the number of &lt;math&gt;x_k = 0&lt;/math&gt; is non-zero. Then, there must be at least &lt;math&gt;m&lt;/math&gt; such &lt;math&gt;x_k&lt;/math&gt; since &lt;math&gt;m&lt;/math&gt; divides all the remaining terms, so &lt;math&gt;m&lt;/math&gt; must also divide the sum of all the &lt;math&gt;m^0&lt;/math&gt; terms. Thus, if we let &lt;math&gt;x_k = 0&lt;/math&gt; for &lt;math&gt;k = 1,2,\ldots,m&lt;/math&gt;, we have,<br /> &lt;cmath&gt;m^{x_0} = m + \sum_{k=m+1}^{2011}m^{x_k}.&lt;/cmath&gt;<br /> Well clearly, &lt;math&gt;m^{x_0}&lt;/math&gt; is greater than &lt;math&gt;m&lt;/math&gt;, so &lt;math&gt;m^2 \mid m^{x_0}&lt;/math&gt;. &lt;math&gt;m^2&lt;/math&gt; will also divide every term, &lt;math&gt;m^{x_k}&lt;/math&gt;, where &lt;math&gt;x_k \geq 2&lt;/math&gt;. So, all the terms, &lt;math&gt;m^{x_k}&lt;/math&gt;, where &lt;math&gt;x_k &lt; 2&lt;/math&gt; must sum to a multiple of &lt;math&gt;m^2&lt;/math&gt;. If there are exactly &lt;math&gt;m&lt;/math&gt; terms where &lt;math&gt;x_k = 0&lt;/math&gt;, then we must have at least &lt;math&gt;m-1&lt;/math&gt; terms where &lt;math&gt;x_k = 1&lt;/math&gt;. Suppose there are exactly &lt;math&gt;m-1&lt;/math&gt; such terms and &lt;math&gt;x_k = 1&lt;/math&gt; for &lt;math&gt;k = m+1,m+2,2m-1&lt;/math&gt;. Now, we have,<br /> &lt;cmath&gt;m^{x_0} = m^2 + \sum_{k=2m}^{2011}m^{x_k}.&lt;/cmath&gt;<br /> One can repeat this process for successive powers of &lt;math&gt;m&lt;/math&gt; until the number of terms reaches 2011. Since there are &lt;math&gt;m + j(m-1)&lt;/math&gt; terms after the &lt;math&gt;j&lt;/math&gt;th power, we will only hit exactly 2011 terms if &lt;math&gt;m-1&lt;/math&gt; is a factor of 2010. To see this, <br /> &lt;cmath&gt;m+j(m-1) = 2011 \Rightarrow m-1+j(m-1) &amp;= 2010 \Rightarrow (m-1)(j+1) = 2010.&lt;/cmath&gt;<br /> Thus, when &lt;math&gt;j = 2010/(m-1) - 1&lt;/math&gt; (which is an integer since &lt;math&gt;m-1 \mid 2010&lt;/math&gt; by assumption, there are exactly 2011 terms. To see that these terms sum to a power of &lt;math&gt;m&lt;/math&gt;, we realize that the sum is a geometric series:<br /> &lt;cmath&gt;1 + (m-1) + (m-1)m+(m-1)m^2 + \cdots + (m-1)m^j &amp;= 1+(m-1)\frac{m^{j+1}-1}{m-1} = m^{j+1}.&lt;/cmath&gt;<br /> Thus, we have found a solution for the case &lt;math&gt;m-1 \mid 2010&lt;/math&gt;.<br /> <br /> Now, for the reverse case, we use the formula &lt;cmath&gt;x^k-1 = (x-1)(x^{k-1}+x^{k-2}+\cdots+1).&lt;/cmath&gt; Suppose &lt;math&gt;m^{x_0} = \sum_{k=1}^{2011}m^{x^k}&lt;/math&gt; has a solution. Subtract 2011 from both sides to get &lt;cmath&gt;m^{x_0}-1-2010 = \sum_{k=1}^{2011}(m^{x^k}-1).&lt;/cmath&gt; Now apply the formula to get &lt;cmath&gt;(m-1)a_0-2010 = \sum_{k=1}^{2011}[(m-1)a_k],&lt;/cmath&gt; where &lt;math&gt;a_k&lt;/math&gt; are some integers. Rearranging this equation, we find &lt;cmath&gt;(m-1)A = 2010,&lt;/cmath&gt; where &lt;math&gt;A = a_0 - \sum_{k=1}^{2011}a_k&lt;/math&gt;. Thus, if &lt;math&gt;m&lt;/math&gt; is a solution, then &lt;math&gt;m-1 \mid 2010&lt;/math&gt;. <br /> <br /> So, there is one positive integer solution corresponding to each factor of 2010. Since &lt;math&gt;2010 = 2\cdot 3\cdot 5\cdot 67&lt;/math&gt;, the number of solutions is &lt;math&gt;2^4 = \boxed{16}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=2011|n=I|num-b=6|num-a=8}}<br /> * [[AIME Problems and Solutions]]<br /> * [[American Invitational Mathematics Examination]]<br /> * [[Mathematics competition resources]]</div> Hakkapeliitta https://artofproblemsolving.com/wiki/index.php?title=Polynomial&diff=47723 Polynomial 2012-07-23T05:52:37Z <p>Hakkapeliitta: /* Intermediate Topics */</p> <hr /> <div>A '''polynomial''' is a [[function]] in one or more [[variable]]s that consists of a sum of variables raised to [[nonnegative]], [[integer|integral]] powers and multiplied by [[coefficient]]s (usually integral, [[rational]], [[real]] or [[complex]], but in [[abstract algebra]] often coming from an arbitrary [[field]]).<br /> <br /> For example, these are polynomials:<br /> * &lt;math&gt;4x^2 + 6x - 9&lt;/math&gt;, in the variable &lt;math&gt;x&lt;/math&gt;<br /> * &lt;math&gt;x^3 + 3x^2y + 3xy^2 + y^3&lt;/math&gt;, in the variables &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;y&lt;/math&gt;<br /> * &lt;math&gt;5x^4 - 2x^2 + 9&lt;/math&gt;, in the variable &lt;math&gt;x&lt;/math&gt;<br /> * &lt;math&gt;\sin^2{x} + 5&lt;/math&gt;, in the variable &lt;math&gt;\sin x&lt;/math&gt;<br /> <br /> However, <br /> * &lt;math&gt;\sin^2{x} + 5&lt;/math&gt;<br /> * &lt;math&gt;\frac{4x+3}{2x-9}&lt;/math&gt;<br /> are functions, but ''not'' polynomials, in the variable &lt;math&gt;x&lt;/math&gt;<br /> <br /> ==Introductory Topics==<br /> ===A More Precise Definition===<br /> <br /> A polynomial in one variable is a function &lt;math&gt;P(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_2x^2 + a_1x + a_0&lt;/math&gt;. Here, &lt;math&gt;a_i&lt;/math&gt; is the &lt;math&gt;i&lt;/math&gt;th coefficient and &lt;math&gt;a_n \neq 0&lt;/math&gt;. Often, the leading coefficient of a polynomial will be equal to 1. In this case, we say we have a ''monic'' polynomial.<br /> <br /> === The Degree of a Polynomial ===<br /> <br /> The simplest piece of information that one can have about a polynomial of one variable is the highest power of the variable which appears in the polynomial. This number is known as the ''degree'' of the polynomial and is written &lt;math&gt;\deg(P)&lt;/math&gt;. For instance, &lt;math&gt;\deg(x^2 + 3x + 4) = 2&lt;/math&gt; and &lt;math&gt;\deg(x^5 - 1) = 5&lt;/math&gt;. When a polynomial is written in the form &lt;math&gt;P(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_2x^2 + a_1x + a_0&lt;/math&gt; with &lt;math&gt;a_n \neq 0&lt;/math&gt;, the integer &lt;math&gt;n&lt;/math&gt; is the degree of the polynomial. <br /> <br /> The degree, together with the coefficient of the largest term, provides a surprisingly large amount of information about the polynomial: how it behaves in the [[limit]] as the variable grows very large (either in the positive or negative direction) and how many roots it has.<br /> <br /> ===Finding Roots of Polynomials===<br /> <br /> ====What is a root?====<br /> <br /> A [[root]] is a value for a variable that will make the polynomial equal zero. For an example, 2 is a root of &lt;math&gt;x^2 - 4&lt;/math&gt; because &lt;math&gt;2^2 - 4 = 0&lt;/math&gt;. For some polynomials, you can easily set the polynomial equal to zero and solve or otherwise find roots, but in some cases it is much more complicated.<br /> <br /> ====The Fundamental Theorem of Algebra====<br /> <br /> The [[Fundamental Theorem of Algebra]] states that any polynomial with [[complex number|complex]] coefficients can be written as<br /> <br /> &lt;math&gt;P(x) = k(x-x_1)(x-x_2)\cdots(x-x_n)&lt;/math&gt; where &lt;math&gt;k&lt;/math&gt; is a constant, the &lt;math&gt;x_i&lt;/math&gt; are (not necessarily distinct) complex numbers and &lt;math&gt;n&lt;/math&gt; is the degree of the polynomial in exactly one way (not counting re-arrangements of the terms of the product). It's very easy to find the roots of a polynomial in this form because the roots will be &lt;math&gt;x_1,x_2,...,x_n&lt;/math&gt;. This also tells us that the degree of a given polynomial is at least as large as the number of distinct roots of that polynomial. In quadratics roots are more complex and can simply be the sqrt of a prime number.<br /> <br /> ====Factoring====<br /> <br /> Different methods of [[factoring]] can help find roots of polynomials. Consider this polynomial:<br /> <br /> &lt;math&gt;x^3 + 3x^2 - 4x - 12 = 0&lt;/math&gt;<br /> <br /> This polynomial easily factors to:<br /> <br /> &lt;math&gt;(x+3)(x^2-4) = 0&lt;/math&gt;<br /> <br /> &lt;math&gt;(x+3)(x-2)(x+2) = 0&lt;/math&gt;<br /> <br /> Now, the roots of the polynomial are clearly -3, -2, and 2.<br /> <br /> ====The Rational Root Theorem====<br /> We are often interested in finding the roots of polynomials with integral coefficients. Consider such a polynomial &lt;math&gt;P(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_2x^2 + a_1x + a_0&lt;/math&gt;. The [[Rational Root Theorem]] states that if &lt;math&gt;P(x)&lt;/math&gt; has a rational root &lt;math&gt;\pm\frac{p}{q}&lt;/math&gt; and this [[fraction]] is fully reduced, then &lt;math&gt;p&lt;/math&gt; is a [[divisor]] of &lt;math&gt;a_0&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; is a divisor of &lt;math&gt;a_n&lt;/math&gt;. This is convenient because it means we must check only a small number of cases to find all rational roots of many polynomials. It is also especially convenient when dealing with monic polynomials.<br /> <br /> ====Descartes' Law of Signs====<br /> By the Fundamental Theorem of Algebra, the maximum number of distinct factors (not all necessarily real) of a polynomial of degree n is n. This tells us nothing about whether or not these roots are positive or negative. Decartes' Rule of Signs says that for a polynomial &lt;math&gt;P(x)&lt;/math&gt;, the number of positive roots to the equation is equal to the number of sign changes in the coefficients of the polynomial, or is less than that number by a multiple of 2. The number of negative roots to the equation is the number of sign changes in the coefficients of &lt;math&gt;P(-x)&lt;/math&gt;, or is less than that by a multiple of 2.<br /> <br /> ===Binomial Theorem===<br /> The [[Binomial Theorem]] can be very useful for factoring and expanding polynomials.<br /> <br /> <br /> ===Special Values===<br /> Given the coefficients of a polynomial, it is very easy to figure out the value of the polynomial on different inputs. In some cases, the reverse is also true. The most obvious example is also the simplest: for any polynomial &lt;math&gt;P(x) = a_nx^n + \ldots + a_1 x + a_0&lt;/math&gt;, &lt;math&gt;P(0) = a_0&lt;/math&gt; so the value of a polynomial at 0 is also the constant coefficient.<br /> <br /> Similarly, &lt;math&gt;P(1) = a_n + a_{n - 1} + \ldots + a_1 + a_0&lt;/math&gt;, so the value at 1 is equal to the sum of the coefficients.<br /> <br /> In fact, the value at any point gives us a linear equation in the coefficients of the polynomial. We can solve this system and find a unique solution when we have as many equations as we do coefficients. Thus, given the value of a polynomial &lt;math&gt;P&lt;/math&gt; and &lt;math&gt;\deg(P) + 1&lt;/math&gt; different points, we can always find the coefficients of the polynomial.<br /> <br /> ==Intermediate Topics==<br /> *[[Complex numbers]]<br /> *[[Fundamental Theorem of Algebra]]<br /> *[[Roots of unity]]<br /> <br /> ==Olympiad Topics==<br /> <br /> * [[Vieta's formulas]]<br /> * [[Newton's identities]]<br /> * [[Newton sums]]<br /> <br /> ==Other Resources==<br /> An extensive coverage of this topic is given in [http://www.artofproblemsolving.com/Resources/Papers/PolynomialsAK.pdf A Few Elementary Properties of Polynomials] by Adeel Khan.<br /> <br /> <br /> == See also ==<br /> * [[Algebra]]<br /> <br /> [[Category:Definition]]<br /> [[Category:Elementary algebra]]</div> Hakkapeliitta https://artofproblemsolving.com/wiki/index.php?title=USAMO_historical_results&diff=47720 USAMO historical results 2012-07-22T17:45:40Z <p>Hakkapeliitta: /* USAMO Winners */</p> <hr /> <div>This is the '''USAMO historical results''' page. &lt;!-- Post results here so the [[USAMO]] page does not become cluttered. --&gt;<br /> <br /> ==USAMO Perfect Scorers==<br /> <br /> Since 1996, a perfect score on the [[USAMO]] has been 42 points for 6 problems. Prior to 1996 a perfect score was 100 points across 5 problems.<br /> <br /> *2008: None<br /> *2007: None<br /> *2006:<br /> **Brian Lawrence<br /> *2005: None<br /> *2004:<br /> **Tiankai Liu<br /> *2003:<br /> **Tiankai Liu<br /> **Po-Ru Loh<br /> *2002: <br /> **Daniel Kane<br /> **Ricky Liu<br /> **Tiankai Liu<br /> **Po-Ru Loh<br /> **Inna Zakharevich<br /> *1996:<br /> **Chris Chang<br /> *1992:<br /> **Kiran Kedlaya<br /> **Lenny Ng<br /> <br /> ==USAMO Winners==<br /> <br /> The top 12 scorers on the [[USAMO]] are currently designated as USAMO winners. In the past, this number was smaller.<br /> *2012:<br /> **Andre Arslan<br /> **Joshua Brakensiek<br /> **Calvin Deng<br /> **Xiaoyu He<br /> **Ravi Jagadeesan<br /> **Mitchell Lee<br /> **Alex Song<br /> **Thomas Swayze<br /> **Victor Wang<br /> **David Yang<br /> **Samuel Zbarsky<br /> **Alex Zhu<br /> *2011:<br /> **Wenyu Cao<br /> **Zijing Gao<br /> **Benjamin Gunby<br /> **Xiaoyu He<br /> **Ravi Jagadeesan<br /> **Spencer Kwon<br /> **Mitchell Lee<br /> **Ray Li<br /> **Evan O'Dorney<br /> **Mark Sellke<br /> **David Yang<br /> **Joy Zheng<br /> *2010:<br /> **Timothy Chu<br /> **Calvin Deng<br /> **Michael Druggan<br /> **Brian Hamrick<br /> **Travis Hance<br /> **Xiaoyu He<br /> **Mitchell Lee<br /> **In Sung Na<br /> **Evan O'Dorney<br /> **Toan Phan<br /> **Hunter Spink<br /> **Allen Yuan<br /> *2009:<br /> **John Berman<br /> **Sergei Bernstein<br /> **Wenyu Cao<br /> **Robin Cheng<br /> **Vlad Firoiu<br /> **Eric Larson<br /> **Delong Meng<br /> **Qinxuan Pan<br /> **Panupang Pasupat<br /> **Toan Phan<br /> **David Rush<br /> **David Yang<br /> *2008:<br /> **David Benjamin<br /> **TaoRan Chen<br /> **Paul Christiano<br /> **Sam Elder<br /> **Shaunak Kishore<br /> **Delong Meng<br /> **Evan O'Dorney<br /> **Qinxuan Pan<br /> **David Rolnick<br /> **Colin Sandon<br /> **Krishanu Sankar<br /> **Alex Zhai<br /> *2007:<br /> **Sergei Bernstein<br /> **Sherry Gong<br /> **Adam Hesterberg<br /> **Eric Larson<br /> **Brian Lawrence<br /> **Tedrick Leung<br /> **Haitao Mao<br /> **Delong Meng<br /> **Krishanu Sankar<br /> **Jacob Steinhardt<br /> **Arnav Tripathy<br /> **Alex Zhai<br /> *2006:<br /> **Brian Lawrence<br /> **Alex Zhai<br /> **Yufei Zhao<br /> **Peng Shi<br /> **Sherry Gong<br /> **Richard McCutchen<br /> **Yi Sun<br /> **Arnav Tripathy<br /> **Taehyeon (Ryan) Ko<br /> **Yi Han<br /> **Yakov Berchenko-Kogan<br /> **Tedrick Leung<br /> *2005:<br /> **Robert Cordwell<br /> **Zhou Fan<br /> **Sherry Gong<br /> **Rishi Gupta<br /> **Hyun Soo Kim<br /> **Brian Lawrence<br /> **Albert Ni<br /> **Natee Pitiwan<br /> **Eric Price<br /> **Peng Shi<br /> **Yi Sun<br /> **Yufei Zhao<br /> *2004:<br /> **Tiankai Liu<br /> **Jae Bae<br /> **Jongmin Baek<br /> **Oleg Golberg<br /> **Matt Ince<br /> **Janos Kramar<br /> **Alison Miller<br /> **Aaron Pixton<br /> **Brian Rice<br /> **Jacob Tsimerman<br /> **Ameya Velingker<br /> **Tony Zhang<br /> *1996:<br /> **Chris Chang<br /> **Alex Saltman<br /> **Josh Nichols-Barrer<br /> **Carl Bosley<br /> **Michael Korn<br /> **Carl Miller<br /> **Nathan Curtis<br /> **Daniel Stronger<br /> *1995:<br /> **Aleksander Khazanov<br /> **Jacob Lurie<br /> **Chris Chang<br /> **Jay Chyung<br /> **Andrei Gnepp<br /> **Josh Nichols-Barrer<br /> **Samit Dasgupta<br /> **Craig Helfgott<br /> *1994:<br /> **Jeremy Bem<br /> **Aleksander Khazanov<br /> **Jonathan Weinstein<br /> **Jacob Lurie<br /> **Noam Shazeer<br /> **Stephen Wang<br /> **Chris Chang<br /> **Jacob Rasmussen<br /> *1989:<br /> **Jordan Ellenberg<br /> **Andrew Kresh<br /> **Jonathan Higa<br /> **[[Richard Rusczyk]]<br /> **Jeff Vanderkam<br /> **[[Sam Vandervelde]]<br /> **David Carlton<br /> <br /> ==USAMO Honorable Mentions==<br /> <br /> Other students who finish (or tie to finish) in the top 24 of the [[USAMO]] receive Honorable Mention (often abbreviated HM).<br /> <br /> *2008:<br /> **John Berman<br /> **Sergei Bernstein<br /> **Gregory Gauthier<br /> **Brian Hamrick<br /> **Eric Larson<br /> **Gaku Liu<br /> **Jeffrey Manning<br /> **Palmer Mebane<br /> **Danny Shi<br /> **Jacob Steinhardt<br /> **Matthew Superdock<br /> **Nicholas Triantafillou<br /> *2007:<br /> **David Benjamin<br /> **Gregory Brockman<br /> **Yingyu Gao<br /> **Yan Li<br /> **Gaku Liu<br /> **Jeffrey Manning<br /> **Palmer Mebane<br /> **Evan O'Dorney<br /> **Alexander Remorov<br /> **Max Rosett<br /> **Qiaochu Yuan<br /> **Bohua Zhan<br /> *2006:<br /> **Joseph Chu<br /> **Zachary Abel<br /> **Zarathustra Brady<br /> **Peter Diao<br /> **Richar Peng<br /> **Adam Hesterberg<br /> **Bohua Zhan<br /> **Kevin Modzelewski<br /> **Daniel Poore<br /> **Lin Fei<br /> **Jason Trigg<br /> **Tony Liu<br /> **Viktoriya Krakovna<br /> *2005:<br /> **Zachary Abel<br /> **Charles Chen<br /> **Evan Dummit<br /> **Adam Hesterberg<br /> **Richard Ho<br /> **Alexander Marcus<br /> **Richard McCutchen<br /> **Thomas Mildorf<br /> **Charles Nathanson<br /> **Keenan Pepper<br /> **Timothy Pollio<br /> *2004:<br /> **Boris Alexeev<br /> **Joshua Batson<br /> **Thomas Belulovich<br /> **Rishi Gupta<br /> **Anders Kaseorg<br /> **Hyun Soo Kim<br /> **John Kim<br /> **Po Ling Loh<br /> **Sira Sriswasdi<br /> **Yi Sun<br /> **Elena Udovina<br /> **Yufei Zhao<br /> *1995<br /> ** Mathew Crawford<br /> *1993<br /> ** Mathew Crawford<br /> <br /> ==See also==<br /> *[http://www.unl.edu/amc/e-exams/e8-usamo/archiveusamo.html USAMO Archive]<br /> <br /> [[Category:Historical results]]</div> Hakkapeliitta https://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_25&diff=47663 2010 AMC 12B Problems/Problem 25 2012-07-19T03:36:54Z <p>Hakkapeliitta: /* Solution */</p> <hr /> <div>== Problem 25 ==<br /> For every integer &lt;math&gt;n\ge2&lt;/math&gt;, let &lt;math&gt;\text{pow}(n)&lt;/math&gt; be the largest power of the largest prime that divides &lt;math&gt;n&lt;/math&gt;. For example &lt;math&gt;\text{pow}(144)=\text{pow}(2^4\cdot3^2)=3^2&lt;/math&gt;. What is the largest integer &lt;math&gt;m&lt;/math&gt; such that &lt;math&gt;2010^m&lt;/math&gt; divides<br /> <br /> &lt;center&gt;<br /> &lt;math&gt;\prod_{n=2}^{5300}\text{pow}(n)&lt;/math&gt;?<br /> &lt;/center&gt;<br /> <br /> <br /> &lt;math&gt;\textbf{(A)}\ 74 \qquad \textbf{(B)}\ 75 \qquad \textbf{(C)}\ 76 \qquad \textbf{(D)}\ 77 \qquad \textbf{(E)}\ 78&lt;/math&gt;<br /> <br /> == Solution == <br /> Because 67 is the largest prime factor of 2010, it means that in the prime factorization of &lt;math&gt;\prod_{n=2}^{5300}\text{pow}(n)&lt;/math&gt;, there'll be &lt;math&gt;p_1 ^{e_1} \cdot p_2 ^{e_2} \cdot .... 67^x ...&lt;/math&gt; where &lt;math&gt;x&lt;/math&gt; is the desired value we are looking for. Thus, to find this answer, we need to look for the number of times 67 would be incorporated into the giant product. <br /> Any number of the form &lt;math&gt;x \cdot 67&lt;/math&gt; would fit this form. However, this number tops at &lt;math&gt;71 = x&lt;/math&gt; because 71 is a higher prime than 67. &lt;math&gt;67^2&lt;/math&gt; itself must be counted twice because it's counted twice as a squared number. Any non-prime number that's less than 79 (and greater than 71) can be counted, and this totals 5. We have &lt;math&gt;70&lt;/math&gt; numbers (as 71 isn't counted - 1 through 70), an additional &lt;math&gt;1&lt;/math&gt; (&lt;math&gt;67^2&lt;/math&gt;), and &lt;math&gt;6&lt;/math&gt; values just greater than &lt;math&gt;71&lt;/math&gt; but less than &lt;math&gt;79&lt;/math&gt; (72, 74, 75, 76, 77, and 78). Thus, &lt;math&gt;70 + 1 + 6 = \boxed{77} \Rightarrow \boxed{D}&lt;/math&gt;<br /> <br /> ==See Also==<br /> {{AMC12 box|ab=B|year=2010|after=Last Problem|num-b=24}}</div> Hakkapeliitta