Antz!

AntLab

In this post I wanted to discuss a few nice problems related to ants (which is really just a metaphor for points moving along some curve).

These are problems that I have either heard by word of mouth or encountered in various places on the internet. The latter of these problems seemingly makes a popular job interview brainteaser.

Let’s start with the problem I personally enjoyed solving the most (so much I even bothered to put together a Flash app to illustrate the idea!).

Here is the statement:

Problem 1 (The Ant In The Middle):

n ants are randomly placed in a narrow test-tube of length 1 meter.
In addition Anton (the ant) is placed in the middle of the tube.

At a certain point in time, all ants start moving in a randomly chosen direction, left or right, at constant speed of 1 meter/minute.
When two ants collide they instantly reverse direction.
When an ant reaches the end of the test tube it also reverses direction.

After 1 minute all ants stop.

What is the probability (in terms of n) that Anton is again in the middle of the tube after 1 minute?

 
Below Flash application illustrates the procedure.

Press “New Sample” to generate a new distribution of ants and press “Start” to set them off.
The time is adjusted to the frame-rate of the animation.
(Click here to start the app if you see a blank space area below, or if you want a better quality version )

 

Solution:

Perhaps the key idea in this problem is to consider what would happen if the ants did not bounce against each other but instead continued straight through as if there were no other ants.
To emulate this behaviour we may think of the ants as exchanging coloured tokens upon collision.
Consider this conceptual construction as in below Flash app.
Anton is the black ant, starting with a black token.
Follow the black token, what do you notice?
(Click here to start the app if you see a blank space area below, or if you want a better quality version)

Likely you noticed that the black token simply passes through to the end of the test-tube and returns back into the middle exactly by the time the minute has ended.
This is of course expected since the velocity of the token is the same as the ant holding it at all times, and will therefore travel a distance of 1 meter during the minute it is under movement.
Thus the black token will start in the middle, travel half the meter tube and back.
As a consequence Anton ends up in the middle iff he holds the black token at the end of the minute.

By the same argument the other tokens all travel an equal distance.
Their end position represent a reflection in the mid-line of their starting position.

I recommend you take a screen shot of the start positions of the tokens and compare with their positions at the end of the animation.

The really observant reader may have noticed that Anton holds the black token at the end iff there are an equal number of ants on either side of Anton in the beginning.

Suppose there are k ants to the left and n-k ants to the right of Anton at the beginning.
Since at the end of the minute all tokens have been reflected in the mid-line, there will be an ant occupying the same space as each token (given that all ants hold a token at all times).
This determines how the ants are distributed after one minute.
Finally since the relative order of the ants remains the same (ants keep bouncing against their two next door neighbours) we know that the mid-tube ant will be the (n-k+1)^{th} ant from the left at the beginning.
The reason for this is that by the end of the minute all tokens have been reflected, so there will be n-k tokens to the left and k tokens to the right of the mid-tube ant.
Anton is the (k+1)^{th} ant from the left at the beginning and will be the (n-k+1)^{th} ant from the left at the end iff n-k+1 = k+1\; \Longrightarrow \; k = \frac{n}{2}.

This says that if Anton ends up in the middle of the tube at the end then the remaining ants are half to the left and half to the right of Anton at the beginning (clearly this is impossible if n is odd).

Now we are in a position to calculate the probability.

If n is odd then the probability is zero as we just established.

If n is even then there are \left( \begin{array}{c} n \\ n/2 \end{array} \right) ways of choosing ants for the left half. Once these are chosen the remaining ants go to the right half, so no further choice.
Each subset of the n ants determine a unique left-half, right-half partition and there are 2^n subsets in total.

Therefore the probability that that Anton finishes in the middle is \left( \begin{array}{c} n \\ n/2 \end{array} \right) /2^n when n is even.

 
The second problem is a variation of the previous problem.
The main difference now is that ants are placed on an open ended stick, and fall off if they reach the end.
We will now ask a slightly different question.
Check out the problem statement below:

Problem 2 (Falling ants):

n ants are placed on a meter stick, facing either left or right.

