Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2013 AMC 12A Problems/Problem 20"
m (Fixed code)
 
(24 intermediate revisions by 12 users not shown)
Line 1: Line 1:
−
Imagine 19 numbers are just 19 persons sitting evenly around a circle <math>C</math>; each of them is facing to the center.
+
== Problem 20 ==
  
−
One may check that <math>x \succ y</math> iff <math>y</math> is one of the 9 persons on the left of <math>x</math>, and <math>y \succ x</math> iff <math>y</math> is one of the 9 persons on the right of <math>x</math>. Therefore, "<math>x \succ y</math> and <math>y \succ z</math> and <math>z \succ x</math>" implies that <math>x, y, z</math> cuts the circumference of <math>C</math> into three arcs, each of which has no more than <math>10</math> numbers sitting on it (inclusive).
+
Let <math>S</math> be the set <math>\{1,2,3,...,19\}</math>. For <math>a,b \in S</math>, define <math>a \succ b</math> to mean that either <math>0 < a - b \le 9</math> or <math>b - a > 9</math>. How many ordered triples <math>(x,y,z)</math> of elements of <math>S</math> have the property that <math>x \succ y</math>, <math>y \succ z</math>, and <math>z \succ x</math>?
 +
 
 +
<math> \textbf{(A)} \ 810 \qquad  \textbf{(B)} \ 855 \qquad  \textbf{(C)} \ 900 \qquad  \textbf{(D)} \ 950 \qquad  \textbf{(E)} \ 988 </math>
 +
 
 +
==Solution 1==
 +
 
 +
Imagine that the 19 numbers are just 19 persons sitting evenly around a circle <math>C</math>; each of them is facing to the center.
 +
 
 +
One may check that <math>x \succ y</math> if and only if <math>y</math> is one of the 9 persons on the left of <math>x</math>, and <math>y \succ x</math> if and only if <math>y</math> is one of the 9 persons on the right of <math>x</math>. Therefore, "<math>x \succ y</math> and <math>y \succ z</math> and <math>z \succ x</math>" implies that <math>x, y, z</math> cuts the circumference of <math>C</math> into three arcs, each of which has no more than <math>10</math> numbers sitting on it (inclusive).
  
 
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.
 
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> are 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 an arc of length <math>k</math>. 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>
 
<cmath>\sum_{k=11}^{18} 3\cdot 19 \cdot (19-k) = 3\cdot 19 \cdot (1+\cdots+8) = 3\cdot 19\cdot 36</cmath>
Line 13: Line 21:
 
<cmath> 3\cdot \binom{19}{3} - 3\cdot 19\cdot 36 = 3\cdot 19 \cdot (51 - 36) = 855 </cmath>
 
<cmath> 3\cdot \binom{19}{3} - 3\cdot 19\cdot 36 = 3\cdot 19 \cdot (51 - 36) = 855 </cmath>
  
−
NOTE: this multiple choice problem can be done even faster -- after we realized the fact that each choice of the three places of <math>x,y,z</math> corresponds to <math>3</math> possible ways to put them in, and that each arc of length <math>k>10</math> has <math>19</math> equitable positions, it is evident that the answer should be divisible by <math>3\cdot 19</math>,  which can only be <math>855</math> from the five choices.
+
NOTE: this multiple-choice problem can be done even faster -- after we realized the fact that each choice of the three places of <math>x,y,z</math> corresponds to <math>3</math> possible ways to put them in, and that each arc of length <math>k>10</math> has <math>19</math> equitable positions, it is evident that the answer should be divisible by <math>3\cdot 19</math>,  which can only be <math>855</math> from the five choices.
 +
 
 +
==Solution 2==
 +
 
 +
First, we can find out that the only <math>x, y, z</math> that satisfy the conditions in the problem are <math>(1 \leq z-y \leq 9 , 1 \leq y-x \leq 9 , z-x \geq 10)</math> , <math>(1 \leq y-x \leq 9 , 1 \leq x-z \leq 9 , y-z \geq 10)</math> , and <math>(1 \leq x-z \leq 9 , 1 \leq z-y \leq 9 , x-y \geq 10)</math>.
 +
 
 +
Consider the 1st set of conditions for <math>x, y, z</math>. We get that there are
 +
 
 +
<cmath>45\cdot 10 - \sum_{k=1}^{9} \binom{k+1}{2} = 285</cmath>
 +
 
 +
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
 +
 
 +
<cmath>3\cdot 285 = \fbox{(B)855} </cmath>
 +
 
 +
 
 +
==Solution 3 (Common sense)==
 +
 
 +
