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

Home > Probability
Octahedron Vertex Ponder (Posted on 2014-08-12) Difficulty: 3 of 5
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.)
Solution 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.  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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information