https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Icecreamcake1&feedformat=atom AoPS Wiki - User contributions [en] 2022-10-02T03:10:18Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2013_AMC_12A_Problems/Problem_20&diff=58225 2013 AMC 12A Problems/Problem 20 2013-12-01T02:19:17Z <p>Icecreamcake1: /* Solution */</p> <hr /> <div>== Problem 20 ==<br /> <br /> Let &lt;math&gt;S&lt;/math&gt; be the set &lt;math&gt;\{1,2,3,...,19\}&lt;/math&gt;. For &lt;math&gt;a,b \in S&lt;/math&gt;, define &lt;math&gt;a \succ b&lt;/math&gt; to mean that either &lt;math&gt;0 &lt; a - b \le 9&lt;/math&gt; or &lt;math&gt;b - a &gt; 9&lt;/math&gt;. How many ordered triples &lt;math&gt;(x,y,z)&lt;/math&gt; of elements of &lt;math&gt;S&lt;/math&gt; have the property that &lt;math&gt;x \succ y&lt;/math&gt;, &lt;math&gt;y \succ z&lt;/math&gt;, and &lt;math&gt;z \succ x&lt;/math&gt;?<br /> <br /> &lt;math&gt; \textbf{(A)} \ 810 \qquad \textbf{(B)} \ 855 \qquad \textbf{(C)} \ 900 \qquad \textbf{(D)} \ 950 \qquad \textbf{(E)} \ 988 &lt;/math&gt;<br /> <br /> ==Solution==<br /> <br /> Imagine 19 numbers are just 19 persons sitting evenly around a circle &lt;math&gt;C&lt;/math&gt;; each of them is facing to the center. <br /> <br /> One may check that &lt;math&gt;x \succ y&lt;/math&gt; iff &lt;math&gt;y&lt;/math&gt; is one of the 9 persons on the left of &lt;math&gt;x&lt;/math&gt;, and &lt;math&gt;y \succ x&lt;/math&gt; iff &lt;math&gt;y&lt;/math&gt; is one of the 9 persons on the right of &lt;math&gt;x&lt;/math&gt;. Therefore, &quot;&lt;math&gt;x \succ y&lt;/math&gt; and &lt;math&gt;y \succ z&lt;/math&gt; and &lt;math&gt;z \succ x&lt;/math&gt;&quot; implies that &lt;math&gt;x, y, z&lt;/math&gt; cuts the circumference of &lt;math&gt;C&lt;/math&gt; into three arcs, each of which has no more than &lt;math&gt;10&lt;/math&gt; numbers sitting on it (inclusive).<br /> <br /> We count the complement: where the cut generated by &lt;math&gt;(x,y,z)&lt;/math&gt; has ONE arc that has more than &lt;math&gt;10&lt;/math&gt; persons sitting on. Note that there can only be one such arc because there are only &lt;math&gt;19&lt;/math&gt; persons in total.<br /> <br /> Suppose the number of persons on the longest arc is &lt;math&gt;k&gt;10&lt;/math&gt;. Then two places of &lt;math&gt;x,y,z&lt;/math&gt; are just chosen from the two end-points of the arc, and there are &lt;math&gt;19-k&lt;/math&gt; possible places for the third person. Once the three places of &lt;math&gt;x,y,z&lt;/math&gt; are chosen, there are three possible ways to put &lt;math&gt;x,y,z&lt;/math&gt; into them clockwise. Also, note that for any &lt;math&gt;k&gt;10&lt;/math&gt;, there are &lt;math&gt;19&lt;/math&gt; ways to choose an arc of length &lt;math&gt;k&lt;/math&gt;. Therefore the total number of ways (of the complement) is <br /> <br /> &lt;cmath&gt;\sum_{k=11}^{18} 3\cdot 19 \cdot (19-k) = 3\cdot 19 \cdot (1+\cdots+8) = 3\cdot 19\cdot 36&lt;/cmath&gt;<br /> <br /> So the answer is<br /> <br /> &lt;cmath&gt; 3\cdot \binom{19}{3} - 3\cdot 19\cdot 36 = 3\cdot 19 \cdot (51 - 36) = 855 &lt;/cmath&gt;<br /> <br /> NOTE: this multiple choice problem can be done even faster -- after we realized the fact that each choice of the three places of &lt;math&gt;x,y,z&lt;/math&gt; corresponds to &lt;math&gt;3&lt;/math&gt; possible ways to put them in, and that each arc of length &lt;math&gt;k&gt;10&lt;/math&gt; has &lt;math&gt;19&lt;/math&gt; equitable positions, it is evident that the answer should be divisible by &lt;math&gt;3\cdot 19&lt;/math&gt;, which can only be &lt;math&gt;855&lt;/math&gt; from the five choices.<br /> <br /> == See also ==<br /> {{AMC12 box|year=2013|ab=A|num-b=19|num-a=21}}<br /> {{MAA Notice}}</div> Icecreamcake1