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?
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 |
No Subject
