2013 AMC 12A Problems/Problem 20

Revision as of 16:01, 3 July 2013 by Kj2002 (talk | contribs) (See also)

Problem 20

Let $S$ be the set $\{1,2,3,...,19\}$. For $a,b \in S$, define $a \succ b$ to mean that either $0 < a - b \le 9$ or $b - a > 9$. How many ordered triples $(x,y,z)$ of elements of $S$ have the property that $x \succ y$, $y \succ z$, and $z \succ x$?

$\textbf{(A)} \ 810 \qquad  \textbf{(B)} \ 855 \qquad  \textbf{(C)} \ 900 \qquad  \textbf{(D)} \ 950 \qquad  \textbf{(E)} \ 988$

Solution

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 an arc of length $k$. 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.

See also

2013 AMC 12A (ProblemsAnswer KeyResources)
Preceded by
Problem 19
Followed by
Problem 21
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png