10
$\begingroup$

Eight spiders are located on the eight vertices of a cube.

When a bell rings, each spider moves (at random, independent of the others) to an adjacent vertex.

What is the probability that no two spiders end up at the same vertex?

How would I start this problem?

$\endgroup$
  • 1
    $\begingroup$ After writing a computer program, I think the answer is $\dfrac{1}{81}$. Anyone have an idea how to prove this? $\endgroup$ – JimmyK4542 Dec 17 '14 at 22:52
  • $\begingroup$ @JimmyK4542 My idea at the moment is to look at the number of functions obeying the conditions, and finding the probability that a random function from this set is injective. I'm currently needing to count how many functions are injective. There are 3^8 possible maps, given "moves to an adjacent vertex" means it cant stay where it is. $\endgroup$ – FireGarden Dec 17 '14 at 22:58
8
$\begingroup$

The key to this problem is to exploit symmetry as much as possible to reduce casework.

Label the vertices on the top face in CCW order $A,B,C,D$ and the vertices on the bottom face in CCW order $E,F,G,H$ where $AE$, $BF$, $CG$, $DH$ are edges connecting the top and bottom faces.

The four spiders at vertices $A,C,F,H$ will end up at one of the vertices $B,D,E,G$ (since there are no edges between the vertices $A,C,F,H$). Similarly, the four spiders at vertices $B,D,E,G$ will end up at one of the vertices $A,C,F,H$. Hence, no two spiders end up at the same vertex iff no two of the spiders at $A,C,F,H$ end up at the same vertex and no two of the spiders at $B,D,E,G$ end up at the same vertex.

There are $3^4$ ways for the four spiders at vertices $A,C,F,H$ to move. We count the ways they can move to $4$ different vertices as follows:

Case I: The spider at $A$ moves to $B$.

The spider at $C$ can only move to $D$ or $G$ (since $CE$ isn't an edge). If the spider at $C$ moves to $D$, then there are two ways for the spiders at $F,H$ to move: $(A,C,F,H) \to (B,D,E,G)$ or $(A,C,F,H) \to (B,D,G,E)$. If the spider at $C$ moves to $G$, then there is only one way for the spiders at $F,H$ to move: $(A,C,F,H) \to (B,G,E,D)$ (because $BH$ and $DF$ aren't edges). This gives $3$ ways for the spiders at $A,C,F,H$ to move to distinct vertices if the spider at $A$ moves to $B$.

Case II: The spider at $A$ moves to $D$.

Similarly to Case I, there are $3$ total ways for the spiders at $A,C,F,H$ to move to distinct vertices if the spider at $A$ moves to $D$.

Case III: The spider at $A$ moves to $E$.

Similarly to Case I, there are $3$ total ways for the spiders at $A,C,F,H$ to move to distinct vertices if the spider at $A$ moves to $E$.

This gives us $9$ ways for the spiders at $A,C,F,H$ to end up at distinct locations. Hence, the probability of no two of these spiders ending up at the same vertex is $\dfrac{9}{81} = \dfrac{1}{9}$.

Similarly, the probability that of no two of the spiders at vertices $B,D,E,G$ end up at the same vertex is $\dfrac{1}{9}$. So, the probability that no two spiders end up at the same vertex is $\dfrac{1}{9} \cdot \dfrac{1}{9} = \dfrac{1}{81}$.

$\endgroup$
  • $\begingroup$ Why can't, for instance, the spider at $C$ move to $B$? $\endgroup$ – Ian Dec 17 '14 at 23:22
  • 1
    $\begingroup$ We are counting the ways that the spiders at $A,C,F,H$ end up at distinct vertices. In the case that the spider at $A$ moves to $B$, spider $C$ moving to $B$ wouldn't yield a way for those four spiders to end up at distinct vertices. $\endgroup$ – JimmyK4542 Dec 17 '14 at 23:24
  • $\begingroup$ @JimmyK4542: What do you mean by CCW order? $\endgroup$ – Math is Life Dec 18 '14 at 5:01
  • $\begingroup$ CCW is an abbreviation for counterclockwise. $\endgroup$ – JimmyK4542 Dec 18 '14 at 5:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.