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 )
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?
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.