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

Home > Probability
Creeping Ants (Posted on 2012-11-21) Difficulty: 4 of 5
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?

No Solution Yet Submitted by Danish Ahmed Khan    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 1 of 3

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

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 (10)
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