All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Bug on a Cube 2 (Posted on 2023-11-27) Difficulty: 3 of 5
A bug is placed at one corner of a wire frame in the shape of a cube. At the diagonally opposite corner is a piece of sugar.

The bug crawls along the 12 wires of the frame searching for the sugar. At each of the 8 corners the bug randomly chooses one a wire to follow next with the additional rule that it can never cross the same wire twice.

What is the probability that it will dead-end by reaching a corner with no available wires? In the case where it does reach the sugar, what is the expected number of edges the bug traverses?

No Solution Yet Submitted by Jer    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution No Subject | Comment 1 of 5
Label the 4 vertices closest to you A,B,C,D; and the 4 furthest from you in the same direction E,F,G,H.
A connects to B,D,E.
B connects to C and F.
D connects to C and H.
E connects to F and H.
C,F,H connect to G.
If you lay out the cube, flattened into 2 dimensions and draw all the connections, you get something like:

0   1   2   3 <-- "layers"
    B   C
A  D   F   G (Goal)
    E   H

Every move changes the position to an adjacent layer; it is impossible to move and also stay on the same layer.

wlog, the first 2 moves can be considered A to B to C.  At this point, there is a 50% chance of going to the goal, ABCG, (50% chance that the answer is 3); and a 50% chance the bug returns to Layer 1, ABCD.
Consider now the latter 50%, the bug is (wlog) at D and has moved 3 so far.
The 3 edges A to B, B to C, C to D are all gone; 9 edges remain.

Assuming 3 moves so far without reaching the goal, location is D.
If you redraw the diagram without the 3 missing edges, you get the topological equivalent of:

D--H--G--C
|  |  |
A--E--F--B

ABCG (1/2)      3 moves  (the other 50%; not on the above diagram)
ABCDHG (1/8)    5 moves
ABCDHEAD (1/16) Dead end
ABCDHEFG (1/32) 7 moves
ABCDHEFB (1/32) Dead end
ABCDAEHD (1/16) Dead end
ABCDAEHG (1/16) 7 moves
ABCDAEFG (1/16) 7 moves
ABCDAEFB (1/16) Dead end

Dead End probability:  1/16 + 1/32 + 1/16 + 1/16 = 7/32
------
Question 2:
Expected value, sum this list then divide by 25/32: 
(1/2)*3  = 48/32
(1/8)*5  = 20/32
(1/32)*7 =  7/32
(1/16)*7 = 14/32
(1/16)*7 = 14/32
--------------------
        103/32 * (32/25) = 103/25 = 4.12 moves (or edges)

  Posted by Larry on 2023-11-27 11:33:39
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information