At a certain point in time the ants will start moving in the direction they are facing with constant speed of 1 meter/minute.

If the ants meet they will instantly reverse direction.

If an ant reaches the end of the stick it will simply fall off.

i) What is the longest time an ant can remain on the stick?

ii) Suppose the ants are placed uniformly at random along the stick.
What is the expected time the ants will remain on the stick before they have all fallen off?

Solution:

i) The idea here is similar to Problem 1. We consider a token being passed among the ants upon collision. Clearly the longest travel time for a token is 1 minute (a travel from end to end) by which time all tokens (and hence all ants) have necessarily fallen off.
So the answer is 1 minute.

ii) Because all ants are indistinguishable in this problem there is no difference between the ants reversing direction upon collision and simply going through each other.
See below animation, does it really matter which ant is which after collision?
(Click here if you see a blank space area below, or if you want a better quality version)

So if we can think of the ants as going through each other, the time it takes for an ant to fall off is simply the time it takes for an ant to walk to the end in a straight direction from its initial position.

In fact one realizes that the direction faced by the ant is irrelevant, it is only the distance to the end that matters. We may therefore assume all ants are facing the same direction.

Now, if we consider n ants facing to the right, the time it takes for all ants to fall off is clearly the time it takes for the leftmost ant to fall off.
To calculate the expected time it is therefore key to know the probability \mathbb{P}(X = x) of the leftmost ant being placed at a distance x from 0 (0 representing the leftmost end of the stick).
There are n ways we can fix an ant at position x.
Then the probability that remaining n-1 ants are positioned to the right of x is (1-x)^{n-1}.
Therefore \mathbb{P}(X = x) = n(1-x)^{n-1}.

Since velocity is 1 meter/minute the time it takes for all ants to fall off given a fixed x is \frac{1-x}{1} = 1-x minutes.
Hence the expected time is given by:
\mathbb{E}(T) = \int_0^1 (1-x).\mathbb{P}(X = x)dx =
\int_0^1 (1-x).n(1-x)^{n-1}dx = \left.-n\frac{(1-x)^{n+1}}{n+1}\right|_0^1 = \frac{n}{n+1}.

Let’s do a few sanity checks to better understand what this expression means.
Indeed if n=1 then the expected time is just equivalent to the expected position on the stick for a single ant, which is \frac{1}{2}.
As n grows we intuitively expect being less and less likely to have ants far away from 0 i.e we expect the time to tend closer and closer to the maximum from i), namely 1 minute.
Indeed lim_{n \rightarrow \infty} \frac{n}{n+1} = 1.

 
Below are some further problems on similar theme.
Feel free to try them.

Exercise 1: Ants on a Circle – Easy:

A number of ants are distributed randomly around a circle of perimeter 1 meter, facing clockwise or anti-clockwise direction.
At a certain point in time the ants start moving with speed 1 meter/minute in the direction they are facing around the circle.

When two ants meet they instantly reverse direction.

How long does it take before all ants have returned to their original position?

 

Exercise 2: Back To Square One – Easy:

If you resume the animation in Problem 1 after the first stop you will notice that all ants end up back where they started, holding the same token they began with.

Why is it that after 2 minutes all ants are back in their original position?

 

Exercise 3: Ant on a Rubber Band – Intermediate:

An ant is crawling along an infinitely stretchable rubber band of initial length 1 m.
The rubber band is fixed at the left end point.
The ant is crawling at a speed of 1 cm/s starting from the left end point.
Simultaneously the rubber band is being stretched at a speed of 1 m/s from the right end point.

Will the ant ever reach the other end of the rubber band, and if so how long will it take?

 
 
(Hint: The answer is Yes given sufficient time – Prove it by expressing the ants velocity as a first order differential equation in terms of its current position and the speed at which the ant is being moved as a result of the stretching).

Note: The problem is often referred to as a “paradox” given its counter-intuitive nature. The argument is popularly used to argue whether light from distant galaxies will ever reach the earth in an ever expanding universe.

Advertisements
This entry was posted in Probability, Uncategorized and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s