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

 Bird on a Wire (Posted on 2004-06-07)
A telephone wire stretched tight between two poles placed ten meters apart is a favorite resting spot for a flock of crows.

Suppose one morning two crows land on the wire, each at a random spot (the probability is uniformly distributed). With a bucket of paint and a brush you mark the stretch of wire between them. A certain length of wire will have been painted.

On average, what length of wire would you expect to have painted? Assume that each bird is a single point along the line, and so has no width.

Suppose instead that a dozen crows landed on the wire, each at an independent, random location, and you painted the stretch of wire between each bird and its nearest neighbor. On average, what total length of wire would you expect to have painted now?

And if a thousand crows landed?

A computer-generated solution could be found, but bonus points will be awarded for a formal proof!

 No Solution Yet Submitted by Sam Rating: 3.7000 (10 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 re(5): Computer simulation -- CORRECTION !! | Comment 15 of 42 |
(In reply to re(4): Computer simulation by Bob)

Indeed you are right.  I left out the last bird in my simulation.  In the new listing below, the line I had previously left out is

IF counted = 0 THEN t = t + bird(n) - bird(n - 1)

For 3 birds: 5.002182 +/- 0.007083
For 4 birds: 4.784935 +/- 0.007823
For 5 birds: 4.635778 +/- 0.006766
For 6 birds: 4.527006  +/- 0.006092

For 12 birds: 4.232355 +/- 0.005719

For 1000 birds: 3.89296 +/- 0.00403

DECLARE SUB sort (n1#, n2#)
CLEAR , , 4000
DEFDBL A-Z
n = 6
DIM SHARED bird(n)
RANDOMIZE TIMER

FOR trial = 1 TO 100000
FOR b = 1 TO n
bird(b) = RND(1)  ' measured in decameters
NEXT
sort 1, n
t = bird(2) - bird(1)
counted = 1
FOR b = 2 TO n - 1
IF bird(b + 1) - bird(b) < bird(b) - bird(b - 1) THEN
t = t + bird(b + 1) - bird(b)
counted = 1
ELSE
IF counted THEN
counted = 0
ELSE
t = t + bird(b) - bird(b - 1)
END IF
END IF
NEXT b
IF counted = 0 THEN t = t + bird(n) - bird(n - 1)
tot = tot + t: totSq = totSq + t * t
numTr = numTr + 1
IF numTr MOD 100 = 0 THEN
PRINT numTr,
avg = tot / numTr
v = ((totSq) - numTr * (avg * avg)) / (numTr - 1)
PRINT USING "  #.######"; avg; SQR(v / numTr)
END IF
NEXT trial

avg = tot / numTr
v = ((numTr * totSq) - (tot * tot)) / (numTr * (numTr - 1))
PRINT USING "  #.######"; avg * 10; 10 * SQR(v / numTr)

SUB sort (n1, n2)
IF n1 = n2 THEN EXIT SUB
pvt = bird(n1)
IF bird(n2) < pvt THEN pvt = bird(n2)
DO
i = n1 - 1: lower = 0
DO
i = i + 1
IF i <= n2 THEN IF bird(i) < pvt THEN lower = i
LOOP WHILE bird(i) <= pvt AND i <= n2
IF i > n2 AND lower = 0 THEN EXIT SUB
IF i > n2 THEN pvt = bird(lower)
LOOP WHILE i > n2
sw1 = i
i = n2 + 1
DO
i = i - 1
LOOP WHILE bird(i) > pvt AND i >= n1
sw2 = i
DO
IF sw2 < sw1 THEN
sort n1, sw1 - 1
sort sw2 + 1, n2
EXIT SUB
END IF
IF bird(sw1) > bird(sw2) THEN
SWAP bird(sw1), bird(sw2)
END IF
DO
sw1 = sw1 + 1
LOOP UNTIL bird(sw1) > pvt OR sw1 > sw2
DO WHILE sw2 >= sw1 AND bird(sw2) > pvt
sw2 = sw2 - 1
LOOP
LOOP
END SUB

 Posted by Charlie on 2004-06-07 20:07:16

 Search: Search body:
Forums (1)