Ant-ics

I was told an example interview question involving ants following one another around in a square, and it continued to bug me for a while (pun wholeheartedly intended). The specific wording of the problem is this:

4 ants are place at the corners of a square of unit area, and each ant walks towards the ant ahead of it. What is the shape of the path the ants take, and how far do they walk until they meet?

Sounds fun and relatively simple (though not so much in an interview situation!), lets have a look.

Now, due to the symmetry of the problem we can just focus on one ant as it follows its neighbour ahead of it – pick the rightmost ant as depicted below, and assign it polar coordinates (r,\theta). I’ve drawn the starting positions of the 4 ants, and how 2 of them have moved after a short time, say \Delta t.

Setup

We’d need to find the path of the ant, so we need to know how r changes as a function of \theta. The direction of motion is always towards the next ant which is moving in the same way but rotated by \pi/2, so it should be fairly obvious that all 4 ants continue to remain on the corners of a square as it rotates and shrinks and they gradually meet each other. The paths should look like a spiral then, and we expect the ants to meet in the middle.

If we zoom in slightly and add some notation, we can decompose the displacement vector along the r and \theta directions. In this geometry the displacement vector is always at pi/4 from the direction of increasing \theta, and this stays the same as the ants walk towards one another.

Setup_zoom

Decomposing displacement components then, we have in some small time period (assuming unit velocity, we’re only concerned in relative displacements so the velocity doesn’t matter)

\Delta r = -\cos(\pi/4)

r\Delta \theta = \sin(\pi/4)

\Rightarrow \frac{\Delta r}{\Delta \theta} = -r\frac{\sin(\pi/4)}{\cos(\pi/4)} = -r.

If we then take the limits \Delta r \rightarrow 0, \Delta \theta \rightarrow 0 we end up at the nice and simple differential equation

\frac{dr}{d\theta} = -r

which I’m sure 9 of 10 people you meet in the street would be able to solve. We’ve assumed a unit square, so the initial ant radius at \theta = 0 is 1/\sqrt{2}, and the solution is

r = \frac{1}{\sqrt{2}}e^{-\theta}

which is surprisingly simple, and much simpler than had we tried cartesian coordinates. The setup of the problem is perhaps designed to encourage a cartesian approach, where I’m sure the poor interviewee would get quickly bogged down in an awful differential equation to solve.

It is interesting to note that this is a logarithmic spiral which is self-similar (another type of fractal?) and occurs throughout nature

http://en.wikipedia.org/wiki/Logarithmic_spiral

We can animate the ants now, and its clear that, as we argued, they stay on the vertices of a square as they spiral inwards.

Ants

Finally, to solve the problem and get our job shepherding insects, we have to work out the path length s. This is simple now we have all the relevant information, we know we’re going from \theta = 0 to \theta \rightarrow \infty so we just have to perform the integral

s = \int_0^{\infty} \sqrt{r^2d\theta^2 + dr^2}

s = \int_0^{\infty} \sqrt{r^2 + \left(\frac{dr}{d\theta}\right)^2}d\theta

s = \sqrt{2}\int_0^{\infty} r d\theta = \int_0^{\infty} e^{-\theta} d\theta = 1.

So, after all that we end up, of course, at 1. There are only two numbers in physics, 1 and \pi, so in hindsight perhaps it would have been prudent to guess one of these and bask in our adulation when we were correct. However, this might not have made for a satisfactory interview and surely a follow-up question would be inbound imminently. Well, lets prepare for just such an occasion! We just dealt with the situation of 4 ants on a square, so naturally we should try and generalise this result. What about regular triangles, pentagons, circles etc?

Again we can exploit the symmetry of the problem and just focus on one ant. The only thing that has changed now is the angle the displacement vector makes with the increasing-\theta vector:

Setup_zoom_ngon

We’ve assumed a regular N-sided polygon (an N-gon), which means the ants are distributed round in steps of 2\pi/N, i.e. for a square N=4 and the steps are \pi/2 as in the previous diagram. The new equations for changes in r and \theta are then

\Delta r = -\cos(\pi/N)

r\Delta \theta = \sin(\pi/N)

\Rightarrow \frac{\Delta r}{\Delta \theta} = -r\frac{\sin(\pi/N)}{\cos(\pi/N)} \Rightarrow \frac{dr}{d\theta} = -r\tan{\pi/N}

so

r = r_0e^{-\tan(\pi/N)\theta}

for some initial radius r_0. How should we compare these N-gons? If we stick with 1 unit to a side they will rapidly become much larger than our initial square and the results won’t be comparable. We’ll stick with the requirement that the area of the N-gon is 1 unit, which leads to the requirement for r_0 that

r_0 = \sqrt{\frac{2}{N}\frac{1}{\sin(2\pi/N)}}

so finally the expression for the paths the ants take for our unit area N-gons becomes

r = \sqrt{\frac{2}{N}\frac{1}{\sin(2\pi/N)}}e^{-\tan(\pi/N)\theta}.

and of course if we set N=4 we recover the previous expression. We can churn through the same algebra as before to find the path length too

s_N = \int_0^{\infty} \sqrt{r^2 + \left(\frac{dr}{d\theta}\right)^2}d\theta

s_N = \int_0^{\infty} r\sqrt{1 + \tan^2(\pi/n)}d\theta

s_N = \sqrt{\frac{2}{N}\frac{1}{\sin(2\pi/N)}}\sqrt{1 + \tan^2(\pi/N)}\int_0^{\infty} e^{-\tan(\pi/N)\theta}d\theta

s_N = \sqrt{\frac{2}{N}\frac{1}{\sin(2\pi/N)}}\frac{\sec(\pi/N)}{\tan(\pi/N)}

s_N = \frac{1}{\sqrt{N\sin^3(\pi/N)\cos(\pi/N)}}.

This is a nice and simple formula that, again, reduces to 1 if we select N=4. We can plot this out to see how it varies, and if we were to allow noninteger N (whatever that means…) there are actually 2 solutions for a unit path length.

LengthPlot

There is a minimum between a triangle and square, but it doesn’t occur at 1 or \pi so I have no idea how to work that out. Actually its the solution to an algebraically unsolvable equation, so there’s not much to be learnt there. As N increases s_N \rightarrow N\pi^{-3/2} and the path length increases without limit. This makes sense, as the shapes become more and more circular the spirals become more and more shallow and eventually the poor ants are just wandering around in circles. At this point in the interview, which I assume is for some kind of bug exhibit at the zoo, you should of course decry this inhumanity of the poor ants (inhumantity?) forever walking in circles and storm out. Not before showing the following fancy animation to prove your newfound anti-aliasing skills though.

Ants

About these ads

One thought on “Ant-ics

  1. I think it’s actually more interesting to consider the side length to be 1, since that keeps the distance between the ants the same. The path length turns out to be 1/(2sin^2 (π/N)), which does reduce to 1 for a square. The radius when the side length is 1 is 1/(2sin(π/N)), so we also get the result that the path length is r/sin(π/N), itself a pretty interesting result. To get a path length of 1, you want the radius to be sin(π/N), which means that the area is N/2 sin^2 (π/N) sin(2π/N) = N sin^3 (π/N) cos (π/N). Interestingly, as N gets large, the area gets small as 1/N^2, which means that the spirals get tighter and tighter.

    Like

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