Difference between revisions of "2013 AMC 12A Problems/Problem 20"
(Created page with "Imagine 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> iff <math>...") |
m |
||
(21 intermediate revisions by 10 users not shown) | |||
Line 1: | Line 1: | ||
− | + | == Problem 20 == | |
− | + | 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> | |
− | Suppose the number of persons on | + | ==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. | ||
+ | |||
+ | 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 | ||
+ | |||
+ | == 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 10:14, 29 October 2023
Contents
Problem 20
Let be the set
. For
, define
to mean that either
or
. How many ordered triples
of elements of
have the property that
,
, and
?
Solution 1
Imagine that the 19 numbers are just 19 persons sitting evenly around a circle ; each of them is facing to the center.
One may check that if and only if
is one of the 9 persons on the left of
, and
if and only if
is one of the 9 persons on the right of
. Therefore, "
and
and
" implies that
cuts the circumference of
into three arcs, each of which has no more than
numbers sitting on it (inclusive).
We count the complement: where the cut generated by has ONE arc that has more than
persons sitting on. Note that there can only be one such arc because there are only
persons in total.
Suppose the number of persons on the longest arc is . Then two places of
are just chosen from the two end-points of the arc, and there are
possible places for the third person. Once the three places of
are chosen, there are three possible ways to put
into them clockwise. Also, note that for any
, there are
ways to choose an arc of length
. Therefore the total number of ways (of the complement) is
So the answer is
NOTE: this multiple-choice problem can be done even faster -- after we realized the fact that each choice of the three places of corresponds to
possible ways to put them in, and that each arc of length
has
equitable positions, it is evident that the answer should be divisible by
, which can only be
from the five choices.
Solution 2
First, we can find out that the only that satisfy the conditions in the problem are
,
, and
.
Consider the 1st set of conditions for . We get that there are
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
Solution 3 (Common sense)
The conditions are very strange. The major way can satisfy is if
because at this point
no matter what. This is the only case that works, but we can rotate the variables around, so our answer is a multiple of
.
Suppose and
where
. That means
and
. WLOG
.
Start casework on what
is, anywhere from
to
. There are 2 main factors:
1. the number of ways to choose
, which is
.
2. the number of ways to choose
or start the sequence, which is
The sum of all cases turns out to be the sum of squares from
to
, which is
.
Multiply that by
and get
~dragnin
Solution 4 (Modular Arithmetic)
Note that if we take , the conditions are equivalent to
,
, and
. Let
. We have
ways to pick
, and
cases in our sample space for
. Of these cases, only those where
will work. By stars and bars, this turns out to be
, hence the answer is
.
~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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.