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?
Program output from 1 million repetitions:
[219123, 0, 0, 499990, 0, 124605, 0, 156282, 0, 0, 0, 0, 0]
Dead ends 0.219123 (analytic result was 0.21875)
Expected value 4.119687223467973 (analytic result was 4.12)
This confirms the earlier analytic solution.
Explanation of program.
In the above list of 13 numbers, the number of times the bug reached the sugar in 'n' moves is the n-th value. But this is zero based indexing, so in the zero-th slot, I added a 1 to the zero-th value in the case of a dead end.
The bug's location is a single character lowercase 'a' thru 'h'.
A wire is named with a 2 character string.
When a random choice is made, the bug selects one of the wires which has its current location as one of the two characters in the wire name. The new location is the other character. And then that wire name is deleted from the list of wires.
Note that a successful trip is always an odd number of moves.
-------
import random
reps = 1000000
triplengths = [0 for i in range(13)]
for r in range(reps):
loc = 'a'
wires = ['ab', 'ad', 'ae', 'bc', 'bf', 'cd', 'dh', 'ef', 'eh', 'cg', 'fg', 'gh']
for step in range(12):
options = [ w for w in wires if loc in w]
if options == [] or len(options) == 0:
triplengths[0] += 1
break
choice = random.randint(0, len(options)-1)
loc = options[choice].replace(loc, '')
wires.remove(options[choice])
if loc == 'g':
stepstaken = 12 - len(wires)
triplengths[stepstaken] += 1
break
print(triplengths)
print('Dead ends', triplengths[0] / reps)
score = 0
for i in range(1,13):
score += i * triplengths[i]
print('Expected value', score / ( reps - triplengths[0] ))
Edited on November 28, 2023, 4:44 pm
|
|
Posted by Larry
on 2023-11-28 16:42:42 |
Simulation
