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

Home > Probability
Eight Points (Posted on 2016-08-24) Difficulty: 3 of 5
Eight points are selected at random from the interior of a unit circle.

What is the probability that these eight points constitute the eight vertices of a convex octagon?

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution simulation | Comment 1 of 3
For purposes of testing whether the condition is true in each simulation trial, it seems the best way is to find the vector angle from each point to each other point. If each of the eight points has some gap in the ordered array of vector angles that exceeds 180°, then the eight points form a convex octahedron.  The converse is obviously true, so it's an if-and-only-if condition (both necessary and sufficient) so long as my first statement is correct, and I think it is.

DefDbl A-Z
Dim crlf$, x(8), y(8), direction(8, 8), raddeg, dir(8), no(8)

Private Sub Command1_Click()
  Form_Load
End Sub

Private Sub Form_Load()
 Form1.Visible = True
 
 Randomize Timer
 'Text1.Text = ""
 crlf = Chr$(13) + Chr$(10)
 
 raddeg = 45 / Atn(1)
 
 For tr = 1 To 10000
   For pt = 1 To 8
    Do
     xp = 2 * Rnd(1) - 1
     yp = 2 * Rnd(1) - 1
    Loop Until xp * xp + yp * yp < 1
    x(pt) = xp: y(pt) = yp
   Next
   For pt = 1 To 8
     x0 = x(pt): y0 = y(pt)
     For i = 1 To 8
       If i <> pt Then
         xp = x(i): yp = y(i)
         xdiff = xp - x0: ydiff = yp - y0
         angle = atan(ydiff / xdiff)
         If xdiff < 0 Then angle = angle + 180
         If angle < 0 Then angle = angle + 360
         If angle > 360 Then angle = angle - 360
         direction(pt, i) = angle
         direction(i, pt) = angle - 180
         If direction(i, pt) < 0 Then direction(i, pt) = direction(i, pt) + 360
         If direction(i, pt) > 360 Or direction(i, pt) = 0 Or direction(pt, i) > 360 Or direction(pt, i) = 0 Then
          xxx = xxx
         End If
       End If
     Next
   Next pt
   hit = 1
   For pt = 1 To 8
     For i = 1 To 8
       dir(i) = direction(pt, i)
        If dir(i) = 0 Then
         xxx = xxx
        End If
     Next
     
     Do
        done = 1
        For i = 1 To 7
          If dir(i + 1) < dir(i) Then
            h = dir(i)
            dir(i) = dir(i + 1)
            dir(i + 1) = h
            done = 0
          End If
        Next
     Loop Until done
     found = 0
     For i = 2 To 7
        If dir(i + 1) - dir(i) >= 180 Then
         found = 1: Exit For
       End If
     Next
     If dir(2) - dir(8) + 360 >= 180 Then found = 1
     If found = 0 Then
       hit = 0: Exit For
     End If
   Next
   If hit Then
      hitct = hitct + 1
      If hitct > 30000 Then
        For pnt = 1 To 8
            Text1.Text = Text1.Text & mform(x(pnt), "#0.0000") & mform(y(pnt), "#0.0000") & "     "
        
        
            For i = 1 To 8
             dir(i) = direction(pnt, i)
             no(i) = i
            Next
            Do
              done = 1
              For i = 1 To 7
                If dir(i + 1) < dir(i) Then
                  h = dir(i): h2 = no(i)
                  dir(i) = dir(i + 1): no(i) = no(i + 1)
                  dir(i + 1) = h: no(i + 1) = h2
                  done = 0
                End If
              Next
            Loop Until done
            For i = 2 To 8
             Text1.Text = Text1.Text & Str(no(i)) & mform(dir(i), " ###0.0") & "  "
            Next
            Text1.Text = Text1.Text & crlf
              
       
        Next
        
        Text1.Text = Text1.Text & crlf
      End If
   End If
   trct = trct + 1
 Next tr
 
 
 
 Text1.Text = Text1.Text & crlf & hitct & Str(trct) & Str(hitct / trct) & " done"
  
End Sub

Function atan(x)
  atan = raddeg * Atn(x)
End Function

Function mform$(x, t$)
  a$ = Format$(x, t$)
  If Len(a$) < Len(t$) Then a$ = Space$(Len(t$) - Len(a$)) & a$
  mform$ = a$
End Function

The coding of "hitct > 30000" is the equivalent of commenting out that set of code. For one run it was given as hitct < 3, to get details on two sample hits (seen at the bottom, below).

