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

 Octahedron Vertex Ponder (Posted on 2014-08-12)
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.

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer solution Comment 1 of 1
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.  permutationof bug cycle notation------123456465132 (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''`
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"

Text1.Text = Text1.Text & Str(wayct) & Str(wayct / (4 ^ 6)) & crlf

Text1.Text = Text1.Text & hct & crlf & "done"
End Sub

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
End If

ptseq(pt) = 0
End If
Next
End Sub

 Posted by Charlie on 2014-08-12 11:41:39

 Search: Search body:
Forums (0)