Six bugs simultaneously stand on the six vertices of a regular octahedron, with each bug situated at a different vertex.
Each bug moves simultaneously and independently from its vertex to one of the four adjacent vertices, each with equal probability.
Determine the probability that no two bugs arrive at the same vertex.
As shown below, there are 80 sets of choices the bugs could make in keeping with each seeking a different vertex, out of the 4^6=4096 sets of choices overall. That makes the probability 80/4096 = 5/256 = .01953125 exactly.
The bugs' original and destination vertices are numbered as follows:
4 5
1
2 3
6
so that, for example, 451 is one of the faces, as are 456 and 426, etc.
dest. permutation
of bug cycle notation
------
123456
465132 (41)(62)(53)
546132 (536241)
345162 (356241)
365142 (3541)(62)
435162 (41)(3562)
536142 (541)(362)
245163 (241)(563)
265143 (263541)
246135 (241)(653)
265134 (2641)(53)
236145 (236541)
235164 (235641)
542163 (563241)
562143 (541)(632)
462135 (41)(6532)
562134 (532641)
342165 (3241)(65)
362145 (326541)
432165 (41)(32)(65)
532164 (5641)(32)
465213 (426351)
546213 (51)(42)(63)
346215 (3651)(42)
365214 (351)(642)
436215 (423651)
536214 (51)(3642)
345612 (351)(462)
346512 (362451)
435612 (462351)
436512 (451)(362)
245613 (246351)
246513 (2451)(63)
235614 (2351)(64)
236514 (236451)
462513 (451)(632)
542613 (51)(4632)
342615 (324651)
362514 (326451)
432615 (4651)(32)
532614 (51)(32)(64)
415263 (421)(563)
516243 (5421)(63)
416235 (421)(653)
516234 (536421)
316245 (365421)
315264 (356421)
415632 (4621)(53)
416532 (453621)
315642 (354621)
316542 (3621)(54)
215643 (21)(5463)
216543 (21)(63)(54)
215634 (21)(53)(64)
216534 (21)(6453)
412563 (456321)
512643 (546321)
412635 (465321)
512634 (5321)(64)
312645 (321)(654)
312564 (321)(564)
541263 (5631)(42)
561243 (542631)
461235 (426531)
561234 (531)(642)
341265 (31)(42)(65)
361245 (31)(6542)
431265 (4231)(65)
531264 (564231)
461532 (4531)(62)
541632 (531)(462)
341562 (31)(4562)
361542 (31)(62)(54)
431562 (456231)
531642 (546231)
241563 (245631)
261543 (2631)(54)
241635 (246531)
261534 (264531)
231645 (231)(654)
231564 (231)(564)
32 of these are Hamiltonians of the octahedron, but others contain smaller cycles.
DefDbl A-Z
Dim crlf$, ptseq(6), wayct, connectsto(6) As String, hct
'
'
' 4 5
' 1
' 2 3
'
'
' 6
'
'
Private Sub Form_Load()
ChDir "C:\Program Files (x86)\DevStudio\VB\projects\flooble"
Text1.Text = ""
crlf$ = Chr(13) + Chr(10)
Form1.Visible = True
DoEvents
connectsto(1) = "4523"
connectsto(2) = "4613"
connectsto(3) = "6512"
connectsto(4) = "1256"
connectsto(5) = "1346"
connectsto(6) = "2345"
addOn 1
Text1.Text = Text1.Text & Str(wayct) & Str(wayct / (4 ^ 6)) & crlf
Text1.Text = Text1.Text & hct & crlf & "done"
End Sub
Sub addOn(wh)
For mv = 1 To 4
pt = Val(Mid(connectsto(wh), mv, 1))
If ptseq(pt) = 0 Then
ptseq(pt) = wh
If wh = 6 Then
wayct = wayct + 1
pts$ = "": outstr$ = ""
For i = 1 To 6: pts$ = pts$ + LTrim(Str(ptseq(i))): Next
Do
ix = 0
For i = 1 To 6
If InStr(outstr$, LTrim(Str(i))) = 0 Then ix = i: Exit For
Next
If ix = 0 Then Exit Do
outstr$ = outstr$ + "("
Do
ix = ptseq(ix): ixs$ = LTrim(Str(ix))
If InStr(outstr$, ixs$) > 0 Then
outstr$ = outstr$ + ")"
Else
outstr$ = outstr$ + ixs$
End If
Loop Until Right(outstr$, 1) = ")"
Loop
For i = 1 To 6
Text1.Text = Text1.Text & ptseq(i)
Next
Text1.Text = Text1.Text & " "
Text1.Text = Text1.Text & outstr$ & crlf
If Len(outstr$) = 8 Then hct = hct + 1
Else
addOn wh + 1
End If
ptseq(pt) = 0
End If
Next
End Sub
|
|
Posted by Charlie
on 2014-08-12 11:41:39 |
computer solution
