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

Revision as of 09:14, 29 October 2023

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 1

Imagine that the 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$ if and only if $y$ is one of the 9 persons on the left of $x$ , and $y \succ x$ if and only if $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$ are 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.

Solution 2

First, we can find out that the only $x, y, z$ that satisfy the conditions in the problem are $(1 \leq z-y \leq 9 , 1 \leq y-x \leq 9 , z-x \geq 10)$ , $(1 \leq y-x \leq 9 , 1 \leq x-z \leq 9 , y-z \geq 10)$ , and $(1 \leq x-z \leq 9 , 1 \leq z-y \leq 9 , x-y \geq 10)$ .

Consider the 1st set of conditions for $x, y, z$ . We get that there are

$45\cdot 10 - \sum_{k=1}^{9} \binom{k+1}{2} = 285$

cases for the first set of conditions.

Since the 2nd and 3rd set of conditions are simply rotations of the 1st set, the total number of cases is

$3\cdot 285 = \fbox{(B)855}$

Solution 3 (Common sense)

The conditions are very strange. The major way $x,y,z$ can satisfy is if $(1 \leq z-y \leq 9 , 1 \leq y-x \leq 9 , z-x \geq 10)$ because at this point $z > x$ no matter what. This is the only case that works, but we can rotate the variables around, so our answer is a multiple of $3$ .

Suppose $z=y+a$ and $y=x+b$ where $0<a,b<10$ . That means $z=x+a+b$ and $10 \leq z \leq 18$ . WLOG $z>y>x$ . Start casework on what $a+b$ is, anywhere from $10$ to $18$ . There are 2 main factors: 1. the number of ways to choose $a,b$ , which is $a+b-1$ . 2. the number of ways to choose $x$ or start the sequence, which is $19-(a+b)$ The sum of all cases turns out to be the sum of squares from $9^2$ to $1^2$ , which is $\frac{9 \cdot 10 \cdot 19}{2 \cdot 3}$ . Multiply that by $3$ and get $\fbox{(B)855}$

~dragnin

Solution 4 (Modular Arithmetic)

Note that if we take $a, b, c\mod{19}$ , the conditions are equivalent to $0<a-b\le{9}\mod{19}$ , $0<b-c\le{9}\mod{19}$ , and $0<c-a\le{9}\mod{19}$ . Let $m=a-b, n=b-c$ . We have $19$ ways to pick $a$ , and $81$ cases in our sample space for $m, n$ . Of these cases, only those where $m+n>9$ will work. By stars and bars, this turns out to be $\binom{10}{2}=45$ , hence the answer is $45*19=\fbox{(B)855}$ . ~sigmapie

@@ Line 52: / Line 52: @@
 ==Solution 4 (Modular Arithmetic)==
 Note that if we take <math>a, b, c\mod{19}</math>, the conditions are equivalent to <math>0<a-b\le{9}\mod{19}</math>, <math>0<b-c\le{9}\mod{19}</math>, and <math>0<c-a\le{9}\mod{19}</math>. Let <math>m=a-b, n=b-c</math>. We have <math>19</math> ways to pick <math>a</math>, and <math>81</math> cases in our sample space for <math>m, n</math>. Of these cases, only those where <math>m+n>9</math> will work. By stars and bars, this turns out to be <math>\binom{10}{2}=45</math>, hence the answer is <math>45*19=\fbox{(B)855}</math>.
+~sigmapie
 == See also ==

2013 AMC 12A (Problems • Answer Key • Resources)
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

Page

Toolbox

Search