The conditions are very strange. The major way <math>x,y,z</math> can satisfy is if <math>(1 \leq z-y \leq 9 , 1 \leq y-x \leq 9 , z-x \geq 10)</math> because at this point <math>z > x</math> no matter what. This is the only case that works, but we can rotate the variables around, so our answer is a multiple of <math>3</math>.
 +
 
 +
Suppose <math>z=y+a</math> and <math>y=x+b</math> where <math>0<a,b<10</math>. That means <math>z=x+a+b</math> and <math>10 \leq z \leq 18</math>. WLOG <math>z>y>x</math>.
 +
Start casework on what <math>a+b</math> is, anywhere from <math>10</math> to <math>18</math>. There are 2 main factors:
 +
1. the number of ways to choose <math>a,b</math>, which is <math>a+b-1</math>.
 +
2. the number of ways to choose <math>x</math> or start the sequence, which is <math>19-(a+b)</math>
 +
The sum of all cases turns out to be the sum of squares from <math>9^2</math> to <math>1^2</math>, which is <math>\frac{9 \cdot 10 \cdot 19}{2 \cdot 3}</math>.
 +
Multiply that by <math>3</math> and get <math>\fbox{(B)855} </math>
 +
 
 +
~dragnin
 +
 
 +
==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
 +
 
 +
==Solution 5 (pretty braindead)==
 +
<math>x \succ_1 y</math> will denote the first inequality, and <math>x\succ_2 y</math> will denote the second.
 +
 
 +
 
 +
We soon see that we cannot have <math>x\succ_1 y \succ_1 z \succ_1 x</math> by adding the inequalities we obtain from them together, as it results in <math>0<0</math>.
 +
 
 +
 
 +
Similarly, we can't have <math>x\succ_2 y \succ_2 z \succ_2 x</math>. <math>x\succ_2 y \succ_2 z \succ_1 x</math> is also not possible by observing the inequalities.
 +
 
 +
 
 +
Thus, we only have to consider <math>x \succ_1 y\succ_1 z \succ_2 x</math>. Something like <math>x \succ_2 y \succ_1 z \succ_1 x</math> is just a rotation of this case.
 +
 
 +
 
 +
Here, we start with <math>0<x-y\le 9</math>, <math>0<y-z\le 9</math>, and <math>x-z > 9</math>. We begin with casework on <math>z</math>, since it is the smallest.
 +
 
 +
 
 +
When <math>z=1</math>, <math>x</math> can range from <math>[11,19]</math>. There are <math>9+8+7+6+5+4+3+2+1 = 45</math> different values for <math>y</math> as x ranges across <math>11-19</math>.
 +
 
 +
 
 +
When <math>z=2</math>, <math>x</math> can range from <math>[12-19]</math>. There are <math>9+8+7+6+5+4+3+2 = 44</math> different values for <math>y</math> as x ranges across <math>12-19</math>.
 +
 
 +
 
 +
Continuing this pattern, we get the sum <math>45+44+42+39+35+30+24+17+9 = 285</math>. Multiplying by three to count for rotations, we get <math>\boxed{(\textbf{B}) 855}</math>.
 +
 
 +
-skibbysiggy
 +
 
 +
== See also ==
 +
{{AMC12 box|year=2013|ab=A|num-b=19|num-a=21}}
 +
 
 +
[[Category: Introductory Set Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 22:03, 23 September 2024

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

Solution 5 (pretty braindead)

$x \succ_1 y$ will denote the first inequality, and $x\succ_2 y$ will denote the second.


We soon see that we cannot have $x\succ_1 y \succ_1 z \succ_1 x$ by adding the inequalities we obtain from them together, as it results in $0<0$.


Similarly, we can't have $x\succ_2 y \succ_2 z \succ_2 x$. $x\succ_2 y \succ_2 z \succ_1 x$ is also not possible by observing the inequalities.


Thus, we only have to consider $x \succ_1 y\succ_1 z \succ_2 x$. Something like $x \succ_2 y \succ_1 z \succ_1 x$ is just a rotation of this case.


Here, we start with $0<x-y\le 9$, $0<y-z\le 9$, and $x-z > 9$. We begin with casework on $z$, since it is the smallest.


When $z=1$, $x$ can range from $[11,19]$. There are $9+8+7+6+5+4+3+2+1 = 45$ different values for $y$ as x ranges across $11-19$.


When $z=2$, $x$ can range from $[12-19]$. There are $9+8+7+6+5+4+3+2 = 44$ different values for $y$ as x ranges across $12-19$.


Continuing this pattern, we get the sum $45+44+42+39+35+30+24+17+9 = 285$. Multiplying by three to count for rotations, we get $\boxed{(\textbf{B}) 855}$.

-skibbysiggy

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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_AMC_12A_Problems/Problem_20&oldid=227910"