Difference between revisions of "2013 AMC 12B Problems/Problem 12"
(→Solution) |
|||
Line 24: | Line 24: | ||
==Solution== | ==Solution== | ||
+ | |||
+ | Note that cities <math>C</math> and <math>E</math> can be removed when counting paths because if a path goes in to <math>C</math> or <math>E</math>, there is only one possible path to take out of cities <math>C</math> or <math>E</math>. | ||
+ | So the diagram is as follows: | ||
+ | <asy> | ||
+ | unitsize(10mm); | ||
+ | defaultpen(linewidth(1.2pt)+fontsize(10pt)); | ||
+ | dotfactor=4; | ||
+ | pair A=(1,0), B=(4.24,0), C=(5.24,3.08), D=(2.62,4.98), E=(0,3.08); | ||
+ | dot (A); | ||
+ | dot (B); | ||
+ | |||
+ | dot (D); | ||
+ | |||
+ | label("$A$",A,S); | ||
+ | label("$B$",B,SE); | ||
+ | |||
+ | label("$D$",D,N); | ||
+ | |||
+ | draw(A--B..D..cycle); | ||
+ | draw(A--D); | ||
+ | draw(B--D);</asy> | ||
+ | |||
+ | Now we proceed with casework. Remember that there are two ways to travel from <math>A</math> to <math>D</math>, <math>D</math> to <math>A</math>, <math>B</math> to <math>D</math> and <math>D</math> to <math>B</math>.: | ||
+ | |||
+ | Case 1 <math>A \Rightarrow D</math>: From <math>D</math>, if the path returns to <math>A</math>, then the next path must go to <math>B\Rightarrow D \Rightarrow B</math>. There are <math>2 \cdot 1 \cdot 2 = 4</math> possibilities of the path <math>ADABDB</math>. If the path goes to <math>B</math> from <math>D</math>, then the path must continue with either <math>BDAB</math> or <math>BADB</math>. There are <math>2 \cdot 2 \cdot 2 = 8</math> possibilities. So, this case gives <math>4+8=12</math> different possibilities. | ||
+ | |||
+ | Case 2 <math>A \Rightarrow B</math>: The path must continue with <math>BDADB</math>. There are <math>2 \cdot 2 = 4</math> possibilities for this case. | ||
+ | |||
+ | Putting the two cases together gives <math>12+4 = \boxed{\textbf{(D)}16}</math> | ||
== See also == | == See also == | ||
{{AMC12 box|year=2013|ab=B|num-b=11|num-a=13}} | {{AMC12 box|year=2013|ab=B|num-b=11|num-a=13}} |
Revision as of 21:14, 22 February 2013
Problem
Cities ,
,
,
, and
are connected by roads
,
,
,
,
,
, and
. How many different routes are there from
to
that use each road exactly once? (Such a route will necessarily visit some cities more than once.)
Solution
Note that cities and
can be removed when counting paths because if a path goes in to
or
, there is only one possible path to take out of cities
or
.
So the diagram is as follows:
Now we proceed with casework. Remember that there are two ways to travel from to
,
to
,
to
and
to
.:
Case 1 : From
, if the path returns to
, then the next path must go to
. There are
possibilities of the path
. If the path goes to
from
, then the path must continue with either
or
. There are
possibilities. So, this case gives
different possibilities.
Case 2 : The path must continue with
. There are
possibilities for this case.
Putting the two cases together gives
See also
2013 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 11 |
Followed by Problem 13 |
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 |