https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=God+of+Math&feedformat=atom AoPS Wiki - User contributions [en] 2022-08-16T22:00:03Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2005_AIME_II_Problems/Problem_8&diff=32802 2005 AIME II Problems/Problem 8 2009-09-12T16:04:35Z <p>God of Math: /* Solution */</p> <hr /> <div>== Problem ==<br /> [[Circle]]s &lt;math&gt; C_1 &lt;/math&gt; and &lt;math&gt; C_2 &lt;/math&gt; are externally [[tangent]], and they are both internally tangent to circle &lt;math&gt; C_3. &lt;/math&gt; The radii of &lt;math&gt; C_1 &lt;/math&gt; and &lt;math&gt; C_2 &lt;/math&gt; are 4 and 10, respectively, and the [[center]]s of the three circles are all [[collinear]]. A [[chord]] of &lt;math&gt; C_3 &lt;/math&gt; is also a common external tangent of &lt;math&gt; C_1 &lt;/math&gt; and &lt;math&gt; C_2. &lt;/math&gt; Given that the length of the chord is &lt;math&gt; \frac{m\sqrt{n}}p &lt;/math&gt; where &lt;math&gt; m,n, &lt;/math&gt; and &lt;math&gt; p &lt;/math&gt; are positive integers, &lt;math&gt; m &lt;/math&gt; and &lt;math&gt; p &lt;/math&gt; are [[relatively prime]], and &lt;math&gt; n &lt;/math&gt; is not divisible by the square of any [[prime]], find &lt;math&gt; m+n+p. &lt;/math&gt;<br /> <br /> == Solution ==<br /> &lt;center&gt;&lt;asy&gt;<br /> pointpen = black; pathpen = black + linewidth(0.7); size(200);<br /> pair C1 = (-10,0), C2 = (4,0), C3 = (0,0), H = (-10-28/3,0), T = 58/7*expi(pi-acos(3/7)); <br /> path cir1 = CR(C1,4), cir2 = CR(C2,10), cir3 = CR(C3,14), t = H--T+2*(T-H);<br /> pair A = OP(cir3, t), B = IP(cir3, t), T1 = IP(cir1, t), T2 = IP(cir2, t);<br /> D(cir1); D(cir2); D(cir3); D((14,0)--(-14,0)); D(A--B); D((-14,0)--D(MP(&quot;H&quot;,H,W))--A,linewidth(0.7) + linetype(&quot;4 4&quot;));<br /> D(MP(&quot;O_1&quot;,C1)); D(MP(&quot;O_2&quot;,C2)); D(MP(&quot;O_3&quot;,C3)); D(MP(&quot;T&quot;,T,N)); D(MP(&quot;A&quot;,A,NW)); D(MP(&quot;B&quot;,B,NE)); D(C1--MP(&quot;T_1&quot;,T1,N)); D(C2--MP(&quot;T_2&quot;,T2,N)); D(C3--T); D(rightanglemark(C_3,T,H));<br /> &lt;/asy&gt;&lt;/center&gt;<br /> <br /> Let &lt;math&gt;O_1, O_2, O_3&lt;/math&gt; be the centers and &lt;math&gt;r_1 = 4, r_2 = 10,r_3 = 14&lt;/math&gt; the radii of the circles &lt;math&gt;C_1, C_2, C_3&lt;/math&gt;. Let &lt;math&gt;T_1, T_2&lt;/math&gt; be the points of tangency from the common external tangent of &lt;math&gt;C_1, C_2&lt;/math&gt;, respectively, and let the extension of &lt;math&gt;\overline{T_1T_2}&lt;/math&gt; intersect the extension of &lt;math&gt;\overline{O_1O_2}&lt;/math&gt; at a point &lt;math&gt;H&lt;/math&gt;. Let the endpoints of the chord/tangent be &lt;math&gt;A,B&lt;/math&gt;, and the foot of the perpendicular from &lt;math&gt;O_3&lt;/math&gt; to &lt;math&gt;\overline{AB}&lt;/math&gt; be &lt;math&gt;T&lt;/math&gt;. From the similar [[right triangle]]s &lt;math&gt;\triangle HO_1T_1 \sim \triangle HO_2T_2 \sim \triangle HO_3T &lt;/math&gt;,<br /> <br /> &lt;cmath&gt;\frac{HO_1}{4} = \frac{HO_1+14}{10} = \frac{HO_1+10}{O_3T}.&lt;/cmath&gt;<br /> <br /> It follows that &lt;math&gt;HO_1 = \frac{28}{3}&lt;/math&gt;, and that &lt;math&gt;O_3T = \frac{58}{7}&lt;/math&gt;. By the [[Pythagorean Theorem]] on &lt;math&gt;\triangle ATO_3&lt;/math&gt;, we find that <br /> <br /> &lt;cmath&gt;AB = 2AT = 2\left(\sqrt{r_3^2 - O_3T^2}\right) = 2\sqrt{14^2 - \frac{58^2}{7^2}} = \frac{8\sqrt{390}}{7}&lt;/cmath&gt;<br /> <br /> and the answer is &lt;math&gt;m+n+p=\boxed{405}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=2005|n=II|num-b=7|num-a=9}}<br /> <br /> [[Category:Intermediate Geometry Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=2005_AIME_II_Problems/Problem_8&diff=32801 2005 AIME II Problems/Problem 8 2009-09-12T16:03:11Z <p>God of Math: /* Solution */</p> <hr /> <div>== Problem ==<br /> [[Circle]]s &lt;math&gt; C_1 &lt;/math&gt; and &lt;math&gt; C_2 &lt;/math&gt; are externally [[tangent]], and they are both internally tangent to circle &lt;math&gt; C_3. &lt;/math&gt; The radii of &lt;math&gt; C_1 &lt;/math&gt; and &lt;math&gt; C_2 &lt;/math&gt; are 4 and 10, respectively, and the [[center]]s of the three circles are all [[collinear]]. A [[chord]] of &lt;math&gt; C_3 &lt;/math&gt; is also a common external tangent of &lt;math&gt; C_1 &lt;/math&gt; and &lt;math&gt; C_2. &lt;/math&gt; Given that the length of the chord is &lt;math&gt; \frac{m\sqrt{n}}p &lt;/math&gt; where &lt;math&gt; m,n, &lt;/math&gt; and &lt;math&gt; p &lt;/math&gt; are positive integers, &lt;math&gt; m &lt;/math&gt; and &lt;math&gt; p &lt;/math&gt; are [[relatively prime]], and &lt;math&gt; n &lt;/math&gt; is not divisible by the square of any [[prime]], find &lt;math&gt; m+n+p. &lt;/math&gt;<br /> <br /> == Solution ==<br /> &lt;center&gt;&lt;asy&gt;<br /> pointpen = black; pathpen = black + linewidth(0.7); size(200);<br /> pair C1 = (-10,0), C2 = (4,0), C3 = (0,0), H = (-10-28/3,0), T = 58/7*expi(pi-acos(3/7)); <br /> path cir1 = CR(C1,4), cir2 = CR(C2,10), cir3 = CR(C3,14), t = H--T+2*(T-H);<br /> pair A = OP(cir3, t), B = IP(cir3, t), T1 = IP(cir1, t), T2 = IP(cir2, t);<br /> D(cir1); D(cir2); D(cir3); D((14,0)--(-14,0)); D(A--B); D((-14,0)--D(MP(&quot;H&quot;,H,W))--A,linewidth(0.7) + linetype(&quot;4 4&quot;));<br /> D(MP(&quot;O_1&quot;,C1)); D(MP(&quot;O_2&quot;,C2)); D(MP(&quot;O_3&quot;,C3)); D(MP(&quot;T&quot;,T,N)); D(MP(&quot;A&quot;,A,NW)); D(MP(&quot;B&quot;,B,NE)); D(C1--MP(&quot;T_1&quot;,T1,N)); D(C2--MP(&quot;T_2&quot;,T2,N)); D(C3--T); D(rightanglemark(C_3,T,H));<br /> &lt;/asy&gt;&lt;/center&gt;<br /> <br /> Let &lt;math&gt;O_1, O_2, O_3&lt;/math&gt; be the centers and &lt;math&gt;r_1 = 4, r_2 = 10,r_3 = 14&lt;/math&gt; the radii of the circles &lt;math&gt;C_1, C_2, C_3&lt;/math&gt;. Let &lt;math&gt;T_1, T_2&lt;/math&gt; be the points of tangency from the common external tangent of &lt;math&gt;C_1, C_2&lt;/math&gt;, respectively, and let the extension of &lt;math&gt;\overline{T_1T_2}&lt;/math&gt; intersect the extension of &lt;math&gt;\overline{O_1O_2}&lt;/math&gt; at a point &lt;math&gt;H&lt;/math&gt;. Let the endpoints of the chord/tangent be &lt;math&gt;A,B&lt;/math&gt;, and the foot of the perpendicular from &lt;math&gt;O_3&lt;/math&gt; to &lt;math&gt;\overline{AB}&lt;/math&gt; be &lt;math&gt;T&lt;/math&gt;. From the similar [[right triangle]]s &lt;math&gt;\triangle HO_1T_1 \sim \triangle HO_2T_2 \sim \triangle HO_3T &lt;/math&gt;,<br /> <br /> &lt;cmath&gt;\frac{HO_1}{4} = \frac{HO_1+14}{10} = \frac{HO_1+10}{O_3T}.&lt;/cmath&gt;<br /> <br /> It follows that &lt;math&gt;HO_1 = \frac{28}{3}&lt;/math&gt;, and that &lt;math&gt;O_3T = \frac{58}{7}&lt;/math&gt;. By the [[Pythagorean Theorem]] on &lt;math&gt;\triangle ATO_3&lt;/math&gt;, we find that <br /> <br /> &lt;cmath&gt;AB = 2AT = 2\left(\sqrt{r_3^2 - O_1T^2}\right) = 2\sqrt{14^2 - \frac{58^2}{7^2}} = \frac{8\sqrt{390}}{7}&lt;/cmath&gt;<br /> <br /> and the answer is &lt;math&gt;m+n+p=\boxed{405}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=2005|n=II|num-b=7|num-a=9}}<br /> <br /> [[Category:Intermediate Geometry Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1973_USAMO_Problems/Problem_3&diff=32697 1973 USAMO Problems/Problem 3 2009-08-20T06:14:03Z <p>God of Math: /* Solution */</p> <hr /> <div>==Problem==<br /> Three distinct vertices are chosen at random from the vertices of a given regular polygon of &lt;math&gt;(2n+1)&lt;/math&gt; sides. If all such choices are equally likely, what is the probability that the center of the given polygon lies in the interior of the triangle determined by the three chosen random points?<br /> <br /> ==Solution==<br /> There are &lt;math&gt;\binom{2n+1}{3}&lt;/math&gt; ways how to pick the three vertices. We will now count the ways where the interior does NOT contain the center. These are obviously exactly the ways where all three picked vertices lie among some &lt;math&gt;n&lt;/math&gt; consecutive vertices of the polygon.<br /> We will count these as follows: We will go clockwise around the polygon. We can pick the first vertex arbitrarily (&lt;math&gt;2n+1&lt;/math&gt; possibilities). Once we pick it, we have to pick &lt;math&gt;2&lt;/math&gt; out of the next &lt;math&gt;n-1&lt;/math&gt; vertices (&lt;math&gt;\binom{n-1}{2}&lt;/math&gt; possibilities).<br /> <br /> Then the probability that our triangle does NOT contain the center is <br /> &lt;cmath&gt;<br /> p<br /> =<br /> \frac{ (2n+1){\binom{n-1}{2}} }{ {\binom{2n+1}{3} } }<br /> =<br /> \frac{ (1/2)(2n+1)(n-1)(n-2) }{ (1/6)(2n+1)(2n)(2n-1) }<br /> = <br /> \frac{ 3(n-1)(n-2) }{ (2n)(2n-1) }<br /> &lt;/cmath&gt;<br /> <br /> And then the probability we seek is <br /> &lt;cmath&gt;<br /> 1-p<br /> = <br /> \frac{ (2n)(2n-1) - 3(n-1)(n-2) }{ (2n)(2n-1) }<br /> =<br /> \boxed{\frac{ n^2+7n-6 }{ 4n^2 - 2n }}<br /> &lt;/cmath&gt;<br /> ''Note: Trying the regular pentagon case, i.e &lt;math&gt;n = 2&lt;/math&gt;, we get &lt;math&gt;12/12&lt;/math&gt;, or &lt;math&gt;1&lt;/math&gt;. The real probability is &lt;math&gt;1/2&lt;/math&gt; for the pentagon, and the correct general formula is &lt;math&gt;(n+1)/(4n-2)&lt;/math&gt;.''<br /> <br /> ==See also==<br /> <br /> {{USAMO box|year=1973|num-b=2|num-a=4}}<br /> <br /> [[Category:Olympiad Combinatorics Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1973_USAMO_Problems/Problem_3&diff=32696 1973 USAMO Problems/Problem 3 2009-08-20T06:13:06Z <p>God of Math: /* Solution */</p> <hr /> <div>==Problem==<br /> Three distinct vertices are chosen at random from the vertices of a given regular polygon of &lt;math&gt;(2n+1)&lt;/math&gt; sides. If all such choices are equally likely, what is the probability that the center of the given polygon lies in the interior of the triangle determined by the three chosen random points?<br /> <br /> ==Solution==<br /> There are &lt;math&gt;\binom{2n+1}{3}&lt;/math&gt; ways how to pick the three vertices. We will now count the ways where the interior does NOT contain the center. These are obviously exactly the ways where all three picked vertices lie among some &lt;math&gt;n&lt;/math&gt; consecutive vertices of the polygon.<br /> We will count these as follows: We will go clockwise around the polygon. We can pick the first vertex arbitrarily (&lt;math&gt;2n+1&lt;/math&gt; possibilities). Once we pick it, we have to pick &lt;math&gt;2&lt;/math&gt; out of the next &lt;math&gt;n-1&lt;/math&gt; vertices (&lt;math&gt;\binom{n-1}{2}&lt;/math&gt; possibilities).<br /> <br /> Then the probability that our triangle does NOT contain the center is <br /> &lt;cmath&gt;<br /> p<br /> =<br /> \frac{ (2n+1){\binom{n-1}{2}} }{ {\binom{2n+1}{3} } }<br /> =<br /> \frac{ (1/2)(2n+1)(n-1)(n-2) }{ (1/6)(2n+1)(2n)(2n-1) }<br /> = <br /> \frac{ 3(n-1)(n-2) }{ (2n)(2n-1) }<br /> &lt;/cmath&gt;<br /> <br /> And then the probability we seek is <br /> &lt;cmath&gt;<br /> 1-p<br /> = <br /> \frac{ (2n)(2n-1) - 3(n-1)(n-2) }{ (2n)(2n-1) }<br /> =<br /> \boxed{\frac{ n^2+7n-6 }{ 4n^2 - 2n }}<br /> &lt;/cmath&gt;<br /> Note: Trying the regular pentagon case, i.e n = 2, we get 12/12, or 1. The real probability is 1/2 for the pentagon, and the correct general formula is (n+1)/(4n-2).<br /> <br /> ==See also==<br /> <br /> {{USAMO box|year=1973|num-b=2|num-a=4}}<br /> <br /> [[Category:Olympiad Combinatorics Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1975_USAMO_Problems/Problem_5&diff=32557 1975 USAMO Problems/Problem 5 2009-08-04T17:00:53Z <p>God of Math: /* Solution */</p> <hr /> <div>==Problem==<br /> A deck of &lt;math&gt;n&lt;/math&gt; playing cards, which contains three aces, is shuffled at random (it is assumed that all possible card distributions are equally likely). The cards are then turned up one by one from the top until the second ace appears. Prove that the expected (average) number of cards to be turned up is &lt;math&gt;(n+1)/2&lt;/math&gt;.<br /> <br /> ==Solution==<br /> <br /> We begin by induction. Our base case is naturally when &lt;math&gt;n = 3&lt;/math&gt;, as there can be no less than &lt;math&gt;3&lt;/math&gt; cards in the deck. The only way to turn up the second ace is to turn up the first, and then turn up the second, which requires &lt;math&gt;2&lt;/math&gt; moves. This indeed is equal to &lt;math&gt;(3 + 1)/2&lt;/math&gt;. Next, we assume that the expected number of cards required to pull the second ace from a deck of n cards is in fact &lt;math&gt;(n + 1)/2&lt;/math&gt;. Now, we see that to simulate the case with &lt;math&gt;n + 1&lt;/math&gt; cards, we simply must add a card to our deck. By our assumption, we can expect to turn up &lt;math&gt;(n + 1)/2&lt;/math&gt; cards to be turned up, including our second ace. Thus ahead of our second ace, we expect &lt;math&gt;(n - 1)/2&lt;/math&gt; cards , and after it &lt;math&gt;(n - 1)/2&lt;/math&gt; as well. When we add our card, it is ahead of the second ace half the time, and behind if half the time. Therefore we expect to add one card to the number of cards drawn half the time, and add nothing for half the time. Hence we expect to add half a card, and the expected value is now &lt;math&gt;((n + 1)/2) + 1/2)&lt;/math&gt;, or &lt;math&gt;(n + 2)/2&lt;/math&gt;, the desired outcome for the &lt;math&gt;n + 1&lt;/math&gt; case.<br /> <br /> ==See also==<br /> <br /> {{USAMO box|year=1975|num-b=4|after=Last Question}}<br /> <br /> [[Category:Olympiad Combinatorics Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1975_USAMO_Problems/Problem_5&diff=32556 1975 USAMO Problems/Problem 5 2009-08-04T16:59:33Z <p>God of Math: /* Solution */</p> <hr /> <div>==Problem==<br /> A deck of &lt;math&gt;n&lt;/math&gt; playing cards, which contains three aces, is shuffled at random (it is assumed that all possible card distributions are equally likely). The cards are then turned up one by one from the top until the second ace appears. Prove that the expected (average) number of cards to be turned up is &lt;math&gt;(n+1)/2&lt;/math&gt;.<br /> <br /> ==Solution==<br /> <br /> We begin by induction. Our base case is naturally when &lt;math&gt;n = 3&lt;/math&gt;, as there can be no less than &lt;math&gt;3&lt;/math&gt; cards in the deck. The only way to turn up the second ace is to turn up the first, and then turn up the second, which requires &lt;math&gt;2&lt;/math&gt; moves. This indeed is equal to &lt;math&gt;(3 + 1)/2&lt;/math&gt;. Next, we assume that the expected number of cards required to pull the second ace from a deck of n cards is in fact &lt;math&gt;(n + 1)/2&lt;/math&gt;. Now, we see that to simulate the case with &lt;math&gt;n + 1&lt;/math&gt; cards, we simply must add a card to our deck. By our assumption, we can expect to turn up &lt;math&gt;(n + 1)/2&lt;/math&gt; cards to be turned up, including our second ace. Thus ahead of our second ace, there are &lt;math&gt;(n - 1)/2&lt;/math&gt; cards expected, and &lt;math&gt;(n - 1)/2&lt;/math&gt; after it as well. When we add our card, it is ahead of the second ace half the time, and behind if half the time. Therefore we expect to add one card to the number of cards drawn half the time, and add nothing for half the time. Hence we expect to add half a card, and the expected value is now &lt;math&gt;((n + 1)/2) + 1/2)&lt;/math&gt;, or &lt;math&gt;(n + 2)/2&lt;/math&gt;, the desired outcome for the &lt;math&gt;n + 1&lt;/math&gt; case.<br /> <br /> ==See also==<br /> <br /> {{USAMO box|year=1975|num-b=4|after=Last Question}}<br /> <br /> [[Category:Olympiad Combinatorics Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1975_USAMO_Problems/Problem_5&diff=32555 1975 USAMO Problems/Problem 5 2009-08-04T16:53:34Z <p>God of Math: /* Solution */</p> <hr /> <div>==Problem==<br /> A deck of &lt;math&gt;n&lt;/math&gt; playing cards, which contains three aces, is shuffled at random (it is assumed that all possible card distributions are equally likely). The cards are then turned up one by one from the top until the second ace appears. Prove that the expected (average) number of cards to be turned up is &lt;math&gt;(n+1)/2&lt;/math&gt;.<br /> <br /> ==Solution==<br /> <br /> We begin by induction. Our base case is naturally when &lt;math&gt;n = 3&lt;/math&gt;, as there can be no less than &lt;math&gt;3&lt;/math&gt; cards in the deck. The only way to turn up the second ace is to turn up the first, and then turn up the second, which requires &lt;math&gt;2&lt;/math&gt; moves. This indeed is equal to &lt;math&gt;(3 + 1)/2&lt;/math&gt;. Next, we assume that the expected number of cards required to pull the second ace from a deck of n cards is in fact &lt;math&gt;(n + 1)/2&lt;/math&gt;. Now, we see that to simulate the case with &lt;math&gt;n + 1&lt;/math&gt; cards, we simply must add a card to our deck.<br /> <br /> ==See also==<br /> <br /> {{USAMO box|year=1975|num-b=4|after=Last Question}}<br /> <br /> [[Category:Olympiad Combinatorics Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1975_USAMO_Problems/Problem_5&diff=32554 1975 USAMO Problems/Problem 5 2009-08-04T16:53:13Z <p>God of Math: /* Solution */</p> <hr /> <div>==Problem==<br /> A deck of &lt;math&gt;n&lt;/math&gt; playing cards, which contains three aces, is shuffled at random (it is assumed that all possible card distributions are equally likely). The cards are then turned up one by one from the top until the second ace appears. Prove that the expected (average) number of cards to be turned up is &lt;math&gt;(n+1)/2&lt;/math&gt;.<br /> <br /> ==Solution==<br /> <br /> We begin by induction. Our base case is naturally when &lt;math&gt;n&lt;/math&gt; = 3, as there can be no less than &lt;math&gt;3&lt;/math&gt; cards in the deck. The only way to turn up the second ace is to turn up the first, and then turn up the second, which requires &lt;math&gt;2&lt;/math&gt; moves. This indeed is equal to &lt;math&gt;(3 + 1)/2&lt;/math&gt;. Next, we assume that the expected number of cards required to pull the second ace from a deck of n cards is in fact &lt;math&gt;(n + 1)/2&lt;/math&gt;. Now, we see that to simulate the case with &lt;math&gt;n + 1&lt;/math&gt; cards, we simply must add a card to our deck.<br /> <br /> ==See also==<br /> <br /> {{USAMO box|year=1975|num-b=4|after=Last Question}}<br /> <br /> [[Category:Olympiad Combinatorics Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1975_USAMO_Problems/Problem_5&diff=32553 1975 USAMO Problems/Problem 5 2009-08-04T16:52:20Z <p>God of Math: /* Solution */</p> <hr /> <div>==Problem==<br /> A deck of &lt;math&gt;n&lt;/math&gt; playing cards, which contains three aces, is shuffled at random (it is assumed that all possible card distributions are equally likely). The cards are then turned up one by one from the top until the second ace appears. Prove that the expected (average) number of cards to be turned up is &lt;math&gt;(n+1)/2&lt;/math&gt;.<br /> <br /> ==Solution==<br /> <br /> We begin by induction. Our base case is naturally when &lt;math&gt;n&lt;/math&gt; = 3, as there can be no less than 3 cards in the deck. The only way to turn up the second ace is to turn up the first, and then turn up the second, which requires 2 moves. This indeed is equal to &lt;math&gt;(3 + 1)/2&lt;/math&gt;. Next, we assume that the expected number of cards required to pull the second ace from a deck of n cards is in fact &lt;math&gt;(n + 1)/2&lt;/math&gt;. Now, we see that to simulate the case with n + 1 cards, we simply must add a card to our deck.<br /> <br /> ==See also==<br /> <br /> {{USAMO box|year=1975|num-b=4|after=Last Question}}<br /> <br /> [[Category:Olympiad Combinatorics Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1975_USAMO_Problems/Problem_5&diff=32552 1975 USAMO Problems/Problem 5 2009-08-04T16:51:30Z <p>God of Math: /* Solution */</p> <hr /> <div>==Problem==<br /> A deck of &lt;math&gt;n&lt;/math&gt; playing cards, which contains three aces, is shuffled at random (it is assumed that all possible card distributions are equally likely). The cards are then turned up one by one from the top until the second ace appears. Prove that the expected (average) number of cards to be turned up is &lt;math&gt;(n+1)/2&lt;/math&gt;.<br /> <br /> ==Solution==<br /> <br /> &lt;math&gt;We begin by induction. Our base case is naturally when n = 3, as there can be no less than 3 cards in the deck. The only way to turn up the second ace is to turn up the first, and then turn up the second, which requires 2 moves. This indeed is equal to (n + 1)/2. Next, we assume that the expected number of cards required to pull the second ace from a deck of n cards is in fact (n + 1)/2. Now, we see that to simulate the case with n + 1 cards, we simply must add a card to our deck.&lt;/math&gt;<br /> <br /> ==See also==<br /> <br /> {{USAMO box|year=1975|num-b=4|after=Last Question}}<br /> <br /> [[Category:Olympiad Combinatorics Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1975_USAMO_Problems/Problem_5&diff=32551 1975 USAMO Problems/Problem 5 2009-08-04T16:48:12Z <p>God of Math: /* Solution */</p> <hr /> <div>==Problem==<br /> A deck of &lt;math&gt;n&lt;/math&gt; playing cards, which contains three aces, is shuffled at random (it is assumed that all possible card distributions are equally likely). The cards are then turned up one by one from the top until the second ace appears. Prove that the expected (average) number of cards to be turned up is &lt;math&gt;(n+1)/2&lt;/math&gt;.<br /> <br /> ==Solution==<br /> <br /> $We begin by induction. Our base case is naturally when n = 3, as there can be no less than 3 cards in the deck. The only way to turn up the second ace is to turn up the first, and then turn up the second, which requires 2 moves. This indeed is equal to (n + 1)/2. Next, we assume that the expected number of cards required to pull the second ace from a deck of n cards is in fact (n + 1)/2. Now, we see that to simulate the case with n + 1 cards, we simply must add a card to our deck.<br /> <br /> ==See also==<br /> <br /> {{USAMO box|year=1975|num-b=4|after=Last Question}}<br /> <br /> [[Category:Olympiad Combinatorics Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1994_USAMO_Problems/Problem_1&diff=32289 1994 USAMO Problems/Problem 1 2009-07-11T10:26:54Z <p>God of Math: /* Solution */</p> <hr /> <div>==Solution==</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1994_USAMO_Problems/Problem_1&diff=32288 1994 USAMO Problems/Problem 1 2009-07-11T10:26:28Z <p>God of Math: /* Solution */</p> <hr /> <div>==Solution==<br /> <br /> Induct on &lt;math&gt;n&lt;/math&gt;. When &lt;math&gt;n = 1&lt;/math&gt;, we are to show that the interval &lt;math&gt;\, [s_n, s_{n + 1}) \,&lt;/math&gt; contains at least one perfect square. This interval is equivalent to &lt;math&gt;\, [k_0, k_0 + k_1) \,&lt;/math&gt; when &lt;math&gt;n = 1&lt;/math&gt;. Now for some &lt;math&gt;a , a^2 \le k_0^2 &lt; (a+1)^2&lt;/math&gt;.Then it suffices to show that the minimal &quot;distance spanned&quot; by the interval &lt;math&gt;\, [k_0, k_0 + k_1) \,&lt;/math&gt; is greater than or equal to the maximum distance from &lt;math&gt;k_0&lt;/math&gt; to the nearest perfect square. Since the smallest element that can follow &lt;math&gt;k_0&lt;/math&gt; is &lt;math&gt;k_0 + 2&lt;/math&gt;, we have to show the below. Note that we ignore the trivial case where &lt;math&gt;k_0 = a^2&lt;/math&gt;, which should be mentioned.<br /> <br /> &lt;math&gt;2a + 1 \le k_0 + 2&lt;/math&gt;<br /> &lt;math&gt;2a \le k_0 + 1&lt;/math&gt;<br /> &lt;math&gt;2a \le k_0 + (q + 1), where q is a member of &lt;/math&gt;\{1, 2, \ldots, 2\a}&lt;math&gt;<br /> &lt;/math&gt;We now prove by contradiction. Assume that <br /> <br /> <br /> &lt;math&gt;2a &gt; a^2 + q + 1<br /> a^2 - 2a + (q + 1) &lt; 0<br /> No real roots (Discriminant &lt; 0)<br /> =&gt;&lt;= &lt;/math&gt;<br /> <br /> &lt;math&gt;Now assume that this property should be true for &lt;/math&gt;\, [s_{n - 1}, s_{n}) \,&lt;math&gt;. Now to show for &lt;/math&gt;\, [s_n, s_{n + 1}) \,&lt;math&gt;, we note that an interval is defined solely by the sum of the elements in the respective sets and '''not''' on the length of the set. Thus any s_{n + 1} can be turned into an s_n by removing k_{n + 1} and adding it to k_n. The new set is now in a form to which we can apply our assumption. The same goes for s_n and s_{n - 1}. Thus we have finished the inductive argument. <br /> <br /> Therefore etc.&lt;/math&gt;</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1994_USAMO_Problems/Problem_1&diff=32287 1994 USAMO Problems/Problem 1 2009-07-11T10:25:43Z <p>God of Math: Created page with '==Solution== Induct on &lt;math&gt;n&lt;/math&gt;. When &lt;math&gt;n = 1&lt;/math&gt;, we are to show that the interval &lt;math&gt;\, [s_n, s_{n + 1}) \,&lt;/math&gt; contains at least one perfect square. This i…'</p> <hr /> <div>==Solution==<br /> <br /> Induct on &lt;math&gt;n&lt;/math&gt;. When &lt;math&gt;n = 1&lt;/math&gt;, we are to show that the interval &lt;math&gt;\, [s_n, s_{n + 1}) \,&lt;/math&gt; contains at least one perfect square. This interval is equivalent to &lt;math&gt;\, [k_0, k_0 + k_1) \,&lt;/math&gt; when &lt;math&gt;n = 1&lt;/math&gt;. Now for some &lt;math&gt;a , a^2 \le k_0^2 &lt; (a+1)^2&lt;/math&gt;.Then it suffices to show that the minimal &quot;distance spanned&quot; by the interval &lt;math&gt;\, [k_0, k_0 + k_1) \,&lt;/math&gt; is greater than or equal to the maximum distance from &lt;math&gt;k_0&lt;/math&gt; to the nearest perfect square. Since the smallest element that can follow &lt;math&gt;k_0&lt;/math&gt; is &lt;math&gt;k_0 + 2&lt;/math&gt;, we have to show the below. Note that we ignore the trivial case where &lt;math&gt;k_0 = a^2&lt;/math&gt;, which should be mentioned.<br /> <br /> &lt;math&gt;2a + 1 \le k_0 + 2&lt;/math&gt;<br /> &lt;math&gt;2a \le k_0 + 1&lt;/math&gt;<br /> &lt;math&gt;2a \le k_0 + (q + 1), where q is a member of &lt;/math&gt;\{1, 2, \ldots, 2\a}&lt;math&gt;<br /> &lt;/math&gt;We now prove by contradiction. Assume that <br /> <br /> <br /> &lt;math&gt;2a &gt; a^2 + q + 1<br /> a^2 - 2a + (q + 1) &lt; 0<br /> No real roots (Discriminant &lt; 0)<br /> =&gt;&lt;=<br /> <br /> Now assume that this property should be true for &lt;/math&gt;\, [s_{n - 1}, s_{n}) \,&lt;math&gt;. Now to show for &lt;/math&gt;\, [s_n, s_{n + 1}) \,$, we note that an interval is defined solely by the sum of the elements in the respective sets and '''not''' on the length of the set. Thus any s_{n + 1} can be turned into an s_n by removing k_{n + 1} and adding it to k_n. The new set is now in a form to which we can apply our assumption. The same goes for s_n and s_{n - 1}. Thus we have finished the inductive argument. <br /> <br /> Therefore etc.</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1994_USAMO_Problems&diff=32286 1994 USAMO Problems 2009-07-11T10:19:50Z <p>God of Math: /* Problem 1 */</p> <hr /> <div>Problems of the [[1994 USAMO | 1994]] [[USAMO]].<br /> <br /> ==Problem 1==<br /> <br /> Let &lt;math&gt;\, k_1 &lt; k_2 &lt; k_3 &lt; \cdots \,&lt;/math&gt; be positive integers, no two consecutive, and let &lt;math&gt;\, s_m = k_1 + k_2 + \cdots + k_m \,&lt;/math&gt; for &lt;math&gt;\, m = 1,2,3, \ldots \; \;&lt;/math&gt;. Prove that, for each positive integer &lt;math&gt;\, n, \,&lt;/math&gt; the interval &lt;math&gt;\, [s_n, s_{n + 1}) \,&lt;/math&gt; contains at least one perfect square.<br /> <br /> [[1994 USAMO Problems/Problem 1|Solution]]<br /> <br /> ==Problem 2==<br /> <br /> The sides of a 99-gon are initially colored so that consecutive sides are red, blue, red, blue, red, blue, yellow. We make a sequence of modifications in the coloring, changing the color of one side at a time to one of the three given colors (red, blue, yellow), under the constraint that no two adjacent sides may be the same color. By making a sequence of such modifications, is it possible to arrive at the coloring in which consecutive sides <br /> are red, blue, red, blue, red, blue, red, yellow, blue?<br /> <br /> [[1994 USAMO Problems/Problem 2|Solution]]<br /> <br /> ==Problem 3==<br /> <br /> A convex hexagon &lt;math&gt;ABCDEF&lt;/math&gt; is inscribed in a circle such that &lt;math&gt;AB = CD = EF&lt;/math&gt; and diagonals &lt;math&gt;AD&lt;/math&gt;, &lt;math&gt;BE&lt;/math&gt;, and &lt;math&gt;CF&lt;/math&gt; are concurrent. Let &lt;math&gt;P&lt;/math&gt; be the intersection of &lt;math&gt;AD&lt;/math&gt; and &lt;math&gt;CE&lt;/math&gt;. Prove that &lt;math&gt;CP/PE = (AC/CE)^2&lt;/math&gt;.<br /> <br /> [[1994 USAMO Problems/Problem 3|Solution]]<br /> <br /> ==Problem 4==<br /> <br /> Let &lt;math&gt;\, a_1, a_2, a_3, \ldots \,&lt;/math&gt; be a sequence of positive real numbers satisfying &lt;math&gt;\, \sum_{j = 1}^n a_j \geq \sqrt {n} \,&lt;/math&gt; for all &lt;math&gt;\, n \geq 1&lt;/math&gt;. Prove that, for all &lt;math&gt;\, n \geq 1, \,&lt;/math&gt;<br /> <br /> &lt;cmath&gt;\sum_{j = 1}^n a_j^2 &gt; \frac {1}{4} \left( 1 + \frac {1}{2} + \cdots + \frac {1}{n} \right).&lt;/cmath&gt;<br /> <br /> [[1994 USAMO Problems/Problem 4|Solution]]<br /> <br /> ==Problem 5==<br /> <br /> Let &lt;math&gt;\, |U|, \, \sigma(U) \,&lt;/math&gt; and &lt;math&gt;\, \pi(U) \,&lt;/math&gt; denote the number of elements, the sum, and the product, respectively, of a finite set &lt;math&gt;\, U \,&lt;/math&gt; of positive integers. (If &lt;math&gt;\, U \,&lt;/math&gt; is the empty set, &lt;math&gt;\, |U| = 0, \, \sigma(U) = 0, \, \pi(U) = 1&lt;/math&gt;.) Let &lt;math&gt;\, S \,&lt;/math&gt; be a finite set of positive integers. As usual, let &lt;math&gt;\, \binom{n}{k} \,&lt;/math&gt; denote &lt;math&gt;\, n! \over k! \, (n - k)!&lt;/math&gt;. Prove that<br /> <br /> &lt;cmath&gt;\sum_{U \subseteq S} ( - 1)^{|U|} \binom{m - \sigma(U)}{|S|} = \pi(S)&lt;/cmath&gt;<br /> <br /> for all integers &lt;math&gt;\, m \geq \sigma(S)&lt;/math&gt;.<br /> <br /> [[1994 USAMO Problems/Problem 5|Solution]]<br /> <br /> == Resources ==<br /> <br /> {{USAMO box|year=1994|before=[[1993 USAMO]]|after=[[1995 USAMO]]}}<br /> <br /> * [http://www.artofproblemsolving.com/Forum/resources.php?c=182&amp;cid=27&amp;year=1994 1994 USAMO Problems on the resources page]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1994_USAMO_Problems&diff=32285 1994 USAMO Problems 2009-07-11T10:19:13Z <p>God of Math: </p> <hr /> <div>Problems of the [[1994 USAMO | 1994]] [[USAMO]].<br /> <br /> ==Problem 1==<br /> <br /> Let &lt;math&gt;\, k_1 &lt; k_2 &lt; k_3 &lt; \cdots \,&lt;/math&gt; be positive integers, no two consecutive, and let &lt;math&gt;\, s_m = k_1 + k_2 + \cdots + k_m \,&lt;/math&gt; for &lt;math&gt;\, m = 1,2,3, \ldots \; \;&lt;/math&gt;. Prove that, for each positive integer &lt;math&gt;\, n, \,&lt;/math&gt; the interval &lt;math&gt;\, [s_n, s_{n + 1}) \,&lt;/math&gt; contains at least one perfect square.<br /> <br /> [[1994 USAMO Problems/Problem 1|Solution]]<br /> <br /> <br /> Induct on &lt;math&gt;n&lt;/math&gt;. When &lt;math&gt;n = 1&lt;/math&gt;, we are to show that the interval &lt;math&gt;\, [s_n, s_{n + 1}) \,&lt;/math&gt; contains at least one perfect square. This interval is equivalent to &lt;math&gt;\, [k_0, k_0 + k_1) \,&lt;/math&gt; when &lt;math&gt;n = 1&lt;/math&gt;. Now for some &lt;math&gt;a , a^2 \le k_0^2 &lt; (a+1)^2&lt;/math&gt;.Then it suffices to show that the minimal &quot;distance spanned&quot; by the interval &lt;math&gt;\, [k_0, k_0 + k_1) \,&lt;/math&gt; is greater than or equal to the maximum distance from &lt;math&gt;k_0&lt;/math&gt; to the nearest perfect square. Since the smallest element that can follow &lt;math&gt;k_0&lt;/math&gt; is &lt;math&gt;k_0 + 2&lt;/math&gt;, we have to show the below. Note that we ignore the trivial case where &lt;math&gt;k_0 = a^2&lt;/math&gt;, which should be mentioned.<br /> <br /> &lt;math&gt;2a + 1 \le k_0 + 2&lt;/math&gt;<br /> &lt;math&gt;2a \le k_0 + 1&lt;/math&gt;<br /> &lt;math&gt;2a \le k_0 + (q + 1)&lt;/math&gt;, where &lt;math&gt;q&lt;/math&gt; is a member of &lt;math&gt;\{1, 2, \ldots, 2\a}&lt;/math&gt;<br /> We now prove by contradiction. Assume that<br /> <br /> ==Problem 2==<br /> <br /> The sides of a 99-gon are initially colored so that consecutive sides are red, blue, red, blue, red, blue, yellow. We make a sequence of modifications in the coloring, changing the color of one side at a time to one of the three given colors (red, blue, yellow), under the constraint that no two adjacent sides may be the same color. By making a sequence of such modifications, is it possible to arrive at the coloring in which consecutive sides <br /> are red, blue, red, blue, red, blue, red, yellow, blue?<br /> <br /> [[1994 USAMO Problems/Problem 2|Solution]]<br /> <br /> ==Problem 3==<br /> <br /> A convex hexagon &lt;math&gt;ABCDEF&lt;/math&gt; is inscribed in a circle such that &lt;math&gt;AB = CD = EF&lt;/math&gt; and diagonals &lt;math&gt;AD&lt;/math&gt;, &lt;math&gt;BE&lt;/math&gt;, and &lt;math&gt;CF&lt;/math&gt; are concurrent. Let &lt;math&gt;P&lt;/math&gt; be the intersection of &lt;math&gt;AD&lt;/math&gt; and &lt;math&gt;CE&lt;/math&gt;. Prove that &lt;math&gt;CP/PE = (AC/CE)^2&lt;/math&gt;.<br /> <br /> [[1994 USAMO Problems/Problem 3|Solution]]<br /> <br /> ==Problem 4==<br /> <br /> Let &lt;math&gt;\, a_1, a_2, a_3, \ldots \,&lt;/math&gt; be a sequence of positive real numbers satisfying &lt;math&gt;\, \sum_{j = 1}^n a_j \geq \sqrt {n} \,&lt;/math&gt; for all &lt;math&gt;\, n \geq 1&lt;/math&gt;. Prove that, for all &lt;math&gt;\, n \geq 1, \,&lt;/math&gt;<br /> <br /> &lt;cmath&gt;\sum_{j = 1}^n a_j^2 &gt; \frac {1}{4} \left( 1 + \frac {1}{2} + \cdots + \frac {1}{n} \right).&lt;/cmath&gt;<br /> <br /> [[1994 USAMO Problems/Problem 4|Solution]]<br /> <br /> ==Problem 5==<br /> <br /> Let &lt;math&gt;\, |U|, \, \sigma(U) \,&lt;/math&gt; and &lt;math&gt;\, \pi(U) \,&lt;/math&gt; denote the number of elements, the sum, and the product, respectively, of a finite set &lt;math&gt;\, U \,&lt;/math&gt; of positive integers. (If &lt;math&gt;\, U \,&lt;/math&gt; is the empty set, &lt;math&gt;\, |U| = 0, \, \sigma(U) = 0, \, \pi(U) = 1&lt;/math&gt;.) Let &lt;math&gt;\, S \,&lt;/math&gt; be a finite set of positive integers. As usual, let &lt;math&gt;\, \binom{n}{k} \,&lt;/math&gt; denote &lt;math&gt;\, n! \over k! \, (n - k)!&lt;/math&gt;. Prove that<br /> <br /> &lt;cmath&gt;\sum_{U \subseteq S} ( - 1)^{|U|} \binom{m - \sigma(U)}{|S|} = \pi(S)&lt;/cmath&gt;<br /> <br /> for all integers &lt;math&gt;\, m \geq \sigma(S)&lt;/math&gt;.<br /> <br /> [[1994 USAMO Problems/Problem 5|Solution]]<br /> <br /> == Resources ==<br /> <br /> {{USAMO box|year=1994|before=[[1993 USAMO]]|after=[[1995 USAMO]]}}<br /> <br /> * [http://www.artofproblemsolving.com/Forum/resources.php?c=182&amp;cid=27&amp;year=1994 1994 USAMO Problems on the resources page]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=2006_AIME_II_Problems/Problem_7&diff=32238 2006 AIME II Problems/Problem 7 2009-07-04T11:12:12Z <p>God of Math: /* Solution 1 */</p> <hr /> <div>== Problem ==<br /> Find the number of [[ordered pair]]s of [[positive]] [[integer]]s &lt;math&gt; (a,b) &lt;/math&gt; such that &lt;math&gt; a+b=1000 &lt;/math&gt; and neither &lt;math&gt; a &lt;/math&gt; nor &lt;math&gt; b &lt;/math&gt; has a zero digit.<br /> <br /> __TOC__<br /> == Solution ==<br /> === Solution 1 ===<br /> There are &lt;math&gt;\left\lfloor\frac{999}{10}\right\rfloor = 99&lt;/math&gt; numbers up to 1000 that have 0 as their units digit. All of the other excluded possibilities are when &lt;math&gt;a&lt;/math&gt; or &lt;math&gt;b&lt;/math&gt; have a 0 in the tens digit, and since the equation is symmetric, we will just count when &lt;math&gt;a&lt;/math&gt; has a 0 in the tens digit and multiply by 2 (notice that the only time both &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; can have a 0 in the tens digit is when they are divisible by 100, which falls into the above category, so we do not have to worry about [[Principle of Inclusion-Exclusion|overcounting]]). <br /> <br /> Excluding the numbers divisible by 100, which were counted already, there are &lt;math&gt;9&lt;/math&gt; numbers in every hundred numbers that have a tens digit of 0 (this is true from 100 to 900), totaling &lt;math&gt;9 \cdot 9 = 81&lt;/math&gt; such numbers; considering &lt;math&gt;b&lt;/math&gt; also and we have &lt;math&gt;81 \cdot 2 = 162&lt;/math&gt;. Therefore, there are &lt;math&gt;999 - (99 + 162) = \boxed{738}&lt;/math&gt; such ordered pairs.<br /> <br /> === Solution 2 ===<br /> Let &lt;math&gt;a = \overline{cde}&lt;/math&gt; and &lt;math&gt;b = \overline{fgh}&lt;/math&gt; be 3 digit numbers:<br /> <br /> cde<br /> +fgh<br /> ----<br /> 1000<br /> <br /> &lt;math&gt;e&lt;/math&gt; and &lt;math&gt;h&lt;/math&gt; must add up to &lt;math&gt;10&lt;/math&gt;, &lt;math&gt;d&lt;/math&gt; and &lt;math&gt;g&lt;/math&gt; must add up to &lt;math&gt;9&lt;/math&gt;, and &lt;math&gt;c&lt;/math&gt; and &lt;math&gt;f&lt;/math&gt; must add up to &lt;math&gt;9&lt;/math&gt;. Since none of the digits can be 0, there are &lt;math&gt;9 \times 8 \times 8=576&lt;/math&gt; possibilites if both numbers are three digits.<br /> <br /> There are two other scenarios. &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; can be a three digit number and a two digit number, or a three digit number and a one digit number. For the first scenario, there are &lt;math&gt;9 \times 8 \times 2=144&lt;/math&gt; possibilities (the two accounting for whether &lt;math&gt;a&lt;/math&gt; or &lt;math&gt;b&lt;/math&gt; has three digits) and for the second case there are &lt;math&gt;9 \times 2=18&lt;/math&gt; possibilities. Thus, thus total possibilities for &lt;math&gt;(a,b)&lt;/math&gt; is &lt;math&gt;576+144+18=738&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=2006|n=II|num-b=6|num-a=8}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1986_AIME_Problems/Problem_7&diff=32207 1986 AIME Problems/Problem 7 2009-06-30T06:03:57Z <p>God of Math: Alternate solution</p> <hr /> <div>== Problem ==<br /> The increasing [[sequence]] &lt;math&gt;1,3,4,9,10,12,13\cdots&lt;/math&gt; consists of all those positive [[integer]]s which are [[exponent|powers]] of 3 or sums of distinct powers of 3. Find the &lt;math&gt;\displaystyle 100^{\mbox{th}}&lt;/math&gt; term of this sequence.<br /> <br /> == Solution 1 ==<br /> <br /> Rewrite all of the terms in base 3. Since the numbers are sums of ''distinct'' powers of 3, in base 3 each number is a sequence of 1s and 0s (if there is a 2, then it is no longer the sum of distinct powers of 3). Therefore, we can recast this into base 2 (binary) in order to determine the 100th number. &lt;math&gt;100&lt;/math&gt; is equal to &lt;math&gt;64 + 32 + 4&lt;/math&gt;, so in binary form we get &lt;math&gt;1100100&lt;/math&gt;. However, we must change it back to base 3 for the answer, which is &lt;math&gt;3^6 + 3^5 + 3^2 = 729 + 243 + 9 = 981&lt;/math&gt;.<br /> <br /> -------------------------------------------------------------<br /> <br /> == Solution 2 ==<br /> <br /> Notice that the first term of the sequence is &lt;math&gt;1&lt;/math&gt;, the second is &lt;math&gt;9&lt;/math&gt;, the fourth is &lt;math&gt;27&lt;/math&gt;, and so on. Thus the &lt;math&gt;64th&lt;/math&gt; term of the sequence is &lt;math&gt;729&lt;/math&gt;. Now out of &lt;math&gt;64&lt;/math&gt; terms which are of the form &lt;math&gt;729&lt;/math&gt; + &lt;math&gt;'''S'''&lt;/math&gt;, &lt;math&gt;32&lt;/math&gt; of them include &lt;math&gt;243&lt;/math&gt; and &lt;math&gt;32&lt;/math&gt; do not. The smallest term that includes &lt;math&gt;243&lt;/math&gt;, i.e. &lt;math&gt;972&lt;/math&gt;, is greater than the largest term which does not, or &lt;math&gt;854&lt;/math&gt;. So the &lt;math&gt;95&lt;/math&gt;th term will be &lt;math&gt;972&lt;/math&gt;, then &lt;math&gt;973&lt;/math&gt;, then &lt;math&gt;976&lt;/math&gt;, then &lt;math&gt;977&lt;/math&gt;, and finally &lt;math&gt;981&lt;/math&gt;<br /> <br /> == See also ==<br /> {{AIME box|year=1986|num-b=6|num-a=8}}<br /> * [[AIME Problems and Solutions]]<br /> * [[American Invitational Mathematics Examination]]<br /> * [[Mathematics competition resources]]<br /> <br /> [[Category:Intermediate Number Theory Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_I_Problems/Problem_10&diff=32006 2009 AIME I Problems/Problem 10 2009-06-02T13:14:58Z <p>God of Math: /* Solution */</p> <hr /> <div>== Problem ==<br /> <br /> The Annual Interplanetary Mathematics Examination (AIME) is written by a committee of five Martians, five Venusians, and five Earthlings. At meetings, committee members sit at a round table with chairs numbered from &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;15&lt;/math&gt; in clockwise order. Committee rules state that a Martian must occupy chair &lt;math&gt;1&lt;/math&gt; and an Earthling must occupy chair &lt;math&gt;15&lt;/math&gt;, Furthermore, no Earthling can sit immediately to the left of a Martian, no Martian can sit immediately to the left of a Venusian, and no Venusian can sit immediately to the left of an Earthling. The number of possible seating arrangements for the committee is &lt;math&gt;N(5!)^3&lt;/math&gt;. Find &lt;math&gt;N&lt;/math&gt;.<br /> <br /> == Solution ==<br /> <br /> Since after each planet, only members of another planet can follow, we simply count the lengths of the blocks adding up to ten. These blocks must be of the form MVE with a certain number of M's,V's,and E's,we consider a few different cases:<br /> <br /> 1. One block of five people- There is only one way to arrange this so &lt;math&gt;{1^3}=1&lt;/math&gt;.<br /> <br /> 2. Five blocks of one person - There is also only one way to arrange this so we get &lt;math&gt;{1^3}=1&lt;/math&gt;.<br /> <br /> 3. Two blocks - There are two cases: &lt;math&gt;4+1&lt;/math&gt; and &lt;math&gt;3+2&lt;/math&gt;. Each of these can be arranged two ways so we get &lt;math&gt;{(2+2)^3}=64&lt;/math&gt;.<br /> <br /> 4. Three blocks - There are also two cases: &lt;math&gt;3+1+1&lt;/math&gt; and &lt;math&gt;2+2+1&lt;/math&gt;.Each of these can be arranged three ways giving us &lt;math&gt;{(3+3)^3}=216&lt;/math&gt;.<br /> <br /> 5. Four blocks - There is only one case: &lt;math&gt;2+1+1+1&lt;/math&gt;. This can be arranged four ways giving us &lt;math&gt;{4^3}=64&lt;/math&gt;.<br /> <br /> Combining all these cases, we get &lt;math&gt;1+1+64+64+216= \boxed{346}&lt;/math&gt;<br /> <br /> == See also ==<br /> {{AIME box|year=2009|n=I|num-b=9|num-a=11}}</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_3_Pre_2005_Problems/Problem_12&diff=31463 Mock AIME 3 Pre 2005 Problems/Problem 12 2009-04-25T22:19:09Z <p>God of Math: /* Solution */</p> <hr /> <div>==Problem==<br /> Determine the number of integers &lt;math&gt;n&lt;/math&gt; such that &lt;math&gt;1 \le n \le 1000&lt;/math&gt; and &lt;math&gt;n^{12} - 1&lt;/math&gt; is divisible by &lt;math&gt;73&lt;/math&gt;.<br /> <br /> ==Solution==<br /> {{solution}}<br /> <br /> We see a pattern when we look at the numbers that do fulfull this property. The first number is &lt;math&gt;1&lt;/math&gt;. Then &lt;math&gt;3, 8, 9, 24, 27, ....&lt;/math&gt;. This follows a pattern. The first number being &lt;math&gt;1&lt;/math&gt;, and the rest being the previous: &lt;math&gt;+2, +5, +1, +15, +3, +19, +3, +15, +1, +5, +2&lt;/math&gt;. This sequence then repeats itself. We hence find that there are a total of &lt;math&gt;11*15 - 1&lt;/math&gt; or &lt;math&gt;\boxed{164}&lt;/math&gt; numbers that satisfy the inequality.<br /> <br /> ==See also==</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_3_Pre_2005_Problems/Problem_12&diff=31462 Mock AIME 3 Pre 2005 Problems/Problem 12 2009-04-25T22:18:46Z <p>God of Math: /* Solution */</p> <hr /> <div>==Problem==<br /> Determine the number of integers &lt;math&gt;n&lt;/math&gt; such that &lt;math&gt;1 \le n \le 1000&lt;/math&gt; and &lt;math&gt;n^{12} - 1&lt;/math&gt; is divisible by &lt;math&gt;73&lt;/math&gt;.<br /> <br /> ==Solution==<br /> {{solution}}<br /> <br /> We see a pattern when we look at the numbers that do fulfull this property. The first number is &lt;math&gt;1&lt;/math&gt;. Then &lt;math&gt;3, 8, 9, 24, 27, ....&lt;/math&gt;. This follows a pattern. The first number being &lt;math&gt;1&lt;/math&gt;, and the rest being the previous &lt;math&gt;+2, +5, +1, +15, +3, +19, +3, +15, +1, +5, +2&lt;/math&gt;. This sequence then repeats itself. We hence find that there are a total of &lt;math&gt;11*15 - 1&lt;/math&gt; or &lt;math&gt;\boxed{164}&lt;/math&gt; numbers that satisfy the inequality.<br /> <br /> ==See also==</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_2006-2007_Problems/Problem_15&diff=31461 Mock AIME 1 2006-2007 Problems/Problem 15 2009-04-25T22:07:36Z <p>God of Math: /* Solution */</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;S&lt;/math&gt; be the set of integers &lt;math&gt;0,1,2,...,10^{11}-1&lt;/math&gt;. An element &lt;math&gt;x\in S&lt;/math&gt; (in) is chosen at random. Let &lt;math&gt;\star (x)&lt;/math&gt; denote the sum of the digits of &lt;math&gt;x&lt;/math&gt;. The probability that &lt;math&gt;\star(x)&lt;/math&gt; is divisible by 11 is &lt;math&gt;\frac{m}{n}&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Compute the last 3 digits of &lt;math&gt;m+n&lt;/math&gt;<br /> ==Solution==<br /> {{solution}}<br /> <br /> <br /> Counting all &lt;math&gt;2&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, and &lt;math&gt;4&lt;/math&gt; digit combinations and then permuting only those up to &lt;math&gt;2045&lt;/math&gt;, we find that there are &lt;math&gt;186&lt;/math&gt; numbers whose sums are either &lt;math&gt;11&lt;/math&gt; or &lt;math&gt;22&lt;/math&gt;. We need not account for the sum &lt;math&gt;33&lt;/math&gt;, as it is not achievable with a &lt;math&gt;2&lt;/math&gt; as the lowest digit. Since there are a total of &lt;math&gt;2048&lt;/math&gt; numbers and &lt;math&gt;186&lt;/math&gt; that work, we get &lt;math&gt;186/2048&lt;/math&gt; or &lt;math&gt;93/1024&lt;/math&gt;. Our sum is then &lt;math&gt;93 + 1024 = 1117&lt;/math&gt;. The last three digits are &lt;math&gt;\boxed{117}&lt;/math&gt;.<br /> <br /> <br /> ----<br /> <br /> *[[Mock AIME 1 2006-2007/Problem 14 | Previous Problem]]<br /> <br /> *[[Mock AIME 1 2006-2007]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_2_2006-2007_Problems/Problem_7&diff=31460 Mock AIME 2 2006-2007 Problems/Problem 7 2009-04-25T22:04:40Z <p>God of Math: /* Solution */</p> <hr /> <div>== Problem ==<br /> <br /> A right circular cone of base radius &lt;math&gt;17&lt;/math&gt;cm and slant height &lt;math&gt;34&lt;/math&gt;cm is given. &lt;math&gt;P&lt;/math&gt; is a point on the circumference of the base and the shortest path from &lt;math&gt;P&lt;/math&gt; around the cone and back is drawn (see diagram). If the length of this path is &lt;math&gt;m\sqrt{n},&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers, find &lt;math&gt;m+n.&lt;/math&gt;<br /> <br /> [[Image:Mock_AIME_2_2007_Problem8.jpg]]<br /> <br /> ==Solution==<br /> {{solution}}<br /> <br /> We begin by noticing that that the shortest path from a point on the base to and around the cone is the perpendicular from the aforementioned point to the slant line. We can now construct two equations based on this fact. Let &lt;math&gt;x&lt;/math&gt; be the length from the point on the other end of the diameter from &lt;math&gt;P&lt;/math&gt; to the point at which &lt;math&gt;P&lt;/math&gt; is perpendicular to the slant. Let &lt;math&gt;y&lt;/math&gt; now be the diameter of the shaded circle. We now have two equations : &lt;math&gt;x_{}^{2} + y_{}^{2} = 34_{}^{}&lt;/math&gt; and &lt;math&gt;y_{}^{2} + (34 - x)_{}^{2} = 34_{}^{2}&lt;/math&gt;. We can tell from this equation that &lt;math&gt;34 - x = x&lt;/math&gt;, so &lt;math&gt;x = 17&lt;/math&gt;. From this we can deduce that y = &lt;math&gt;17\sqrt3&lt;/math&gt;.<br /> <br /> <br /> <br /> <br /> <br /> ----<br /> <br /> *[[Mock AIME 2 2006-2007/Problem 6 | Previous Problem]]<br /> <br /> *[[Mock AIME 2 2006-2007/Problem 8 | Next Problem]]<br /> <br /> *[[Mock AIME 2 2006-2007]]<br /> <br /> [[Category:Intermediate Geometry Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_2_2006-2007_Problems/Problem_7&diff=31459 Mock AIME 2 2006-2007 Problems/Problem 7 2009-04-25T22:04:11Z <p>God of Math: /* Solution */</p> <hr /> <div>== Problem ==<br /> <br /> A right circular cone of base radius &lt;math&gt;17&lt;/math&gt;cm and slant height &lt;math&gt;34&lt;/math&gt;cm is given. &lt;math&gt;P&lt;/math&gt; is a point on the circumference of the base and the shortest path from &lt;math&gt;P&lt;/math&gt; around the cone and back is drawn (see diagram). If the length of this path is &lt;math&gt;m\sqrt{n},&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers, find &lt;math&gt;m+n.&lt;/math&gt;<br /> <br /> [[Image:Mock_AIME_2_2007_Problem8.jpg]]<br /> <br /> ==Solution==<br /> {{solution}}<br /> <br /> We begin by noticing that that the shortest path from a point on the base to and around the cone is the perpendicular from the aforementioned point to the slant line. We can now construct two equations based on this fact. Let &lt;math&gt;x&lt;/math&gt; be the length from the point on the other end of the diameter from P to the point at which P is perpendicular to the slant. Let &lt;math&gt;y&lt;/math&gt; now be the diameter of the shaded circle. We now have two equations : &lt;math&gt;x_{}^{2} + y_{}^{2} = 34_{}^{}&lt;/math&gt; and &lt;math&gt;y_{}^{2} + (34 - x)_{}^{2} = 34_{}^{2}&lt;/math&gt;. We can tell from this equation that &lt;math&gt;34 - x = x&lt;/math&gt;, so &lt;math&gt;x = 17&lt;/math&gt;. From this we can deduce that y = &lt;math&gt;17\sqrt3&lt;/math&gt;.<br /> <br /> <br /> <br /> <br /> <br /> ----<br /> <br /> *[[Mock AIME 2 2006-2007/Problem 6 | Previous Problem]]<br /> <br /> *[[Mock AIME 2 2006-2007/Problem 8 | Next Problem]]<br /> <br /> *[[Mock AIME 2 2006-2007]]<br /> <br /> [[Category:Intermediate Geometry Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_2_2006-2007_Problems/Problem_7&diff=31458 Mock AIME 2 2006-2007 Problems/Problem 7 2009-04-25T19:53:03Z <p>God of Math: /* Solution */</p> <hr /> <div>== Problem ==<br /> <br /> A right circular cone of base radius &lt;math&gt;17&lt;/math&gt;cm and slant height &lt;math&gt;34&lt;/math&gt;cm is given. &lt;math&gt;P&lt;/math&gt; is a point on the circumference of the base and the shortest path from &lt;math&gt;P&lt;/math&gt; around the cone and back is drawn (see diagram). If the length of this path is &lt;math&gt;m\sqrt{n},&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers, find &lt;math&gt;m+n.&lt;/math&gt;<br /> <br /> [[Image:Mock_AIME_2_2007_Problem8.jpg]]<br /> <br /> ==Solution==<br /> {{solution}}<br /> <br /> We begin by noticing that that the shortest path from a point on the base to and around the cone is the perpendicular from the aforementioned point to the slant line. We can now construct two equations based on this fact. Let x be the length from the point on the other end of the diameter from P to the point at which P is perpendicular to the slant. Let y now be the diameter of the shaded circle. We now have two equations : &lt;math&gt;x_{}^{2} + y_{}^{2} = 34_{}^{}&lt;/math&gt; and &lt;math&gt;y_{}^{2} + (34 - x)_{}^{2} = 34_{}^{2}&lt;/math&gt;. We can tell from this equation that &lt;math&gt;34 - x = x&lt;/math&gt;, so &lt;math&gt;x = 17&lt;/math&gt;. From this we can deduce that y = &lt;math&gt;17\sqrt3&lt;/math&gt;.<br /> <br /> <br /> <br /> <br /> <br /> ----<br /> <br /> *[[Mock AIME 2 2006-2007/Problem 6 | Previous Problem]]<br /> <br /> *[[Mock AIME 2 2006-2007/Problem 8 | Next Problem]]<br /> <br /> *[[Mock AIME 2 2006-2007]]<br /> <br /> [[Category:Intermediate Geometry Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_2_2006-2007_Problems/Problem_7&diff=31457 Mock AIME 2 2006-2007 Problems/Problem 7 2009-04-25T19:15:16Z <p>God of Math: /* Solution */</p> <hr /> <div>== Problem ==<br /> <br /> A right circular cone of base radius &lt;math&gt;17&lt;/math&gt;cm and slant height &lt;math&gt;34&lt;/math&gt;cm is given. &lt;math&gt;P&lt;/math&gt; is a point on the circumference of the base and the shortest path from &lt;math&gt;P&lt;/math&gt; around the cone and back is drawn (see diagram). If the length of this path is &lt;math&gt;m\sqrt{n},&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers, find &lt;math&gt;m+n.&lt;/math&gt;<br /> <br /> [[Image:Mock_AIME_2_2007_Problem8.jpg]]<br /> <br /> ==Solution==<br /> {{solution}}<br /> <br /> We begin by noticing that that the shortest path from a point on the base to and around the cone is the perpendicular from the aforementioned point to the slant line. We can now construct two equations based on this fact. Let x be the length from the point on the other end of the diameter from P to the point at which P is perpendicular to the slant. Let y now be the diameter of the shaded circle. We now have two equations : &lt;math&gt;x_{}^{2} + y_{}^{2} = 34_{}^{}&lt;/math&gt; and &lt;math&gt;y_{}^{2} + (34 - x)_{}^{2} = 34_{}^{2}&lt;/math&gt;. We can tell from this equation that &lt;math&gt;34 - x = x&lt;/math&gt;, so &lt;math&gt;x = 17&lt;/math&gt;. From this we can deduce that y = &lt;math&gt;17\sqrt(3)&lt;/math&gt;.<br /> <br /> <br /> <br /> <br /> <br /> ----<br /> <br /> *[[Mock AIME 2 2006-2007/Problem 6 | Previous Problem]]<br /> <br /> *[[Mock AIME 2 2006-2007/Problem 8 | Next Problem]]<br /> <br /> *[[Mock AIME 2 2006-2007]]<br /> <br /> [[Category:Intermediate Geometry Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_2_2006-2007_Problems/Problem_7&diff=31456 Mock AIME 2 2006-2007 Problems/Problem 7 2009-04-25T19:14:52Z <p>God of Math: /* Problem */</p> <hr /> <div>== Problem ==<br /> <br /> A right circular cone of base radius &lt;math&gt;17&lt;/math&gt;cm and slant height &lt;math&gt;34&lt;/math&gt;cm is given. &lt;math&gt;P&lt;/math&gt; is a point on the circumference of the base and the shortest path from &lt;math&gt;P&lt;/math&gt; around the cone and back is drawn (see diagram). If the length of this path is &lt;math&gt;m\sqrt{n},&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers, find &lt;math&gt;m+n.&lt;/math&gt;<br /> <br /> [[Image:Mock_AIME_2_2007_Problem8.jpg]]<br /> <br /> ==Solution==<br /> {{solution}}<br /> <br /> We begin by noticing that that the shortest path from a point on the base to and around the cone is the perpendicular from the aforementioned point to the slant line. We can now construct two equations based on this fact. Let x be the length from the point on the other end of the diameter from P to the point at which P is perpendicular to the slant. Let y now be the diameter of the shaded circle. We now have two equations : &lt;math&gt;x_{}^{2} + y_{}^{2} = 34_{}^{}&lt;/math&gt; and &lt;math&gt;y_{}^{2} + (34 - x)_{}^{2} = 34_{}^{2}&lt;/math&gt;. We can tell from this equation that &lt;math&gt;34 - x = x&lt;/math&gt;, so &lt;math&gt;x = 17&lt;/math&gt;. From this we can deduce that y = $17*sqrt(3)<br /> <br /> <br /> <br /> <br /> <br /> ----<br /> <br /> *[[Mock AIME 2 2006-2007/Problem 6 | Previous Problem]]<br /> <br /> *[[Mock AIME 2 2006-2007/Problem 8 | Next Problem]]<br /> <br /> *[[Mock AIME 2 2006-2007]]<br /> <br /> [[Category:Intermediate Geometry Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_2_2006-2007_Problems/Problem_7&diff=31455 Mock AIME 2 2006-2007 Problems/Problem 7 2009-04-25T19:14:35Z <p>God of Math: /* Solution */</p> <hr /> <div>== Problem ==<br /> <br /> A right circular cone of base radius &lt;math&gt;\displaystyle 17&lt;/math&gt;cm and slant height &lt;math&gt;\displaystyle 34&lt;/math&gt;cm is given. &lt;math&gt;\displaystyle P&lt;/math&gt; is a point on the circumference of the base and the shortest path from &lt;math&gt;\displaystyle P&lt;/math&gt; around the cone and back is drawn (see diagram). If the length of this path is &lt;math&gt;\displaystyle m\sqrt{n},&lt;/math&gt; where &lt;math&gt;\displaystyle m&lt;/math&gt; and &lt;math&gt;\displaystyle n&lt;/math&gt; are relatively prime positive integers, find &lt;math&gt;\displaystyle m+n.&lt;/math&gt;<br /> <br /> [[Image:Mock_AIME_2_2007_Problem8.jpg]]<br /> <br /> ==Solution==<br /> {{solution}}<br /> <br /> We begin by noticing that that the shortest path from a point on the base to and around the cone is the perpendicular from the aforementioned point to the slant line. We can now construct two equations based on this fact. Let x be the length from the point on the other end of the diameter from P to the point at which P is perpendicular to the slant. Let y now be the diameter of the shaded circle. We now have two equations : &lt;math&gt;x_{}^{2} + y_{}^{2} = 34_{}^{}&lt;/math&gt; and &lt;math&gt;y_{}^{2} + (34 - x)_{}^{2} = 34_{}^{2}&lt;/math&gt;. We can tell from this equation that &lt;math&gt;34 - x = x&lt;/math&gt;, so &lt;math&gt;x = 17&lt;/math&gt;. From this we can deduce that y =$17*sqrt(3)<br /> <br /> <br /> <br /> <br /> <br /> ----<br /> <br /> *[[Mock AIME 2 2006-2007/Problem 6 | Previous Problem]]<br /> <br /> *[[Mock AIME 2 2006-2007/Problem 8 | Next Problem]]<br /> <br /> *[[Mock AIME 2 2006-2007]]<br /> <br /> [[Category:Intermediate Geometry Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=Butterfly_Theorem&diff=31454 Butterfly Theorem 2009-04-25T18:58:22Z <p>God of Math: /* Proof */</p> <hr /> <div>Let &lt;math&gt;D&lt;/math&gt; be the [[midpoint]] of [[chord]] &lt;math&gt;BC&lt;/math&gt; of a [[circle]], through which two other chords &lt;math&gt;EH&lt;/math&gt; and &lt;math&gt;FG&lt;/math&gt; are drawn. &lt;math&gt;EG&lt;/math&gt; and &lt;math&gt;HF&lt;/math&gt; intersect chord &lt;math&gt;BC&lt;/math&gt; at &lt;math&gt;I&lt;/math&gt; and &lt;math&gt;J&lt;/math&gt;, respectively. The '''Butterfly Theorem''' states that &lt;math&gt;D&lt;/math&gt; is the midpoint of &lt;math&gt;IJ&lt;/math&gt;.<br /> <br /> &lt;geogebra&gt;ac0eaced14d78b0f4ff370ae453962b4db309b5f&lt;/geogebra&gt; <br /> <br /> ==Proof==<br /> {{solution}}<br /> <br /> Link to a good proof : <br /> <br /> http://agutie.homestead.com/FiLEs/GeometryButterfly.html<br /> <br /> ==See also==<br /> [[Category:Geometry]]<br /> [[Category:Theorems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=Butterfly_Theorem&diff=31453 Butterfly Theorem 2009-04-25T18:58:08Z <p>God of Math: </p> <hr /> <div>Let &lt;math&gt;D&lt;/math&gt; be the [[midpoint]] of [[chord]] &lt;math&gt;BC&lt;/math&gt; of a [[circle]], through which two other chords &lt;math&gt;EH&lt;/math&gt; and &lt;math&gt;FG&lt;/math&gt; are drawn. &lt;math&gt;EG&lt;/math&gt; and &lt;math&gt;HF&lt;/math&gt; intersect chord &lt;math&gt;BC&lt;/math&gt; at &lt;math&gt;I&lt;/math&gt; and &lt;math&gt;J&lt;/math&gt;, respectively. The '''Butterfly Theorem''' states that &lt;math&gt;D&lt;/math&gt; is the midpoint of &lt;math&gt;IJ&lt;/math&gt;.<br /> <br /> &lt;geogebra&gt;ac0eaced14d78b0f4ff370ae453962b4db309b5f&lt;/geogebra&gt; <br /> <br /> ==Proof==<br /> {{solution}}<br /> <br /> Link to a good proof : <br /> <br /> http://agutie.homestead.com/FiLEs/GeometryButterfly.html<br /> <br /> <br /> <br /> ==See also==<br /> [[Category:Geometry]]<br /> [[Category:Theorems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_2006-2007_Problems/Problem_15&diff=31452 Mock AIME 1 2006-2007 Problems/Problem 15 2009-04-25T18:52:32Z <p>God of Math: /* Solution */</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;S&lt;/math&gt; be the set of integers &lt;math&gt;0,1,2,...,10^{11}-1&lt;/math&gt;. An element &lt;math&gt;x\in S&lt;/math&gt; (in) is chosen at random. Let &lt;math&gt;\star (x)&lt;/math&gt; denote the sum of the digits of &lt;math&gt;x&lt;/math&gt;. The probability that &lt;math&gt;\star(x)&lt;/math&gt; is divisible by 11 is &lt;math&gt;\frac{m}{n}&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Compute the last 3 digits of &lt;math&gt;m+n&lt;/math&gt;<br /> ==Solution==<br /> {{solution}}<br /> <br /> <br /> Counting all &lt;math&gt;2&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, and &lt;math&gt;4&lt;/math&gt; digit combinations and then permuting only those up to &lt;math&gt;2045&lt;/math&gt;, we find that there are 186 numbers whose sums are either &lt;math&gt;11&lt;/math&gt; or &lt;math&gt;22&lt;/math&gt;. We need not account for the sum 33, as it is not achievable with a &lt;math&gt;2&lt;/math&gt; as the lowest digit. Since there are a total of &lt;math&gt;2048&lt;/math&gt; numbers and &lt;math&gt;186&lt;/math&gt; that work, we get &lt;math&gt;186/2048&lt;/math&gt; or &lt;math&gt;93/1024&lt;/math&gt;. Our sum is then &lt;math&gt;93 + 1024 = 1117&lt;/math&gt;. The last three digits are &lt;math&gt;\boxed{117}&lt;/math&gt;.<br /> <br /> <br /> ----<br /> <br /> *[[Mock AIME 1 2006-2007/Problem 14 | Previous Problem]]<br /> <br /> *[[Mock AIME 1 2006-2007]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_2006-2007_Problems/Problem_15&diff=31451 Mock AIME 1 2006-2007 Problems/Problem 15 2009-04-25T18:51:35Z <p>God of Math: /* Solution */</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;S&lt;/math&gt; be the set of integers &lt;math&gt;0,1,2,...,10^{11}-1&lt;/math&gt;. An element &lt;math&gt;x\in S&lt;/math&gt; (in) is chosen at random. Let &lt;math&gt;\star (x)&lt;/math&gt; denote the sum of the digits of &lt;math&gt;x&lt;/math&gt;. The probability that &lt;math&gt;\star(x)&lt;/math&gt; is divisible by 11 is &lt;math&gt;\frac{m}{n}&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Compute the last 3 digits of &lt;math&gt;m+n&lt;/math&gt;<br /> ==Solution==<br /> {{solution}}<br /> <br /> <br /> Counting all &lt;math&gt;2&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, and &lt;math&gt;4&lt;/math&gt; digit combinations and then permuting only those up to &lt;math&gt;2045&lt;/math&gt;, we find that there are 186 numbers whose sums are either &lt;math&gt;11&lt;/math&gt; or &lt;math&gt;22&lt;/math&gt;. We need not account for the sum 33, as it is not achievable with a &lt;math&gt;2&lt;/math&gt; as the lowest digit. Since there are a total of &lt;math&gt;2048&lt;/math&gt; numbers and &lt;math&gt;186&lt;/math&gt; that work, we get &lt;math&gt;186/2048&lt;/math&gt; or &lt;math&gt;93/1024&lt;/math&gt;. Our sum is then &lt;math&gt;93 + 1024 = 1117&lt;/math&gt;. The last three digits are &lt;math&gt;117&lt;/math&gt;.<br /> <br /> <br /> ----<br /> <br /> *[[Mock AIME 1 2006-2007/Problem 14 | Previous Problem]]<br /> <br /> *[[Mock AIME 1 2006-2007]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_2006-2007_Problems/Problem_15&diff=31450 Mock AIME 1 2006-2007 Problems/Problem 15 2009-04-25T18:50:52Z <p>God of Math: /* Solution */</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;S&lt;/math&gt; be the set of integers &lt;math&gt;0,1,2,...,10^{11}-1&lt;/math&gt;. An element &lt;math&gt;x\in S&lt;/math&gt; (in) is chosen at random. Let &lt;math&gt;\star (x)&lt;/math&gt; denote the sum of the digits of &lt;math&gt;x&lt;/math&gt;. The probability that &lt;math&gt;\star(x)&lt;/math&gt; is divisible by 11 is &lt;math&gt;\frac{m}{n}&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Compute the last 3 digits of &lt;math&gt;m+n&lt;/math&gt;<br /> ==Solution==<br /> {{solution}}<br /> <br /> ----<br /> <br /> *[[Mock AIME 1 2006-2007/Problem 14 | Previous Problem]]<br /> <br /> *[[Mock AIME 1 2006-2007]]<br /> <br /> Counting all &lt;math&gt;2&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, and &lt;math&gt;4&lt;/math&gt; digit combinations and then permuting only those up to &lt;math&gt;2045&lt;/math&gt;, we find that there are 186 numbers whose sums are either &lt;math&gt;11&lt;/math&gt; or &lt;math&gt;22&lt;/math&gt;. We need not account for the sum 33, as it is not achievable with a &lt;math&gt;2&lt;/math&gt; as the lowest digit. Since there are a total of &lt;math&gt;2048&lt;/math&gt; numbers and &lt;math&gt;186&lt;/math&gt; that work, we get &lt;math&gt;186/2048&lt;/math&gt; or &lt;math&gt;93/1024&lt;/math&gt;. Our sum is then &lt;math&gt;93 + 1024 = 1117&lt;/math&gt;. The last three digits are &lt;math&gt;117&lt;/math&gt;.</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_II_Problems/Problem_4&diff=31176 2009 AIME II Problems/Problem 4 2009-04-09T00:14:06Z <p>God of Math: /* Another Solution */</p> <hr /> <div>== Problem ==<br /> A group of children held a grape-eating contest. When the contest was over, the winner had eaten &lt;math&gt;n&lt;/math&gt; grapes, and the child in &lt;math&gt;k&lt;/math&gt;-th place had eaten &lt;math&gt;n+2-2k&lt;/math&gt; grapes. The total number of grapes eaten in the contest was &lt;math&gt;2009&lt;/math&gt;. Find the smallest possible value of &lt;math&gt;n&lt;/math&gt;.<br /> <br /> == Solution ==<br /> <br /> === Resolving the ambiguity ===<br /> <br /> The problem statement is confusing, as it can be interpreted in two ways: Either as &quot;there is a &lt;math&gt;k&gt;1&lt;/math&gt; such that the child in &lt;math&gt;k&lt;/math&gt;-th place had eaten &lt;math&gt;n+2-2k&lt;/math&gt; grapes&quot;, or &quot;for all &lt;math&gt;k&lt;/math&gt;, the child in &lt;math&gt;k&lt;/math&gt;-th place had eaten &lt;math&gt;n+2-2k&lt;/math&gt; grapes&quot;.<br /> <br /> The second meaning was apparrently the intended one. Hence we will restate the problem statement in this way:<br /> <br /> A group of &lt;math&gt;c&lt;/math&gt; children held a grape-eating contest. When the contest was over, the following was true: There was a &lt;math&gt;n&lt;/math&gt; such that for each &lt;math&gt;k&lt;/math&gt; between &lt;math&gt;1&lt;/math&gt; and &lt;math&gt;c&lt;/math&gt;, inclusive, the child in &lt;math&gt;k&lt;/math&gt;-th place had eaten exactly &lt;math&gt;n+2-2k&lt;/math&gt; grapes. The total number of grapes eaten in the contest was &lt;math&gt;2009&lt;/math&gt;. Find the smallest possible value of &lt;math&gt;n&lt;/math&gt;.<br /> <br /> === Solving this problem ===<br /> <br /> The total number of grapes eaten can be computed as the sum of the arithmetic progression with initial term &lt;math&gt;n&lt;/math&gt; (the number of grapes eaten by the child in &lt;math&gt;1&lt;/math&gt;-st place), difference &lt;math&gt;d=-2&lt;/math&gt;, and number of terms &lt;math&gt;c&lt;/math&gt;. We can easily compute that this sum is equal to &lt;math&gt;c(n-c+1)&lt;/math&gt;.<br /> <br /> Hence we have the equation &lt;math&gt;2009=c(n-c+1)&lt;/math&gt;, and we are looking for a solution &lt;math&gt;(n,c)&lt;/math&gt;, where both &lt;math&gt;n&lt;/math&gt; and &lt;math&gt;c&lt;/math&gt; are positive integers, &lt;math&gt;n\geq 2(c-1)&lt;/math&gt;, and &lt;math&gt;n&lt;/math&gt; is maximized. (The condition &lt;math&gt;n\geq 2(c-1)&lt;/math&gt; states that even the last child had to eat a non-negative number of grapes.)<br /> <br /> The prime factorization of &lt;math&gt;2009&lt;/math&gt; is &lt;math&gt;2009=7^2 \cdot 41&lt;/math&gt;. Hence there are &lt;math&gt;6&lt;/math&gt; ways how to factor &lt;math&gt;2009&lt;/math&gt; into two positive terms &lt;math&gt;c&lt;/math&gt; and &lt;math&gt;n-c+1&lt;/math&gt;:<br /> <br /> * &lt;math&gt;c=1&lt;/math&gt;, &lt;math&gt;n-c+1=2009&lt;/math&gt;, then &lt;math&gt;n=2009&lt;/math&gt; is a solution.<br /> * &lt;math&gt;c=7&lt;/math&gt;, &lt;math&gt;n-c+1=7\cdot 41=287&lt;/math&gt;, then &lt;math&gt;n=293&lt;/math&gt; is a solution.<br /> * &lt;math&gt;c=41&lt;/math&gt;, &lt;math&gt;n-c+1=7\cdot 7=49&lt;/math&gt;, then &lt;math&gt;n=89&lt;/math&gt; is a solution.<br /> * In each of the other three cases, &lt;math&gt;n&lt;/math&gt; will obviously be less than &lt;math&gt;2(c-1)&lt;/math&gt;, hence these are not valid solutions.<br /> <br /> The smallest valid solution is therefore &lt;math&gt;c=41&lt;/math&gt;, &lt;math&gt;n=\boxed{089}&lt;/math&gt;.<br /> <br /> <br /> === Another Solution ===<br /> <br /> Let us go in order of place, from &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;k&lt;/math&gt;. The first kid eats &lt;math&gt;n&lt;/math&gt; grapes, the second kid eats &lt;math&gt;n - 2&lt;/math&gt; grapes, and so on. These must sum up to 2009. Hence &lt;math&gt;n(k + 1) - 2(k)(k + 1)/2 = 2009&lt;/math&gt;, or &lt;math&gt;n(k + 1) - k(k + 1) = 2009&lt;/math&gt;. Factoring, we get &lt;math&gt;(n - k)(k + 1) = 2009&lt;/math&gt;. We are only looking for integer solutions, so we can prime factorize 2009 and look for factor pairs. &lt;math&gt;2009 = (7)*(7)*(41)&lt;/math&gt;. So &lt;math&gt;(n - k) = 2009&lt;/math&gt; and &lt;math&gt;k + 1 = 1&lt;/math&gt;, &lt;math&gt;(n - k) = 49&lt;/math&gt; and &lt;math&gt;(k + 1) = 41&lt;/math&gt;, or &lt;math&gt;(n - k) = 287&lt;/math&gt; and &lt;math&gt;(k + 1) = 7&lt;/math&gt;. The solution sets (in the form (n , k), respectively, are &lt;math&gt;(2009, 0)&lt;/math&gt;, &lt;math&gt;(293, 6)&lt;/math&gt;, and &lt;math&gt;(89, 48)&lt;/math&gt;. The pair with the smallest n value has &lt;math&gt;n=\boxed{089}&lt;/math&gt;.<br /> <br /> == See Also ==<br /> <br /> {{AIME box|year=2009|n=II|num-b=3|num-a=5}}</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_II_Problems/Problem_4&diff=31175 2009 AIME II Problems/Problem 4 2009-04-09T00:12:48Z <p>God of Math: /* Solution */</p> <hr /> <div>== Problem ==<br /> A group of children held a grape-eating contest. When the contest was over, the winner had eaten &lt;math&gt;n&lt;/math&gt; grapes, and the child in &lt;math&gt;k&lt;/math&gt;-th place had eaten &lt;math&gt;n+2-2k&lt;/math&gt; grapes. The total number of grapes eaten in the contest was &lt;math&gt;2009&lt;/math&gt;. Find the smallest possible value of &lt;math&gt;n&lt;/math&gt;.<br /> <br /> == Solution ==<br /> <br /> === Resolving the ambiguity ===<br /> <br /> The problem statement is confusing, as it can be interpreted in two ways: Either as &quot;there is a &lt;math&gt;k&gt;1&lt;/math&gt; such that the child in &lt;math&gt;k&lt;/math&gt;-th place had eaten &lt;math&gt;n+2-2k&lt;/math&gt; grapes&quot;, or &quot;for all &lt;math&gt;k&lt;/math&gt;, the child in &lt;math&gt;k&lt;/math&gt;-th place had eaten &lt;math&gt;n+2-2k&lt;/math&gt; grapes&quot;.<br /> <br /> The second meaning was apparrently the intended one. Hence we will restate the problem statement in this way:<br /> <br /> A group of &lt;math&gt;c&lt;/math&gt; children held a grape-eating contest. When the contest was over, the following was true: There was a &lt;math&gt;n&lt;/math&gt; such that for each &lt;math&gt;k&lt;/math&gt; between &lt;math&gt;1&lt;/math&gt; and &lt;math&gt;c&lt;/math&gt;, inclusive, the child in &lt;math&gt;k&lt;/math&gt;-th place had eaten exactly &lt;math&gt;n+2-2k&lt;/math&gt; grapes. The total number of grapes eaten in the contest was &lt;math&gt;2009&lt;/math&gt;. Find the smallest possible value of &lt;math&gt;n&lt;/math&gt;.<br /> <br /> === Solving this problem ===<br /> <br /> The total number of grapes eaten can be computed as the sum of the arithmetic progression with initial term &lt;math&gt;n&lt;/math&gt; (the number of grapes eaten by the child in &lt;math&gt;1&lt;/math&gt;-st place), difference &lt;math&gt;d=-2&lt;/math&gt;, and number of terms &lt;math&gt;c&lt;/math&gt;. We can easily compute that this sum is equal to &lt;math&gt;c(n-c+1)&lt;/math&gt;.<br /> <br /> Hence we have the equation &lt;math&gt;2009=c(n-c+1)&lt;/math&gt;, and we are looking for a solution &lt;math&gt;(n,c)&lt;/math&gt;, where both &lt;math&gt;n&lt;/math&gt; and &lt;math&gt;c&lt;/math&gt; are positive integers, &lt;math&gt;n\geq 2(c-1)&lt;/math&gt;, and &lt;math&gt;n&lt;/math&gt; is maximized. (The condition &lt;math&gt;n\geq 2(c-1)&lt;/math&gt; states that even the last child had to eat a non-negative number of grapes.)<br /> <br /> The prime factorization of &lt;math&gt;2009&lt;/math&gt; is &lt;math&gt;2009=7^2 \cdot 41&lt;/math&gt;. Hence there are &lt;math&gt;6&lt;/math&gt; ways how to factor &lt;math&gt;2009&lt;/math&gt; into two positive terms &lt;math&gt;c&lt;/math&gt; and &lt;math&gt;n-c+1&lt;/math&gt;:<br /> <br /> * &lt;math&gt;c=1&lt;/math&gt;, &lt;math&gt;n-c+1=2009&lt;/math&gt;, then &lt;math&gt;n=2009&lt;/math&gt; is a solution.<br /> * &lt;math&gt;c=7&lt;/math&gt;, &lt;math&gt;n-c+1=7\cdot 41=287&lt;/math&gt;, then &lt;math&gt;n=293&lt;/math&gt; is a solution.<br /> * &lt;math&gt;c=41&lt;/math&gt;, &lt;math&gt;n-c+1=7\cdot 7=49&lt;/math&gt;, then &lt;math&gt;n=89&lt;/math&gt; is a solution.<br /> * In each of the other three cases, &lt;math&gt;n&lt;/math&gt; will obviously be less than &lt;math&gt;2(c-1)&lt;/math&gt;, hence these are not valid solutions.<br /> <br /> The smallest valid solution is therefore &lt;math&gt;c=41&lt;/math&gt;, &lt;math&gt;n=\boxed{089}&lt;/math&gt;.<br /> <br /> <br /> === Another Solution ===<br /> <br /> Let us go in order of place, from &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;k&lt;/math&gt;. The first kid eats &lt;math&gt;n&lt;/math&gt; grapes, the second kid eats &lt;math&gt;n - 2&lt;/math&gt; grapes, and so on. These must sum up to 2009. Hence &lt;math&gt;n(k + 1) - 2(k)(k + 1)/2 = 2009&lt;/math&gt;, or &lt;math&gt;n(k + 1) - k(k + 1) = 2009&lt;/math&gt;. Factoring, we get &lt;math&gt;(n - k)(k + 1) = 2009&lt;/math&gt;. We are only looking for integer solutions, so we can prime factorize 2009 and look for factor pairs. &lt;math&gt;2009 = (7)*(7)*(41)&lt;/math&gt;. So &lt;math&gt;(n - k) = 2009&lt;/math&gt; and &lt;math&gt;k + 1 = 1&lt;/math&gt;, &lt;math&gt;(n - k) = 49&lt;/math&gt; and &lt;math&gt;(k + 1) = 41&lt;/math&gt;, or &lt;math&gt;(n - k) = 287 and &lt;/math&gt;(k + 1) = 7&lt;math&gt;. The solution sets (in the form (n , k), respectively, are &lt;/math&gt;(2009, 0)&lt;math&gt;, &lt;/math&gt;(293, 6)&lt;math&gt;, and &lt;/math&gt;(89, 48)&lt;math&gt;. The pair with the smallest n value has &lt;/math&gt;n=\boxed{089}.<br /> <br /> == See Also ==<br /> <br /> {{AIME box|year=2009|n=II|num-b=3|num-a=5}}</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_II_Problems/Problem_9&diff=31174 2009 AIME II Problems/Problem 9 2009-04-08T23:53:35Z <p>God of Math: /* Solution 1 */</p> <hr /> <div>== Problem ==<br /> Let &lt;math&gt;m&lt;/math&gt; be the number of solutions in positive integers to the equation &lt;math&gt;4x+3y+2z=2009&lt;/math&gt;, and let &lt;math&gt;n&lt;/math&gt; be the number of solutions in positive integers to the equation &lt;math&gt;4x+3y+2z=2000&lt;/math&gt;. Find the remainder when &lt;math&gt;m-n&lt;/math&gt; is divided by &lt;math&gt;1000&lt;/math&gt;.<br /> <br /> == Solution ==<br /> <br /> === Solution 1 ===<br /> <br /> Brute force. It is actually reasonably easy to compute &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; exactly.<br /> <br /> First, note that if &lt;math&gt;4x+3y+2z=2009&lt;/math&gt;, then &lt;math&gt;y&lt;/math&gt; must be odd. Let &lt;math&gt;y=2y'-1&lt;/math&gt;. We get &lt;math&gt;4x + 6y' - 3 + 2z = 2009, 4x + 3y' + 2z = 2012, &lt;/math&gt;and&lt;math&gt; 2x + 3y' + z = 1006&lt;/math&gt;. For any pair of positive integers &lt;math&gt;(x,y')&lt;/math&gt; such that &lt;math&gt;2x + 3y' &lt; 1006&lt;/math&gt; we have exactly one &lt;math&gt;z&lt;/math&gt; such that the equality holds. Hence we need to count the pairs &lt;math&gt;(x,y')&lt;/math&gt;. <br /> <br /> For a fixed &lt;math&gt;y'&lt;/math&gt;, &lt;math&gt;x&lt;/math&gt; can be at most &lt;math&gt;\left\lfloor \dfrac{1005-3y'}2 \right\rfloor&lt;/math&gt;. Hence the number of solutions is <br /> <br /> &lt;cmath&gt;<br /> \begin{align*}<br /> m<br /> &amp; =<br /> \sum_{y'=1}^{334} \left\lfloor \dfrac{1005-3y'}2 \right\rfloor <br /> \\<br /> &amp; = <br /> 501 + 499 + 498 + 496 + \cdots + 6 + 4 + 3 + 1 <br /> \\<br /> &amp; =<br /> 1000 + 994 + \cdots + 10 + 4<br /> \\<br /> &amp; =<br /> 83834<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> <br /> Similarly, we can compute that &lt;math&gt;n=82834&lt;/math&gt;, hence &lt;math&gt;(m-n)\bmod 1000 = 1000\bmod 1000 = \boxed{000}&lt;/math&gt;.<br /> <br /> === Solution 2 ===<br /> <br /> We can avoid computing &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt;, instead we will compute &lt;math&gt;m-n&lt;/math&gt; directly.<br /> <br /> Note that &lt;math&gt;4x+3y+2z=2009&lt;/math&gt; if and only if &lt;math&gt;4(x-1)+3(y-1)+2(z-1)=2000&lt;/math&gt;. Hence there is an almost 1-to-1 correspondence between the positive integer solutions of the two equations. The only exceptions are the solutions of the first equation in which at least one of the variables is equal to &lt;math&gt;1&lt;/math&gt;. The value &lt;math&gt;m-n&lt;/math&gt; is the number of such solutions.<br /> <br /> If &lt;math&gt;x=1&lt;/math&gt;, we get the equation &lt;math&gt;3y+2z=2005&lt;/math&gt;. The variable &lt;math&gt;y&lt;/math&gt; must be odd, and it must be between &lt;math&gt;1&lt;/math&gt; and &lt;math&gt;667&lt;/math&gt;, inclusive. For each such &lt;math&gt;y&lt;/math&gt; there is exactly one valid &lt;math&gt;z&lt;/math&gt;. Hence in this case there are &lt;math&gt;334&lt;/math&gt; valid solutions.<br /> <br /> If &lt;math&gt;y=1&lt;/math&gt;, we get the equation &lt;math&gt;4x+2z=2006&lt;/math&gt;, or equivalently &lt;math&gt;2x+z=1003&lt;/math&gt;. The variable &lt;math&gt;x&lt;/math&gt; must be between &lt;math&gt;1&lt;/math&gt; and &lt;math&gt;501&lt;/math&gt;, inclusive, and for each such &lt;math&gt;x&lt;/math&gt; there is exactly one valid &lt;math&gt;z&lt;/math&gt;. Hence in this case there are &lt;math&gt;501&lt;/math&gt; valid solutions.<br /> <br /> If &lt;math&gt;z=1&lt;/math&gt;, we get the equation &lt;math&gt;4x+3y=2007&lt;/math&gt;. The variable &lt;math&gt;y&lt;/math&gt; must be odd, thus let &lt;math&gt;y=2u-1&lt;/math&gt;. We get &lt;math&gt;4x+6u=2010&lt;/math&gt;, or equivalently, &lt;math&gt;2x+3u=1005&lt;/math&gt;. Again, we see that &lt;math&gt;u&lt;/math&gt; must be odd, thus let &lt;math&gt;u=2v-1&lt;/math&gt;. We get &lt;math&gt;2x+6v=1008&lt;/math&gt;, which simplifies to &lt;math&gt;x+3v=504&lt;/math&gt;. Now, we see that &lt;math&gt;v&lt;/math&gt; must be between &lt;math&gt;1&lt;/math&gt; and &lt;math&gt;167&lt;/math&gt;, inclusive, and for each such &lt;math&gt;v&lt;/math&gt; we have exactly one valid &lt;math&gt;x&lt;/math&gt;. Hence in this case there are &lt;math&gt;167&lt;/math&gt; valid solutions.<br /> <br /> Finally, we must note that there are two special solutions: one with &lt;math&gt;x=y=1&lt;/math&gt;, and one with &lt;math&gt;y=z=1&lt;/math&gt;. We counted each of them twice, hence we have to subtract two from the total.<br /> <br /> Therefore &lt;math&gt;m-n = 334 + 501 + 167 - 2 = 1000&lt;/math&gt;, and the answer is &lt;math&gt;1000\bmod 1000 = \boxed{000}&lt;/math&gt;.<br /> <br /> == See Also ==<br /> <br /> {{AIME box|year=2009|n=II|num-b=8|num-a=10}}</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_II_Problems/Problem_9&diff=31173 2009 AIME II Problems/Problem 9 2009-04-08T23:53:11Z <p>God of Math: /* Solution 1 */</p> <hr /> <div>== Problem ==<br /> Let &lt;math&gt;m&lt;/math&gt; be the number of solutions in positive integers to the equation &lt;math&gt;4x+3y+2z=2009&lt;/math&gt;, and let &lt;math&gt;n&lt;/math&gt; be the number of solutions in positive integers to the equation &lt;math&gt;4x+3y+2z=2000&lt;/math&gt;. Find the remainder when &lt;math&gt;m-n&lt;/math&gt; is divided by &lt;math&gt;1000&lt;/math&gt;.<br /> <br /> == Solution ==<br /> <br /> === Solution 1 ===<br /> <br /> Brute force. It is actually reasonably easy to compute &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; exactly.<br /> <br /> First, note that if &lt;math&gt;4x+3y+2z=2009&lt;/math&gt;, then &lt;math&gt;y&lt;/math&gt; must be odd. Let &lt;math&gt;y=2y'-1&lt;/math&gt;. We get &lt;math&gt;4x + 6y' - 3 + 2z = 2009, 4x + 3y' + 2z = 2012, and 2x + 3y' + z = 1006&lt;/math&gt;. For any pair of positive integers &lt;math&gt;(x,y')&lt;/math&gt; such that &lt;math&gt;2x + 3y' &lt; 1006&lt;/math&gt; we have exactly one &lt;math&gt;z&lt;/math&gt; such that the equality holds. Hence we need to count the pairs &lt;math&gt;(x,y')&lt;/math&gt;. <br /> <br /> For a fixed &lt;math&gt;y'&lt;/math&gt;, &lt;math&gt;x&lt;/math&gt; can be at most &lt;math&gt;\left\lfloor \dfrac{1005-3y'}2 \right\rfloor&lt;/math&gt;. Hence the number of solutions is <br /> <br /> &lt;cmath&gt;<br /> \begin{align*}<br /> m<br /> &amp; =<br /> \sum_{y'=1}^{334} \left\lfloor \dfrac{1005-3y'}2 \right\rfloor <br /> \\<br /> &amp; = <br /> 501 + 499 + 498 + 496 + \cdots + 6 + 4 + 3 + 1 <br /> \\<br /> &amp; =<br /> 1000 + 994 + \cdots + 10 + 4<br /> \\<br /> &amp; =<br /> 83834<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> <br /> Similarly, we can compute that &lt;math&gt;n=82834&lt;/math&gt;, hence &lt;math&gt;(m-n)\bmod 1000 = 1000\bmod 1000 = \boxed{000}&lt;/math&gt;.<br /> <br /> === Solution 2 ===<br /> <br /> We can avoid computing &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt;, instead we will compute &lt;math&gt;m-n&lt;/math&gt; directly.<br /> <br /> Note that &lt;math&gt;4x+3y+2z=2009&lt;/math&gt; if and only if &lt;math&gt;4(x-1)+3(y-1)+2(z-1)=2000&lt;/math&gt;. Hence there is an almost 1-to-1 correspondence between the positive integer solutions of the two equations. The only exceptions are the solutions of the first equation in which at least one of the variables is equal to &lt;math&gt;1&lt;/math&gt;. The value &lt;math&gt;m-n&lt;/math&gt; is the number of such solutions.<br /> <br /> If &lt;math&gt;x=1&lt;/math&gt;, we get the equation &lt;math&gt;3y+2z=2005&lt;/math&gt;. The variable &lt;math&gt;y&lt;/math&gt; must be odd, and it must be between &lt;math&gt;1&lt;/math&gt; and &lt;math&gt;667&lt;/math&gt;, inclusive. For each such &lt;math&gt;y&lt;/math&gt; there is exactly one valid &lt;math&gt;z&lt;/math&gt;. Hence in this case there are &lt;math&gt;334&lt;/math&gt; valid solutions.<br /> <br /> If &lt;math&gt;y=1&lt;/math&gt;, we get the equation &lt;math&gt;4x+2z=2006&lt;/math&gt;, or equivalently &lt;math&gt;2x+z=1003&lt;/math&gt;. The variable &lt;math&gt;x&lt;/math&gt; must be between &lt;math&gt;1&lt;/math&gt; and &lt;math&gt;501&lt;/math&gt;, inclusive, and for each such &lt;math&gt;x&lt;/math&gt; there is exactly one valid &lt;math&gt;z&lt;/math&gt;. Hence in this case there are &lt;math&gt;501&lt;/math&gt; valid solutions.<br /> <br /> If &lt;math&gt;z=1&lt;/math&gt;, we get the equation &lt;math&gt;4x+3y=2007&lt;/math&gt;. The variable &lt;math&gt;y&lt;/math&gt; must be odd, thus let &lt;math&gt;y=2u-1&lt;/math&gt;. We get &lt;math&gt;4x+6u=2010&lt;/math&gt;, or equivalently, &lt;math&gt;2x+3u=1005&lt;/math&gt;. Again, we see that &lt;math&gt;u&lt;/math&gt; must be odd, thus let &lt;math&gt;u=2v-1&lt;/math&gt;. We get &lt;math&gt;2x+6v=1008&lt;/math&gt;, which simplifies to &lt;math&gt;x+3v=504&lt;/math&gt;. Now, we see that &lt;math&gt;v&lt;/math&gt; must be between &lt;math&gt;1&lt;/math&gt; and &lt;math&gt;167&lt;/math&gt;, inclusive, and for each such &lt;math&gt;v&lt;/math&gt; we have exactly one valid &lt;math&gt;x&lt;/math&gt;. Hence in this case there are &lt;math&gt;167&lt;/math&gt; valid solutions.<br /> <br /> Finally, we must note that there are two special solutions: one with &lt;math&gt;x=y=1&lt;/math&gt;, and one with &lt;math&gt;y=z=1&lt;/math&gt;. We counted each of them twice, hence we have to subtract two from the total.<br /> <br /> Therefore &lt;math&gt;m-n = 334 + 501 + 167 - 2 = 1000&lt;/math&gt;, and the answer is &lt;math&gt;1000\bmod 1000 = \boxed{000}&lt;/math&gt;.<br /> <br /> == See Also ==<br /> <br /> {{AIME box|year=2009|n=II|num-b=8|num-a=10}}</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_II_Problems/Problem_1&diff=31172 2009 AIME II Problems/Problem 1 2009-04-08T20:01:18Z <p>God of Math: /* Solution 2 */</p> <hr /> <div>== Problem ==<br /> Before starting to paint, Bill had &lt;math&gt;130&lt;/math&gt; ounces of blue paint, &lt;math&gt;164&lt;/math&gt; ounces of red paint, and &lt;math&gt;188&lt;/math&gt; ounces of white paint. Bill painted four equally sized stripes on a wall, making a blue stripe, a red stripe, a white stripe, and a pink stripe. Pink is a mixture of red and white, not necessarily in equal amounts. When Bill finished, he had equal amounts of blue, red, and white paint left. Find the total number of ounces of paint Bill had left.<br /> <br /> == Solution ==<br /> After the pink stripe is drawn, all three colors will be used equally so the pink stripe must bring the amount of red and white paint down to &lt;math&gt;130&lt;/math&gt; ounces each. Say &lt;math&gt;a&lt;/math&gt; is the fraction of the pink paint that is red paint and &lt;math&gt;x&lt;/math&gt; is the size of each stripe. Then equations can be written: &lt;math&gt;ax = 164 - 130 = 34&lt;/math&gt; and &lt;math&gt;(1-a)x = 188 - 130 = 58&lt;/math&gt;. The second equation becomes &lt;math&gt;x - ax = 58&lt;/math&gt; and substituting the first equation into this one we get &lt;math&gt;x - 34 = 58&lt;/math&gt; so &lt;math&gt;x = 92&lt;/math&gt;. The amount of each color left over at the end is thus &lt;math&gt;130 - 92 = 38&lt;/math&gt; and &lt;math&gt;38 * 3 = \boxed{114}&lt;/math&gt;.<br /> <br /> == Solution 2 ==<br /> <br /> We know that all the stripes are of equal size. We can then say that &lt;math&gt;r&lt;/math&gt; is the amount of pain per stripe. Then &lt;math&gt;130 - r&lt;/math&gt; will be the amount of blue paint left. Now for the other two stripes. The amount of white paint left after the white stripe and the amount of red paint left after the blue stripe are &lt;math&gt;188 - r&lt;/math&gt; and &lt;math&gt;164 - r&lt;/math&gt; respectively. The pink stripe is also r ounces of paint, but let there be &lt;math&gt;k&lt;/math&gt; ounces of red paint in the mixture and &lt;math&gt;r - k&lt;/math&gt; ounces of white paint. We now have two equations: &lt;math&gt;164 - r - k = 188 - r - (r-k)&lt;/math&gt; and &lt;math&gt;164 - r - k = 130 - r&lt;/math&gt;. Solving yields k = 34 and r = 92. We now see that there will be &lt;math&gt;130 - 92 = 38&lt;/math&gt; ounces of paint left in each can. &lt;math&gt;38 * 3 = \boxed{114}&lt;/math&gt;<br /> <br /> == See Also ==<br /> <br /> {{AIME box|year=2009|n=II|before=First Question|num-a=2}}</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_II_Problems/Problem_1&diff=31171 2009 AIME II Problems/Problem 1 2009-04-08T20:00:52Z <p>God of Math: /* Solution 2 */</p> <hr /> <div>== Problem ==<br /> Before starting to paint, Bill had &lt;math&gt;130&lt;/math&gt; ounces of blue paint, &lt;math&gt;164&lt;/math&gt; ounces of red paint, and &lt;math&gt;188&lt;/math&gt; ounces of white paint. Bill painted four equally sized stripes on a wall, making a blue stripe, a red stripe, a white stripe, and a pink stripe. Pink is a mixture of red and white, not necessarily in equal amounts. When Bill finished, he had equal amounts of blue, red, and white paint left. Find the total number of ounces of paint Bill had left.<br /> <br /> == Solution ==<br /> After the pink stripe is drawn, all three colors will be used equally so the pink stripe must bring the amount of red and white paint down to &lt;math&gt;130&lt;/math&gt; ounces each. Say &lt;math&gt;a&lt;/math&gt; is the fraction of the pink paint that is red paint and &lt;math&gt;x&lt;/math&gt; is the size of each stripe. Then equations can be written: &lt;math&gt;ax = 164 - 130 = 34&lt;/math&gt; and &lt;math&gt;(1-a)x = 188 - 130 = 58&lt;/math&gt;. The second equation becomes &lt;math&gt;x - ax = 58&lt;/math&gt; and substituting the first equation into this one we get &lt;math&gt;x - 34 = 58&lt;/math&gt; so &lt;math&gt;x = 92&lt;/math&gt;. The amount of each color left over at the end is thus &lt;math&gt;130 - 92 = 38&lt;/math&gt; and &lt;math&gt;38 * 3 = \boxed{114}&lt;/math&gt;.<br /> <br /> == Solution 2 ==<br /> <br /> We know that all the stripes are of equal size. We can then say that &lt;math&gt;r&lt;/math&gt; is the amount of pain per stripe. Then &lt;math&gt;130 - r&lt;/math&gt; will be the amount of blue paint left. Now for the other two stripes. The amount of white paint left after the white stripe and the amount of red paint left after the blue stripe are &lt;math&gt;188 - r&lt;/math&gt; and &lt;math&gt;164 - r&lt;/math&gt; respectively. The pink stripe is also r ounces of paint, but let there be &lt;math&gt;k&lt;/math&gt; ounces of red paint in the mixture and &lt;math&gt;r - k&lt;/math&gt; ounces of white paint. We now have two equations: &lt;math&gt;164 - r - k = 188 - r - (r-k)&lt;/math&gt; and &lt;math&gt;164 - r - k = 130 - r&lt;/math&gt;. Solving yields k = 34 and r = 92. We now see that there will be &lt;math&gt;130 - 92 = 38&lt;/math&gt; ounces of paint left in each can. &lt;math&gt;38 * 3&lt;/math&gt; = \boxed{114}<br /> <br /> == See Also ==<br /> <br /> {{AIME box|year=2009|n=II|before=First Question|num-a=2}}</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_II_Problems/Problem_1&diff=31170 2009 AIME II Problems/Problem 1 2009-04-08T20:00:15Z <p>God of Math: /* Solution 2 */</p> <hr /> <div>== Problem ==<br /> Before starting to paint, Bill had &lt;math&gt;130&lt;/math&gt; ounces of blue paint, &lt;math&gt;164&lt;/math&gt; ounces of red paint, and &lt;math&gt;188&lt;/math&gt; ounces of white paint. Bill painted four equally sized stripes on a wall, making a blue stripe, a red stripe, a white stripe, and a pink stripe. Pink is a mixture of red and white, not necessarily in equal amounts. When Bill finished, he had equal amounts of blue, red, and white paint left. Find the total number of ounces of paint Bill had left.<br /> <br /> == Solution ==<br /> After the pink stripe is drawn, all three colors will be used equally so the pink stripe must bring the amount of red and white paint down to &lt;math&gt;130&lt;/math&gt; ounces each. Say &lt;math&gt;a&lt;/math&gt; is the fraction of the pink paint that is red paint and &lt;math&gt;x&lt;/math&gt; is the size of each stripe. Then equations can be written: &lt;math&gt;ax = 164 - 130 = 34&lt;/math&gt; and &lt;math&gt;(1-a)x = 188 - 130 = 58&lt;/math&gt;. The second equation becomes &lt;math&gt;x - ax = 58&lt;/math&gt; and substituting the first equation into this one we get &lt;math&gt;x - 34 = 58&lt;/math&gt; so &lt;math&gt;x = 92&lt;/math&gt;. The amount of each color left over at the end is thus &lt;math&gt;130 - 92 = 38&lt;/math&gt; and &lt;math&gt;38 * 3 = \boxed{114}&lt;/math&gt;.<br /> <br /> == Solution 2 ==<br /> <br /> We know that all the stripes are of equal size. We can then say that &lt;math&gt;r&lt;/math&gt; is the amount of pain per stripe. Then &lt;math&gt;130 - r&lt;/math&gt; will be the amount of blue paint left. Now for the other two stripes. The amount of white paint left after the white stripe and the amount of red paint left after the blue stripe are &lt;math&gt;188 - r&lt;/math&gt; and &lt;math&gt;164 - r&lt;/math&gt; respectively. The pink stripe is also r ounces of paint, but let there be &lt;math&gt;k&lt;/math&gt; ounces of red paint in the mixture and &lt;math&gt;r - k&lt;/math&gt; ounces of white paint. We now have two equations: &lt;math&gt;164 - r - k = 188 - r - (r-k)&lt;/math&gt; and &lt;math&gt;164 - r - k = 130 - r&lt;/math&gt;. Solving yields k = 34 and r = 92. We now see that there will be &lt;math&gt;130 - 92 = 38&lt;/math&gt; ounces of paint left in each can. &lt;math&gt;38&lt;/math&gt; ounces * &lt;math&gt;3&lt;/math&gt; cans = \boxed{114}\$<br /> <br /> == See Also ==<br /> <br /> {{AIME box|year=2009|n=II|before=First Question|num-a=2}}</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_II_Problems/Problem_1&diff=31169 2009 AIME II Problems/Problem 1 2009-04-08T19:59:59Z <p>God of Math: /* Solution 2 */</p> <hr /> <div>== Problem ==<br /> Before starting to paint, Bill had &lt;math&gt;130&lt;/math&gt; ounces of blue paint, &lt;math&gt;164&lt;/math&gt; ounces of red paint, and &lt;math&gt;188&lt;/math&gt; ounces of white paint. Bill painted four equally sized stripes on a wall, making a blue stripe, a red stripe, a white stripe, and a pink stripe. Pink is a mixture of red and white, not necessarily in equal amounts. When Bill finished, he had equal amounts of blue, red, and white paint left. Find the total number of ounces of paint Bill had left.<br /> <br /> == Solution ==<br /> After the pink stripe is drawn, all three colors will be used equally so the pink stripe must bring the amount of red and white paint down to &lt;math&gt;130&lt;/math&gt; ounces each. Say &lt;math&gt;a&lt;/math&gt; is the fraction of the pink paint that is red paint and &lt;math&gt;x&lt;/math&gt; is the size of each stripe. Then equations can be written: &lt;math&gt;ax = 164 - 130 = 34&lt;/math&gt; and &lt;math&gt;(1-a)x = 188 - 130 = 58&lt;/math&gt;. The second equation becomes &lt;math&gt;x - ax = 58&lt;/math&gt; and substituting the first equation into this one we get &lt;math&gt;x - 34 = 58&lt;/math&gt; so &lt;math&gt;x = 92&lt;/math&gt;. The amount of each color left over at the end is thus &lt;math&gt;130 - 92 = 38&lt;/math&gt; and &lt;math&gt;38 * 3 = \boxed{114}&lt;/math&gt;.<br /> <br /> == Solution 2 ==<br /> <br /> We know that all the stripes are of equal size. We can then say that &lt;math&gt;r&lt;/math&gt; is the amount of pain per stripe. Then &lt;math&gt;130 - r&lt;/math&gt; will be the amount of blue paint left. Now for the other two stripes. The amount of white paint left after the white stripe and the amount of red paint left after the blue stripe are &lt;math&gt;188 - r&lt;/math&gt; and &lt;math&gt;164 - r&lt;/math&gt; respectively. The pink stripe is also r ounces of paint, but let there be &lt;math&gt;k&lt;/math&gt; ounces of red paint in the mixture and &lt;math&gt;r - k&lt;/math&gt; ounces of white paint. We now have two equations: &lt;math&gt;164 - r - k = 188 - r - (r-k)&lt;/math&gt; and &lt;math&gt;164 - r - k = 130 - r&lt;/math&gt;. Solving yields k = 34 and r = 92. We now see that there will be &lt;math&gt;130 - 92 = 38&lt;/math&gt; ounces of paint left in each can. &lt;math&gt;38 ounces * 3 cans = \boxed{114}&lt;/math&gt;<br /> <br /> == See Also ==<br /> <br /> {{AIME box|year=2009|n=II|before=First Question|num-a=2}}</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_II_Problems/Problem_1&diff=31168 2009 AIME II Problems/Problem 1 2009-04-08T19:59:33Z <p>God of Math: /* Solution */</p> <hr /> <div>== Problem ==<br /> Before starting to paint, Bill had &lt;math&gt;130&lt;/math&gt; ounces of blue paint, &lt;math&gt;164&lt;/math&gt; ounces of red paint, and &lt;math&gt;188&lt;/math&gt; ounces of white paint. Bill painted four equally sized stripes on a wall, making a blue stripe, a red stripe, a white stripe, and a pink stripe. Pink is a mixture of red and white, not necessarily in equal amounts. When Bill finished, he had equal amounts of blue, red, and white paint left. Find the total number of ounces of paint Bill had left.<br /> <br /> == Solution ==<br /> After the pink stripe is drawn, all three colors will be used equally so the pink stripe must bring the amount of red and white paint down to &lt;math&gt;130&lt;/math&gt; ounces each. Say &lt;math&gt;a&lt;/math&gt; is the fraction of the pink paint that is red paint and &lt;math&gt;x&lt;/math&gt; is the size of each stripe. Then equations can be written: &lt;math&gt;ax = 164 - 130 = 34&lt;/math&gt; and &lt;math&gt;(1-a)x = 188 - 130 = 58&lt;/math&gt;. The second equation becomes &lt;math&gt;x - ax = 58&lt;/math&gt; and substituting the first equation into this one we get &lt;math&gt;x - 34 = 58&lt;/math&gt; so &lt;math&gt;x = 92&lt;/math&gt;. The amount of each color left over at the end is thus &lt;math&gt;130 - 92 = 38&lt;/math&gt; and &lt;math&gt;38 * 3 = \boxed{114}&lt;/math&gt;.<br /> <br /> == Solution 2 ==<br /> <br /> We know that all the stripes are of equal size. We can then say that &lt;math&gt;r&lt;/math&gt; is the amount of pain per stripe. Then &lt;math&gt;130 - r&lt;/math&gt; will be the amount of blue paint left. Now for the other two stripes. The amount of white paint left after the white stripe and the amount of red paint left after the blue stripe are &lt;math&gt;188 - r&lt;/math&gt; and &lt;math&gt;164 - r&lt;/math&gt; respectively. The pink stripe is also r ounces of paint, but let there be &lt;math&gt;k&lt;/math&gt; ounces of red paint in the mixture and &lt;math&gt;r - k&lt;/math&gt; ounces of white paint. We now have two equations: &lt;math&gt;164 - r - k = 188 - r - (r-k)&lt;/math&gt; and &lt;math&gt;164 - r - k = 130 - r&lt;/math&gt;. Solving yields k = 34 and r = 92. We now see that there will be &lt;math&gt;130 - 92 = 38&lt;/math&gt; ounces of paint left in each can. &lt;math&gt;38 * 3 = \boxed{114}&lt;/math&gt;<br /> <br /> == See Also ==<br /> <br /> {{AIME box|year=2009|n=II|before=First Question|num-a=2}}</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1984_AIME_Problems/Problem_2&diff=30926 1984 AIME Problems/Problem 2 2009-03-21T21:09:20Z <p>God of Math: /* Solution */</p> <hr /> <div>== Problem ==<br /> The [[integer]] &lt;math&gt;\displaystyle n&lt;/math&gt; is the smallest [[positive]] [[multiple]] of &lt;math&gt;\displaystyle 15&lt;/math&gt; such that every [[digit]] of &lt;math&gt;\displaystyle n&lt;/math&gt; is either &lt;math&gt;\displaystyle 8&lt;/math&gt; or &lt;math&gt;\displaystyle 0&lt;/math&gt;. Compute &lt;math&gt;\frac{n}{15}&lt;/math&gt;.<br /> <br /> == Solution ==<br /> Any multiple of 15 is a multiple of 5 and a multiple of 3. <br /> <br /> Any multiple of 5 ends in 0 or 5; since &lt;math&gt;n&lt;/math&gt; only contains the digits 0 and 8, the units [[digit]] of &lt;math&gt;n&lt;/math&gt; must be 0. <br /> <br /> The sum of the digits of any multiple of 3 must be [[divisible]] by 3. If &lt;math&gt;n&lt;/math&gt; has &lt;math&gt;a&lt;/math&gt; digits equal to 8, the sum of the digits of &lt;math&gt;n&lt;/math&gt; is &lt;math&gt;8a&lt;/math&gt;. For this number to be divisible by 3, &lt;math&gt;a&lt;/math&gt; must be divisible by 3. Thus &lt;math&gt;n&lt;/math&gt; must have at least three copies of the digit 8. <br /> <br /> The smallest number which meets these two requirements is 8880. Thus the answer is &lt;math&gt;\frac{8880}{15} = \boxed{592}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=1984|num-b=1|num-a=3}}<br /> * [[AIME Problems and Solutions]]<br /> * [[American Invitational Mathematics Examination]]<br /> * [[Mathematics competition resources]]<br /> <br /> [[Category:Intermediate Number Theory Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1984_AIME_Problems/Problem_1&diff=30925 1984 AIME Problems/Problem 1 2009-03-21T21:04:32Z <p>God of Math: /* Solution */</p> <hr /> <div>== Problem ==<br /> Find the value of &lt;math&gt;\displaystyle a_2+a_4+a_6+a_8+\ldots+a_{98}&lt;/math&gt; if &lt;math&gt;\displaystyle a_1&lt;/math&gt;, &lt;math&gt;\displaystyle a_2&lt;/math&gt;, &lt;math&gt;\displaystyle a_3\ldots&lt;/math&gt; is an [[arithmetic progression]] with common difference 1, and &lt;math&gt;\displaystyle a_1+a_2+a_3+\ldots+a_{98}=137&lt;/math&gt;.<br /> <br /> == Solution ==<br /> One approach to this problem is to apply the formula for the sum of an [[arithmetic series]] in order to find the value of &lt;math&gt;a_1&lt;/math&gt;, then use that to calculate &lt;math&gt;a_2&lt;/math&gt; and sum another arithmetic series to get our answer.<br /> <br /> A somewhat quicker method is to do the following: for each &lt;math&gt;n \geq 1&lt;/math&gt;, we have &lt;math&gt;a_{2n - 1} = a_{2n} - 1&lt;/math&gt;. We can substitute this into our given equation to get &lt;math&gt;(a_2 - 1) + a_2 + (a_4 - 1) + a_4 + \ldots + (a_{98} - 1) + a_{98} = 137&lt;/math&gt;. The left-hand side of this equation is simply &lt;math&gt;2(a_2 + a_4 + \ldots + a_{98}) - 49&lt;/math&gt;, so our desired value is &lt;math&gt;\frac{137 + 49}{2} = \boxed{093}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=1984|before=First Question|num-a=2}}<br /> * [[AIME Problems and Solutions]]<br /> * [[American Invitational Mathematics Examination]]<br /> * [[Mathematics competition resources]]<br /> <br /> [[Category:Intermediate Algebra Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1984_AIME_Problems/Problem_15&diff=30924 1984 AIME Problems/Problem 15 2009-03-21T21:03:02Z <p>God of Math: /* Solution 2 */</p> <hr /> <div>== Problem ==<br /> Determine &lt;math&gt;w^2+x^2+y^2+z^2&lt;/math&gt; if<br /> <br /> &lt;div style=&quot;text-align:center;&quot;&gt;&lt;math&gt; \frac{x^2}{2^2-1}+\frac{y^2}{2^2-3^2}+\frac{z^2}{2^2-5^2}+\frac{w^2}{2^2-7^2}=1 &lt;/math&gt;&lt;br /&gt;&lt;math&gt; \frac{x^2}{4^2-1}+\frac{y^2}{4^2-3^2}+\frac{z^2}{4^2-5^2}+\frac{w^2}{4^2-7^2}=1 &lt;/math&gt;&lt;br /&gt;&lt;math&gt; \frac{x^2}{6^2-1}+\frac{y^2}{6^2-3^2}+\frac{z^2}{6^2-5^2}+\frac{w^2}{6^2-7^2}=1 &lt;/math&gt;&lt;br /&gt;&lt;math&gt; \frac{x^2}{8^2-1}+\frac{y^2}{8^2-3^2}+\frac{z^2}{8^2-5^2}+\frac{w^2}{8^2-7^2}=1 &lt;/math&gt;&lt;/div&gt;<br /> <br /> == Solution 1 ==<br /> For each of the values &lt;math&gt;t=4,16,36,64&lt;/math&gt;, we have the [[equation]]<br /> <br /> &lt;div style=&quot;text-align:center;&quot;&gt;&lt;math&gt;x^2(t-9)(t-25)(t-49)+y^2(t-1)(t-25)(t-49)&lt;/math&gt; &lt;math&gt;+z^2(t-1)(t-9)(t-49)+w^2(t-1)(t-9)(t-25)&lt;/math&gt;<br /> &lt;math&gt;=(t-1)(t-9)(t-25)(t-49)-(t-4)(t-16)(t-36)(t-64)&lt;/math&gt;<br /> &lt;/div&gt;<br /> <br /> However, each side of the equation is a [[polynomial]] in &lt;math&gt;t&lt;/math&gt; of degree at most 3, and they have 4 common roots. Therefore, the polynomials must be equal.<br /> <br /> Now we can plug in &lt;math&gt;t=1&lt;/math&gt; into the polynomial equation. Most terms drop, and we end up with<br /> <br /> &lt;cmath&gt;x^2(-8)(-24)(-48)=-(-3)(-15)(-35)(-63)&lt;/cmath&gt;<br /> <br /> so that<br /> <br /> &lt;cmath&gt;x^2=\frac{3\cdot 15\cdot 35\cdot 63}{8\cdot 24\cdot 48}=\frac{3^2\cdot 5^2\cdot 7^2}{2^{10}}&lt;/cmath&gt;<br /> <br /> Similarly, we can plug in &lt;math&gt;t=9,25,49&lt;/math&gt; and get<br /> <br /> &lt;cmath&gt;\begin{align*}<br /> y^2&amp;=\frac{5\cdot 7\cdot 27\cdot 55}{8\cdot 16\cdot 40}=\frac{3^3\cdot 5\cdot 7\cdot 11}{2^{10}}\\<br /> z^2&amp;=\frac{21\cdot 9\cdot 11\cdot 39}{24\cdot 16\cdot 24}=\frac{3^2\cdot 7\cdot 11\cdot 13}{2^{10}}\\<br /> w^2&amp;=\frac{45\cdot 33\cdot 13\cdot 15}{48\cdot 40\cdot 24}=\frac{3^2\cdot 5\cdot 11\cdot 13}{2^{10}}&lt;/cmath&gt;<br /> <br /> Now adding them up,<br /> <br /> &lt;cmath&gt;\begin{align*}z^2+w^2&amp;=\frac{3^2\cdot 11\cdot 13(7+5)}{2^{10}}=\frac{3^3\cdot 11\cdot 13}{2^8}\\<br /> x^2+y^2&amp;=\frac{3^2\cdot 5\cdot 7(5\cdot 7+3\cdot 11)}{2^{10}}=\frac{3^2\cdot 5\cdot 7\cdot 17}{2^8}\end{align*}&lt;/cmath&gt;<br /> <br /> with a sum of<br /> <br /> &lt;cmath&gt;\frac{3^2(3\cdot 11\cdot 13+5\cdot 7\cdot 17)}{2^8}=3^2\cdot 4=\boxed{036}.&lt;/cmath&gt;<br /> <br /> == Solution 2 ==<br /> As in Solution 1, we have <br /> &lt;div style=&quot;text-align:center;&quot;&gt;&lt;math&gt;(t-1)(t-9)(t-25)(t-49)-x^2(t-9)(t-25)(t-49)-y^2(t-1)(t-25)(t-49)&lt;/math&gt; &lt;math&gt;-z^2(t-1)(t-9)(t-49)-w^2(t-1)(t-9)(t-25)&lt;/math&gt;<br /> &lt;math&gt;=(t-4)(t-16)(t-36)(t-64)&lt;/math&gt;<br /> &lt;/div&gt;<br /> Now the coefficient of &lt;math&gt;t^3&lt;/math&gt; on both sides must be equal. Therefore we have &lt;math&gt;1+9+25+49+x^2+y^2+z^2+w^2=4+16+36+64\implies x^2+y^2+z^2+w^2=\boxed{036}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=1984|num-b=14|after=Last Question}}<br /> <br /> [[Category:Intermediate Algebra Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=1984_AIME_Problems/Problem_3&diff=30920 1984 AIME Problems/Problem 3 2009-03-21T20:57:05Z <p>God of Math: /* Solution */</p> <hr /> <div>== Problem ==<br /> A [[point]] &lt;math&gt;P&lt;/math&gt; is chosen in the interior of &lt;math&gt;\triangle ABC&lt;/math&gt; such that when [[line]]s are drawn through &lt;math&gt;P&lt;/math&gt; [[parallel]] to the sides of &lt;math&gt;\triangle ABC&lt;/math&gt;, the resulting smaller [[triangle]]s &lt;math&gt;t_{1}&lt;/math&gt;, &lt;math&gt;t_{2}&lt;/math&gt;, and &lt;math&gt;t_{3}&lt;/math&gt; in the figure, have [[area]]s &lt;math&gt;4&lt;/math&gt;, &lt;math&gt;9&lt;/math&gt;, and &lt;math&gt;49&lt;/math&gt;, respectively. Find the area of &lt;math&gt;\triangle ABC&lt;/math&gt;.<br /> &lt;center&gt;&lt;asy&gt;<br /> size(200);<br /> pathpen=black;pointpen=black;<br /> pair A=(0,0),B=(12,0),C=(4,5);<br /> D(A--B--C--cycle); D(A+(B-A)*3/4--A+(C-A)*3/4); D(B+(C-B)*5/6--B+(A-B)*5/6);D(C+(B-C)*5/12--C+(A-C)*5/12);<br /> MP(&quot;A&quot;,C,N);MP(&quot;B&quot;,A,SW);MP(&quot;C&quot;,B,SE); /* sorry mixed up points according to resources diagram. */<br /> MP(&quot;t_3&quot;,(A+B+(B-A)*3/4+(A-B)*5/6)/2+(-1,0.8),N);<br /> MP(&quot;t_2&quot;,(B+C+(B-C)*5/12+(C-B)*5/6)/2+(-0.3,0.1),WSW);<br /> MP(&quot;t_1&quot;,(A+C+(C-A)*3/4+(A-C)*5/12)/2+(0,0.15),ESE);<br /> &lt;/asy&gt;&lt;/center&gt;<br /> <br /> == Solution ==<br /> By the transversals that go through &lt;math&gt;P&lt;/math&gt;, all four triangles are [[similar triangles|similar]] to each other by the &lt;math&gt;AA&lt;/math&gt; postulate. Also, note that the length of any one side of the larger triangle is equation to the sum of the sides of each of the corresponding sides on the smaller triangles. We use the identity &lt;math&gt;K = absinC&lt;/math&gt; to show that the areas are proportional (the sides are proportional and the angles are equal) Hence, we can write the lengths of corresponding sides of the triangle as &lt;math&gt;2x,\ 3x,\ 7x&lt;/math&gt;. Thus, the corresponding side on the large triangle is &lt;math&gt;12x&lt;/math&gt;, and the area of the triangle is &lt;math&gt;12^2 = \boxed{144}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=1984|num-b=2|num-a=4}}<br /> <br /> [[Category:Intermediate Geometry Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_I_Problems/Problem_1&diff=30874 2009 AIME I Problems/Problem 1 2009-03-21T02:14:25Z <p>God of Math: /* Solution */</p> <hr /> <div><br /> == Problem ==<br /> <br /> Call a &lt;math&gt;3&lt;/math&gt;-digit number ''geometric'' if it has &lt;math&gt;3&lt;/math&gt; distinct digits which, when read from left to right, form a geometric sequence. Find the difference between the largest and smallest geometric numbers.<br /> <br /> == Solution ==<br /> <br /> Assume that the largest geometric number starts with a nine. We know that the common ratio must be k/3, because a whole number should be attained for the 3rd term as well. When k = 1, the number is &lt;math&gt;931&lt;/math&gt;. When k = 2, the number is 964. When k = 3, we get &lt;math&gt;999&lt;/math&gt;, but the integers must be distinct. By the same logic, the smallest geometric number is &lt;math&gt;124&lt;/math&gt;. The largest geometric number is &lt;math&gt;964&lt;/math&gt; and the smallest is &lt;math&gt;124&lt;/math&gt;. Thus the difference is &lt;math&gt;964 - 124 = \boxed{840}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=2009|n=I|before=First Question|num-a=2}}<br /> <br /> [[Category:Intermediate Number Theory Problems]]</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_I_Problems/Problem_9&diff=30840 2009 AIME I Problems/Problem 9 2009-03-21T00:11:27Z <p>God of Math: New page: We are given the 7 digits of the values, so let us find the ways we can distrubute these digits among the prizes. We are supposed to find the ways to group the digits such that each price ...</p> <hr /> <div>We are given the 7 digits of the values, so let us find the ways we can distrubute these digits among the prizes. We are supposed to find the ways to group the digits such that each price has at least one digit, and no prices have 5 or more digits. We can express 7 this way as :<br /> <br /> 4, 2, 1<br /> 3, 3, 1<br /> 3, 2, 2<br /> <br /> Let us begin with the first case. The possibilities are like so:<br /> *When we construct the table for the 1 and 2 digit numbers, we just permute the other 4 to find the choices for the 4 digit number<br /> <br /> 1 digit number 2 digit number 4 digit number<br /> <br /> 1 11 4 choose 1, or 4 numbers<br /> 1 13 4 choose 2, or 6 numbers<br /> 1 31 4 choose 2, or 6 numbers <br /> 1 33 4 choose 3, or 4 numbers<br /> 3 11 4 choose 2, or 6 numbers<br /> 3 13 4 choose 3, or 4 numbers<br /> 3 31 4 choose 3, or 4 numbers<br /> 3 33 4 choose 4, or 1 number<br /> --------------------------------------------------------------</div> God of Math https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_I_Problems/Problem_4&diff=30839 2009 AIME I Problems/Problem 4 2009-03-20T23:58:16Z <p>God of Math: /* Solution */</p> <hr /> <div>== Problem 4 ==<br /> In parallelogram &lt;math&gt;ABCD&lt;/math&gt;, point &lt;math&gt;M&lt;/math&gt; is on &lt;math&gt;\overline{AB}&lt;/math&gt; so that &lt;math&gt;\frac {AM}{AB} = \frac {17}{1000}&lt;/math&gt; and point &lt;math&gt;N&lt;/math&gt; is on &lt;math&gt;\overline{AD}&lt;/math&gt; so that &lt;math&gt;\frac {AN}{AD} = \frac {17}{2009}&lt;/math&gt;. Let &lt;math&gt;P&lt;/math&gt; be the point of intersection of &lt;math&gt;\overline{AC}&lt;/math&gt; and &lt;math&gt;\overline{MN}&lt;/math&gt;. Find &lt;math&gt;\frac {AC}{AP}&lt;/math&gt;.<br /> <br /> [[2009 AIME I Problems/Problem 4|Solution]]<br /> <br /> ==Solution==<br /> <br /> One of the ways to solve this problem is to make this parallelogram a straight line.<br /> <br /> So the whole length of the line&lt;math&gt;(AP)&lt;/math&gt; is &lt;math&gt;1000+2009=3009units&lt;/math&gt;<br /> <br /> And &lt;math&gt;AC&lt;/math&gt; will be &lt;math&gt;17 units&lt;/math&gt;<br /> <br /> So the answer is &lt;math&gt;3009/17 = 177&lt;/math&gt;</div> God of Math