hits  trials    fraction
100 10000 .01 done
92 10000 .0092 done
88 10000 .0088 done
86 10000 .0086 done
81 10000 .0081 done
78 10000 .0078 done
91 10000 .0091 done
66 10000 .0066 done
87 10000 .0087 done
83 10000 .0083 done
95 10000 .0095 done
99 10000 .0099 done
79 10000 .0079 done
89 10000 .0089 done
98 10000 .0098 done
82 10000 .0082 done
87 10000 .0087 done
83 10000 .0083 done
88 10000 .0088 done
89 10000 .0089 done
94 10000 .0094 done
103 10000 .0103 done
91 10000 .0091 done
79 10000 .0079 done
91 10000 .0091 done
82 10000 .0082 done
78 10000 .0078 done
81 10000 .0081 done
90 10000 .009 done
90 10000 .009 done
97 10000 .0097 done
99 10000 .0099 done
112 10000 .0112 done
95 10000 .0095 done
71 10000 .0071 done
79 10000 .0079 done
83 10000 .0083 done
91 10000 .0091 done
97 10000 .0097 done
91 10000 .0091 done
88 10000 .0088 done
83 10000 .0083 done
74 10000 .0074 done
95 10000 .0095 done
93 10000 .0093 done
60 10000 .006 done
96 10000 .0096 done
82 10000 .0082 done

That's 48 rows for 480,000 trials, with 48 reseedings of the random number generator with new seeds based on the time of hitting the command button.

Excel tells me the total hits is 4206.  4206/480000 = .0087625, so it seems the probability is less than 1% (about 0.88%) or about 1 in 114.

Two sample successful hits are shown below. In each case the x and y coordinates of each of the eight points are shown. To the right of each such pair are the vector angles to the other points in ascending order, each preceded by the number (printout line) of the other point, so in the first set, the angle from the first point to the seventh point is 165.7. The angle from the first point to the fifth is 291.2 and this is in fact the larger than 180° angle for point 1: pt5-pt1-pt7. All angles are measured counterclockwise, so no internal angles are considered. These verify as convex octahedra.

 0.5759 0.3652      7  165.7   6  206.6   4  219.1   3  232.1   2  240.6   8  257.9   5  291.2  
-0.1620-0.9422      8   29.5   5   35.0   1   60.6   7   92.4   6  118.3   4  148.9   3  159.5  
-0.3791-0.8608      8   16.1   5   26.8   1   52.1   7   83.8   6  105.4   4  142.1   2  339.5  
-0.6629-0.6402      5   14.6   1   39.1   7   70.1   6   76.7   3  322.1   2  328.9   8  359.6  
 0.8171-0.2557      1  111.2   7  141.6   6  177.9   4  194.6   3  206.8   2  215.0   8  220.6  
-0.5599-0.2045      1   26.6   7   66.5   4  256.7   3  285.4   2  298.3   8  334.3   5  357.9  
-0.2241 0.5696      6  246.5   4  250.1   3  263.8   2  272.4   8  295.6   5  321.6   1  345.7  
 0.3594-0.6474      5   40.6   1   77.9   7  115.6   6  154.3   4  179.6   3  196.1   2  209.5
  
 0.0832-0.7422      2   75.8   7   80.6   3   86.9   5   97.8   6  129.1   8  145.5   4  149.6  
 0.2145-0.2217      7   84.6   3   93.5   5  112.7   6  161.8   8  188.4   4  197.1   1  255.8  
 0.1598 0.6710      5  215.3   6  222.5   8  235.9   4  240.8   1  266.9   2  273.5   7  295.2  
-0.4545-0.4273      2   17.1   7   49.4   3   60.8   5   68.3   6  101.1   8  122.7   1  329.6  
-0.0860 0.4969      3   35.3   6  225.7   8  242.5   4  248.3   1  277.8   2  292.7   7  348.6  
-0.5433 0.0275      7   25.8   3   42.5   5   45.7   8  274.2   4  281.1   1  309.1   2  341.8  
 0.2758 0.4241      3  115.2   5  168.6   6  205.8   8  223.6   4  229.4   1  260.6   2  264.6  
-0.5171-0.3298      2    8.4   7   43.6   3   55.9   5   62.5   6   94.2   4  302.7   1  325.5  

Edited on August 24, 2016, 6:31 pm
  Posted by Charlie on 2016-08-24 18:30: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 (7)
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