https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Etashthebomb&feedformat=atom AoPS Wiki - User contributions [en] 2021-01-27T20:30:53Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2006_AIME_II_Problems/Problem_10&diff=82028 2006 AIME II Problems/Problem 10 2016-12-27T02:03:36Z <p>Etashthebomb: /* Solution */</p> <hr /> <div>== Problem ==<br /> Seven teams play a soccer tournament in which each team plays every other team exactly once. No ties occur, each team has a &lt;math&gt; 50\% &lt;/math&gt; chance of winning each game it plays, and the outcomes of the games are independent. In each game, the winner is awarded a point and the loser gets 0 points. The total points are accumilated to decide the ranks of the teams. In the first game of the tournament, team &lt;math&gt; A &lt;/math&gt; beats team &lt;math&gt; B. &lt;/math&gt; The [[probability]] that team &lt;math&gt; A &lt;/math&gt; finishes with more points than team &lt;math&gt; B &lt;/math&gt; is &lt;math&gt; m/n, &lt;/math&gt; where &lt;math&gt; m &lt;/math&gt; and &lt;math&gt; n &lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt; m+n. &lt;/math&gt;<br /> <br /> __TOC__<br /> == Solution ==<br /> === Solution 1 ===<br /> The results of the five remaining games are independent of the first game, so by symmetry, the probability that &lt;math&gt;A&lt;/math&gt; scores higher than &lt;math&gt;B&lt;/math&gt; in these five games is equal to the probability that &lt;math&gt;B&lt;/math&gt; scores higher than &lt;math&gt;A&lt;/math&gt;. We let this probability be &lt;math&gt;p&lt;/math&gt;; then the probability that &lt;math&gt;A&lt;/math&gt; and &lt;math&gt;B&lt;/math&gt; end with the same score in these five games is &lt;math&gt;1-2p&lt;/math&gt;.<br /> <br /> Of these three cases (&lt;math&gt;|A| &gt; |B|, |A| &lt; |B|, |A|=|B|&lt;/math&gt;), the last is the easiest to calculate (see solution 2 for a way to directly calculate the other cases). <br /> <br /> There are &lt;math&gt;{5\choose k}&lt;/math&gt; ways to &lt;math&gt;A&lt;/math&gt; to have &lt;math&gt;k&lt;/math&gt; victories, and &lt;math&gt;{5\choose k}&lt;/math&gt; ways for &lt;math&gt;B&lt;/math&gt; to have &lt;math&gt;k&lt;/math&gt; victories. Summing for all values of &lt;math&gt;k&lt;/math&gt;,<br /> &lt;center&gt;&lt;math&gt;1-2p = \frac{1}{2^{5} \times 2^{5}}\left(\sum_{k=0}^{5} {5\choose k}^2\right) = \frac{1^2+5^2+10^2+10^2+5^2+1^2}{1024} = \frac{126}{512}.&lt;/math&gt;&lt;/center&gt;<br /> Thus &lt;math&gt;p = \frac 12 \left(1-\frac{126}{512}\right) = \frac{193}{512}&lt;/math&gt;. The desired probability is the sum of the cases when &lt;math&gt;|A| \ge |B|&lt;/math&gt;, so the answer is &lt;math&gt;\frac{126}{512} + \frac{193}{512} = \frac{319}{512}&lt;/math&gt;, and &lt;math&gt;m+n = \boxed{831}&lt;/math&gt;.<br /> <br /> === Solution 2 ===<br /> You can break this into cases based on how many rounds &lt;math&gt;A&lt;/math&gt; wins out of the remaining &lt;math&gt;5&lt;/math&gt; games.<br /> <br /> *If &lt;math&gt;A&lt;/math&gt; wins 0 games, then &lt;math&gt;B&lt;/math&gt; must win 0 games and the probability of this is &lt;math&gt; \frac{{5 \choose 0}}{2^5} \frac{{5 \choose 0}}{2^5} = \frac{1}{1024} &lt;/math&gt;.<br /> <br /> *If &lt;math&gt;A&lt;/math&gt; wins 1 games, then &lt;math&gt;B&lt;/math&gt; must win 1 or less games and the probability of this is &lt;math&gt; \frac{{5 \choose 1}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}}{2^5} = \frac{30}{1024} &lt;/math&gt;.<br /> <br /> *If &lt;math&gt;A&lt;/math&gt; wins 2 games, then &lt;math&gt;B&lt;/math&gt; must win 2 or less games and the probability of this is &lt;math&gt; \frac{{5 \choose 2}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}}{2^5} = \frac{160}{1024} &lt;/math&gt;.<br /> <br /> *If &lt;math&gt;A&lt;/math&gt; wins 3 games, then &lt;math&gt;B&lt;/math&gt; must win 3 or less games and the probability of this is &lt;math&gt; \frac{{5 \choose 3}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}+{5 \choose 3}}{2^5} = \frac{260}{1024} &lt;/math&gt;.<br /> <br /> *If &lt;math&gt;A&lt;/math&gt; wins 4 games, then &lt;math&gt;B&lt;/math&gt; must win 4 or less games and the probability of this is &lt;math&gt; \frac{{5 \choose 4}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}+{5 \choose 3}+{5 \choose 4}}{2^5} = \frac{155}{1024} &lt;/math&gt;.<br /> <br /> *If &lt;math&gt;A&lt;/math&gt; wins 5 games, then &lt;math&gt;B&lt;/math&gt; must win 5 or less games and the probability of this is &lt;math&gt; \frac{{5 \choose 5}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}+{5 \choose 3}+{5 \choose 4}+{5 \choose 5}}{2^5} = \frac{32}{1024} &lt;/math&gt;.<br /> <br /> Summing these 6 cases, we get &lt;math&gt; \frac{638}{1024} &lt;/math&gt;, which simplifies to &lt;math&gt; \frac{319}{512} &lt;/math&gt;, so our answer is &lt;math&gt;319 + 512 = \boxed{831}&lt;/math&gt;.<br /> <br /> ===Solution 3===<br /> <br /> We can apply the concept of generating functions here. <br /> <br /> The generating function for &lt;math&gt;B&lt;/math&gt; is &lt;math&gt; (1 + 0x^{1}) &lt;/math&gt; for the first game where &lt;math&gt;x^{n}&lt;/math&gt; is winning n games. Since he lost the first game, the coefficient for &lt;math&gt;x^{1}&lt;/math&gt; is 0. The generating function for the next 5 games is &lt;math&gt;(1 + x)^{5}&lt;/math&gt;. Thus, the total generating function for number of games he wins is<br /> <br /> &lt;math&gt;{(1 + 0x)(1 + x)^{5}} = (1 + 5x^{1} + 10x^{2} + 10x^{3} + 5x^{4} + x^{5})&lt;/math&gt;.<br /> <br /> The generating function for &lt;math&gt;A&lt;/math&gt; is the same except that it is multiplied by &lt;math&gt;x&lt;/math&gt; instead of &lt;math&gt;(1+0x)&lt;/math&gt;. <br /> Thus, the generating function for &lt;math&gt;A&lt;/math&gt; is <br /> <br /> &lt;math&gt;1x + 5x^{2} + 10x^{3} + 10x^{4} + 5x^{5} + x^{6}&lt;/math&gt;. <br /> <br /> The probability that &lt;math&gt;B&lt;/math&gt; wins 0 games is &lt;math&gt;\frac{1}{32}&lt;/math&gt;. Since the coefficients for all &lt;math&gt;x^{n}&lt;/math&gt; where <br /> <br /> &lt;math&gt;n \geq 1&lt;/math&gt; sums to 32, the probability that he wins more games is &lt;math&gt;\frac{32}{32}&lt;/math&gt;. <br /> <br /> Thus, the probability that &lt;math&gt;A&lt;/math&gt; has more wins than &lt;math&gt;B&lt;/math&gt; is &lt;math&gt;\frac{1}{32} \times \frac{32}{32} + \frac{5}{32} \times \frac{31}{32} + \frac{10}{32} \times \frac{26}{32} + \frac{10}{32} \times \frac{16}{32} + \frac{5}{32} \times \frac{6}{32} +\frac{1}{32} \times \frac{1}{32} = \frac{638}{1024} = \frac{319}{512}&lt;/math&gt;.<br /> <br /> Thus, &lt;math&gt;319 + 512 = \boxed{831} &lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=2006|n=II|num-b=9|num-a=11}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]<br /> {{MAA Notice}}</div> Etashthebomb