

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 doublevisiting 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 boxyear=2006ab=Anumb=24after=Last Question}}
 
−   
−  [[Category:Introductory Combinatorics Problems]]
 
Revision as of 17:59, 28 October 2007