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?
Call the vartices:
A the bug's original position
B, C, D the points accessible directly from A
E, F, G the next points accessible -- each from two of the preceding
H the sugary goal
clearvars,clc
global totsucc avail edges prob hist countsucc lensucc
locs=['abcdefgh'];
loc='a';
edges=['ab';'ac';'ad';'be';'bf';'cf';'cg';'dg';'de';'eh';'fh';'gh'];
avail=true(1,12);
prob=sym(1);
totsucc=sym(0);
hist=char.empty(0,2);
lensucc=0;
countsucc=0;
moveIt('a');
totsucc
totfail=1-totsucc
lensucc/countsucc
function moveIt(wh)
global totsucc avail edges prob hist countsucc lensucc
if wh=='h'
countsucc=countsucc+1;
lensucc=lensucc+length(hist);
totsucc=totsucc+prob;
for i=1:length(hist)
fprintf('%s ',hist(i,:))
end
disp([' ' char(string(prob))])
else
ctPoss=0;
for i=1:12
if avail(i)
if edges(i,1)==wh || edges(i,2)==wh
ctPoss=ctPoss+1;
end
end
end
if ctPoss==0
for i=1:length(hist)
fprintf('%s ',hist(i,:))
end
disp('dead end ')
end
for i=1:12
if avail(i)
if edges(i,1)==wh || edges(i,2)==wh
avail(i)=false;
saveprob=prob;
prob=prob/ctPoss;
savehist=hist;
hist(end+1,:)=edges(i,:);
moveIt(edges(i,2-(edges(i,2)==wh)))
hist=savehist;
prob=saveprob;
avail(i)=true;
end
end
end
end
end
lists the dead-end paths and the successful paths. The latter show the probability that that specific route will be taken. Each edge has its endpoints shown in alphabetic order, so going from E to D might be listed as de.
ab be de ad ac cf bf dead end
ab be de ad ac cf fh 1/96
ab be de ad ac cg dg dead end
ab be de ad ac cg gh 1/96
ab be de dg cg ac ad dead end
ab be de dg cg cf bf dead end
ab be de dg cg cf fh 1/192
ab be de dg gh 1/48
ab be eh 1/12
ab bf cf ac ad dg cg dead end
ab bf cf ac ad dg gh 1/96
ab bf cf ac ad de be dead end
ab bf cf ac ad de eh 1/96
ab bf cf cg dg ad ac dead end
ab bf cf cg dg de be dead end
ab bf cf cg dg de eh 1/192
ab bf cf cg gh 1/48
ab bf fh 1/12
ac cf bf ab ad dg cg dead end
ac cf bf ab ad dg gh 1/96
ac cf bf ab ad de be dead end
ac cf bf ab ad de eh 1/96
ac cf bf be de ad ab dead end
ac cf bf be de dg cg dead end
ac cf bf be de dg gh 1/192
ac cf bf be eh 1/48
ac cf fh 1/12
ac cg dg ad ab be de dead end
ac cg dg ad ab be eh 1/96
ac cg dg ad ab bf cf dead end
ac cg dg ad ab bf fh 1/96
ac cg dg de be ab ad dead end
ac cg dg de be bf cf dead end
ac cg dg de be bf fh 1/192
ac cg dg de eh 1/48
ac cg gh 1/12
ad dg cg ac ab be de dead end
ad dg cg ac ab be eh 1/96
ad dg cg ac ab bf cf dead end
ad dg cg ac ab bf fh 1/96
ad dg cg cf bf ab ac dead end
ad dg cg cf bf be de dead end
ad dg cg cf bf be eh 1/192
ad dg cg cf fh 1/48
ad dg gh 1/12
ad de be ab ac cf bf dead end
ad de be ab ac cf fh 1/96
ad de be ab ac cg dg dead end
ad de be ab ac cg gh 1/96
ad de be bf cf ac ab dead end
ad de be bf cf cg dg dead end
ad de be bf cf cg gh 1/192
ad de be bf fh 1/48
ad de eh 1/12
The end shows the statistics:
totsucc =
25/32 probability that the bug gets sugar
totfail =
7/32 probability of dead end reached
ans =
5.8 average length of a successful run
BTW 7/32 = 0.21875
The above calculation of the average length of a successful run is incorrect, as it did not take into consideration the probabilities of each length of run.
Edited on November 27, 2023, 2:02 pm
|
|
Posted by Charlie
on 2023-11-27 13:56:24 |
computer solution
