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

 Don't Be a Square (Posted on 2003-05-19)
Given n points drawn randomly on the circumference of a circle, what is the probability they will all be within any common semicircle?

 See The Solution Submitted by DJ Rating: 4.4667 (15 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Simulation | Comment 14 of 21 |
In a simulation of 1,000,000 trials, adding 11 points at random, one at a time, and noting at each number of points from 3 to 11 the span taken up, the following numbers appear:
3 187486 561980 749466 250534 0 1000000
4 62659 437033 499692 500308 0 1000000
5 19439 292777 312216 683941 3843 1000000
6 5880 181339 187219 787418 25363 1000000
7 1662 107769 109431 816731 73838 1000000
8 492 62104 62596 790008 147396 1000000
9 153 35259 35412 726006 238582 1000000
10  34 19706 19740 643549 336711 1000000
11  7 10834 10841 554994 434165 1000000

The middle column is the number, for the given number of points plotted so far, that are within 180 degrees. The two numbers before this are for the first and second quadrants (fitting within 90 degrees, fitting more than 90 less than 180). After the 180 figure come the 3rd and 4th quadrants and the final column has the total of 1,000,000 for a check.

The program simulating the random placement placed the first point always at 0 and everything else is relative to that:

DIM span(11, 360)
DIM pt(11)
PRINT : PRINT : PRINT
RANDOMIZE TIMER
FOR trial = 1 TO 1000000
ERASE pt
pt(1) = 0
pt(2) = RND(1) * 360
FOR ptNo = 3 TO 11
cPosn = RND(1) * 360
ins = 0
FOR i = 2 TO ptNo - 1
IF pt(i) > cPosn THEN
FOR j = i TO ptNo
SWAP pt(j), cPosn
NEXT
ins = 1
EXIT FOR
END IF
NEXT
IF ins = 0 THEN pt(ptNo) = cPosn
lgGap = 0
FOR i = 2 TO ptNo
IF pt(i) - pt(i - 1) > lgGap THEN lgGap = pt(i) - pt(i - 1)
NEXT
IF 360 - pt(ptNo) > lgGap THEN lgGap = 360 - pt(ptNo)
lgSpan = 360 - lgGap
span(ptNo, INT(lgSpan)) = span(ptNo, INT(lgSpan)) + 1
NEXT
NEXT trial

FOR i = 3 TO 11
tot = 0: subtot = 0: st2 = 0
PRINT USING "### "; i;
FOR j = 1 TO 360
subtot = subtot + span(i, j - 1)
' j - 1 because of original truncation
st2 = st2 + span(i, j - 1)
tot = tot + span(i, j - 1)
IF j / 90 = INT(j / 90) THEN
PRINT USING "#######"; subtot;
subtot = 0
END IF
IF j = 180 THEN
PRINT USING " ######## "; st2;
st2 = 0
END IF
NEXT
PRINT USING "##########"; tot;
tot = 0
PRINT
NEXT

 Posted by Charlie on 2003-05-20 10:03:08

 Search: Search body:
Forums (0)