|
|
| Line 1: |
Line 1: |
| − | == Problem ==
| + | #redirect [[2006 AMC 12A Problems/Problem 20]] {{redirect from amc10}} |
| − | A bug starts at one [[vertex]] of a [[cube (geometry) | cube]] and moves along the [[edge]]s of the cube according to the following rule. At each vertex the bug will choose to travel along one of the three edges emanating from that vertex. Each edge has equal [[probability]] of being chosen, and all choices are independent. What is the probability that after seven moves the bug will have visited every vertex exactly once?
| |
| − | | |
| − | <math>\mathrm{(A) \ } \frac{1}{2187}\qquad\mathrm{(B) \ } \frac{1}{729}\qquad\mathrm{(C) \ } \frac{2}{243}\qquad\mathrm{(D) \ } \frac{1}{81}\qquad\mathrm{(E) \ } \frac{5}{243}\qquad</math>
| |
| − | | |
| − | == Solution ==
| |
| − | Let us count the good paths. The bug starts at an arbitrary [[vertex]], moves to a neighboring vertex (3 ways), and then to a new neighbor (2 more ways). So, [[without loss of generality]], let the [[cube (geometry) | cube]] have vertex <math>ABCDEFGH</math> such that <math>ABCD</math> and <math>EFGH</math> are two opposite [[face]]s with <math>A</math> above <math>E</math> and <math>B</math> above <math>F</math>. The bug starts at <math>A</math> and moves first to <math>B</math>, then to <math>C</math>.
| |
| − | | |
| − | From this point, there are two cases.
| |
| − | | |
| − | Case 1: the bug moves to <math>D</math>. From <math>D</math>, there is only one good move available, to <math>H</math>. From <math>H</math>, there are two ways to finish the trip, either by going <math>H \to G \to F \to E</math> or <math>\displaystyle H \to E \to F \to G</math>. So there are 2 good paths in this case.
| |
| − | | |
| − | Case 2: the bug moves to <math>G</math>.
| |
| − | Case 2a: the bug moves <math>G \to H</math>. In this case, there are 0 good paths because it will not be possible to visit both <math>D</math> and <math>E</math> without double-visiting some vertex.
| |
| − | Case 2b: the bug moves <math>G \to F</math>. There is a unique good path in this case, <math>F \to E \to G \to H</math>.
| |
| − | | |
| − | Thus, all told we have 3 good paths after the first two moves, for a total of <math>3\cdot 3 \cdot 2 = 18</math> good paths. There were <math>3^7 = 2187</math> possible paths the bug could have taken, so the [[probability]] a random path is good is the [[ratio]] of good paths to total paths, <math>\frac{18}{2187} = \frac2{243}</math>, which is answer choice <math>\mathrm (C)</math>.
| |
| − | | |
| − | == See also ==
| |
| − | * [[Casework]]
| |
| − | {{AMC10 box|year=2006|ab=A|num-b=24|after=Last Question}}
| |
| − | | |
| − | [[Category:Introductory Combinatorics Problems]]
| |
