At a certain time, 101 ants are placed on a one-meter stick, with one of them, Alice, placed at the exact center. The positions of the other 100 ants are random, as are the directions they face. All ants start crawling in whatever direction they are facing, always traveling at one meter per minute. When an ant meets another ant or reaches the end of the stick, it immediately turns around and continues going in the other direction. What is the probability that after 1 minute Alice is at the exact center of the stick?
The simulation depends on the fact that once the motion starts, the ants remain in the same sequence from left to right. Calculation is made as to the minimum time to the next event (ants meeting or an ant getting to an end), and computing the positions after that time period and reversing any motion needing reversing at that time, until one minute has gone by.
DEFDBL A-Z
CLS
o(1) = 4: o(2) = 10: o(3) = 30: o(4) = 100
FOR osub = 1 TO 4
others = o(osub)
REDIM ant(others), spd(others), trk(others), t(others + 1), ct(others)
FOR tr = 1 TO 1000
tm = 0
ant(0) = .5
spd(0) = INT(RND(1) + .5) * 2 - 1
FOR i = 1 TO others
ant(i) = RND(1)
spd(i) = INT(RND(1) + .5) * 2 - 1
NEXT
FOR i = 0 TO others
trk(i) = i
NEXT
DO
done = 1
FOR i = 0 TO others - 1
IF ant(i) > ant(i + 1) THEN
SWAP ant(i), ant(i + 1)
SWAP trk(i), trk(i + 1)
done = 0
END IF
NEXT
LOOP UNTIL done
' FOR i = 0 TO others: PRINT USING " #.####"; ant(i); : NEXT
' PRINT ,
' FOR i = 0 TO others: PRINT trk(i); : NEXT
' PRINT
DO
IF spd(0) > 0 THEN t(0) = 999: ELSE t(0) = ant(0)
IF spd(others) < 0 THEN t(others + 1) = 999: ELSE t(others + 1) = 1 - ant(others)
FOR i = 1 TO others
IF spd(i - 1) <= spd(i) THEN
t(i) = 999
ELSE
t(i) = ABS(ant(i - 1) - ant(i)) / 2#
END IF
NEXT i
mn = 999
FOR i = 0 TO others + 1
IF t(i) < mn THEN mn = t(i)
NEXT
IF tm + mn > 1 THEN mn = 1 - tm
FOR i = 0 TO others
ant(i) = ant(i) + spd(i) * mn
NEXT
'PRINT mn,
'FOR i = 0 TO others
' PRINT i; ant(i); spd(i)
'NEXT
FOR i = 0 TO others - 1
IF ABS(ant(i) - ant(i + 1)) < .00000001# THEN
spd(i) = -spd(i)
spd(i + 1) = -spd(i + 1)
END IF
NEXT
IF ABS(ant(0)) < .00000001# THEN spd(0) = 1
IF ABS(ant(others) - 1) < .00000001# THEN spd(others) = -1
tm = tm + mn
LOOP UNTIL tm >= 1 OR mn > 1
' FOR i = 0 TO others: PRINT USING " #.####"; ant(i); : NEXT
' PRINT ,
' FOR i = 0 TO others: PRINT trk(i); : NEXT
FOR i = 0 TO others
IF ABS(ant(i) - .5) < .00001# THEN
'PRINT trk(i);
ct(trk(i)) = ct(trk(i)) + 1
END IF
NEXT
'PRINT
NEXT tr
PRINT others, ct(0)
NEXT
finds
extra
ants count
4 382
10 260
30 134
100 89
These are the counts of the times, out of 1000 trials for each line, that the ant initially in the center wound up in the center, when the number of additional ants is as specified in the "extra ants" column (so Alice makes one more).
So when there are 5 ants initially, including Alice at the center, Alice winds up in the exact center over 1/3 of the time. When there are 11 ants altogether, Alice winds up in the center over 1/4 of the time. With 31 ants, over 1/8 the time, but with 101 ants, under 1/10 the time.
In prior trials, with some of the commented-out lines still present, it was seen that one ant or another always winds up at the exact center.
As this is a simulation, we can't tell what the exact formula is, relating Alice's center termination probability to the number of other ants present.
Analysis:
Note that since the ants reflect off of one another, the order of the ants along the stick does not change.
However, if we weren't concerned about the identities of the ants, we could treat the ants as if they passed through one another, as that's what the interaction at a meeting of two ants would look like, given their perfectly elastic collisions. Each such ghostly ant would then travel exactly 1 meter and as a result wind up at the position complementary to its original position: if it started at position 0.1, for example, it would wind up at position 0.9. The important result of this is that every occupied position at the beginning of the 1-minute interval will correspond to an occupied complementary position at the end of the 1-minute interval. This explains why always at the end there is some ant exactly at the 0.5 position, even if it's not Alice.
Combining these two ideas--the identities of the ants remaining in the same order and the positions occupied being the set of positions complementary to the original positions--leads to the conclusion that Alice will be the ant occupying position 0.5 at the end if and only if there originally were the same number of ants to her left as there were to her right. That has probability C(x,x/2)/2^x, where x is the number of extra ants besides Alice. The case presented in the puzzle is that of x=100. Note that if there were an even number of ants originally, including Alice so that the extra ants would be odd in number, it would be impossible for Alice to wind up at the exact center of the stick, as there couldn't be the same number on either side of her. How does this formula compare with the simulation results. The expected numbers, rounded to the nearest integer, in each case are:
4 375
10 246
30 144
100 80
These are a good fit for the simulation results. All the simulation results lie within plus or minus the square root of the expected number--a rough rule-of-thumb approximation to the s.d. of a Poisson distribution, and in turn to that of a binary distribution.
So for this particular puzzle with 100 extra ants besides Alice, the answer is
C(100,50)/2^100 = 100891344545564193334812497256/1267650600228229401496703205376 = 12611418068195524166851562157/158456325028528675187087900672 ~= 0.0795892373871787614 or 1/12.5645129018549010066.
Edited on November 21, 2012, 9:12 pm
|
|
Posted by Charlie
on 2012-11-21 21:11:38 |
solution
