Difference between revisions of "2013 AMC 12A Problems/Problem 20"

Revision as of 23:55, 13 February 2013

Imagine 19 numbers are just 19 persons sitting evenly around a circle $C$ ; each of them is facing to the center.

One may check that $x \succ y$ iff $y$ is one of the 9 persons on the left of $x$ , and $y \succ x$ iff $y$ is one of the 9 persons on the right of $x$ . Therefore, " $x \succ y$ and $y \succ z$ and $z \succ x$ " implies that $x, y, z$ cuts the circumference of $C$ into three arcs, each of which has no more than $10$ numbers sitting on it (inclusive).

We count the complement: where the cut generated by $(x,y,z)$ has ONE arc that has more than $10$ persons sitting on. Note that there can only be one such arc because there are only $19$ persons in total.

Suppose the number of persons on the longest arc is $k>10$ . Then two places of $x,y,z$ are just chosen from the two end-points of the arc, and there are $19-k$ possible places for the third person. Once the three places of $x,y,z$ is chosen, there are three possible ways to put $x,y,z$ into them clockwise. Also, note that for any $k>10$ , there are $19$ ways to choose it. Therefore the total number of ways (of the complement) is

$\sum_{k=11}^{18} 3\cdot 19 \cdot (19-k) = 3\cdot 19 \cdot (1+\cdots+8) = 3\cdot 19\cdot 36$

So the answer is

$3\cdot \binom{19}{3} - 3\cdot 19\cdot 36 = 3\cdot 19 \cdot (51 - 36) = 855$

NOTE: this multiple choice problem can be done even faster -- after we realized the fact that each choice of the three places of $x,y,z$ corresponds to $3$ possible ways to put them in, and that each arc of length $k>10$ has $19$ equitable positions, it is evident that the answer should be divisible by $3\cdot 19$ , which can only be $855$ from the five choices.

@@ Line 5: / Line 5: @@
 We count the complement: where the cut generated by <math>(x,y,z)</math> has ONE arc that has more than <math>10</math> persons sitting on. Note that there can only be one such arc because there are only <math>19</math> persons in total.
-Suppose the number of persons on  the longest arc is <math>k>10</math>. Then two places of <math>x,y,z</math> are just chosen from the two end-points of the arc, and there are <math>19-k</math> possible places for the third person. Once the three places of <math>x,y,z</math> is chosen, there are three possible ways to put <math>x,y,z</math> into it clockwise. Also, note that for any <math>k>10</math>, there are <math>19</math> ways to choose it. Therefore the total number of ways (of the complement) is
+Suppose the number of persons on  the longest arc is <math>k>10</math>. Then two places of <math>x,y,z</math> are just chosen from the two end-points of the arc, and there are <math>19-k</math> possible places for the third person. Once the three places of <math>x,y,z</math> is chosen, there are three possible ways to put <math>x,y,z</math> into them clockwise. Also, note that for any <math>k>10</math>, there are <math>19</math> ways to choose it. Therefore the total number of ways (of the complement) is
 <cmath>\sum_{k=11}^{18} 3\cdot 19 \cdot (19-k) = 3\cdot 19 \cdot (1+\cdots+8) = 3\cdot 19\cdot 36</cmath>

Page

Toolbox

Search

Difference between revisions of "2013 AMC 12A Problems/Problem 20"

Revision as of 23:55, 13 February 2013