Difference between revisions of "2006 AMC 10A Problems/Problem 25"

m (r)
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]]

Revision as of 17:59, 28 October 2007


This problem appears on both the AMC 12 and the AMC 10.

Invalid username
Login to AoPS