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$ .

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.

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.

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:

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}$

$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.

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.

6 thoughts on “Ant-ics”

Mauro says:

July 20, 2014 at 6:16 am

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.

LikeLike

Sandy says:

October 27, 2014 at 9:24 pm

Your differential equation and general solution are incorrect.

dr/dθ = -r * cos(pi/N) / sin(pi/N)

That is, the sine should be in the denominator. This flip doesn’t change anything for the square, but it does matter for every other N-gon.

In fact, the whole problem becomes much easier if you consider dr/ds instead of dr/dθ. Going back to your trig diagram:

delta r = -cos(pi / N)
delta s = 1

.*. dr/ds = -cos(pi / N)

.*. s = r_0 / cos(pi/N)

If you use the correct differential equation for dr/dθ you also get:

s = r_0 / cos(pi/N) = sqrt(2 / (N*sin(2*pi/N)) * 1/cos(pi/N)

Your choice of unit area is also weird. It means you have a singularity as N approaches 2.

If you choose a constant r_0 instead (say, r_0 = 1) you get the much more intuitive result that N=2 minimizes the ant walking distance. This also corresponds to both ants walking straight towards the center of the n-gon.

LikeLike

1. Sandy says:
  
  October 27, 2014 at 10:09 pm
  
  Oh dear. Sadly I typed this up and submitted before I properly checked everything, and there is no way to edit myself to look smarter.
  
  The interior angle is not pi/N. The total of the interior angles of an N-gon is (N-2)*pi. Thus, the internal angle of a single vertex is (N-2)*pi/N. This makes nice intuitive sense, as it approaches pi as N grows large. Half of that angle is then (N-2)*pi/2N.
  
  Thus, the correct equation is:
  
  dr/ds = – cos((N-2)*PI/2N)
  s = r / cos((N-2)*PI/2N)
  
  Here is a plot of this function for constant r, showing the minimum at N=2:
  http://fooplot.com/#W3sidHlwZSI6MCwiZXEiOiIxLyhjb3MoKHgtMikqcGkvKDIqeCkpKSIsImNvbG9yIjoiIzAwMDAwMCJ9LHsidHlwZSI6MTAwMCwid2luZG93IjpbIi0wLjIwMDAwMDAwMDAwMDAwMDE1IiwiMTIuOCIsIi0zLjMyIiwiNC42OCJdfV0-
  
  The area of an n-gon with radius r is then:
  
  area = N*r^2 * cos(pi/N) * sin(pi/N)
  
  Again, this has pleasing limiting cases. It goes to 0 for N=2 and pi*r^2 for N large.
  
  s = 1 / (sqrt(N*cos(pi/N)*sin(pi/N)) * cos((N-2)pi/2N))
  
  This function shows a clear minimum near 3. I have plotted it here:
  http://fooplot.com/#W3sidHlwZSI6MCwiZXEiOiJzPTEvKHNxcnQoeCpjb3MocGkveCkqc2luKHBpL3gpKSpjb3MoKHgtMilwaS8oMngpKSkiLCJjb2xvciI6IiMwMDAwMDAifSx7InR5cGUiOjEwMDAsIndpbmRvdyI6WyItMS44MjQ5OTk5OTk5OTk5ODY5IiwiMTQuNDI0OTk5OTk5OTk5OTg4IiwiLTQuMzE5OTk5OTk5OTk5OTkyIiwiNS42Nzk5OTk5OTk5OTk5OTIiXX1d
  
  LikeLike
  
  1. jasmcole says:
    
    October 30, 2014 at 10:50 am
    
    Whoops! Thanks for pointing that out. I realise now that my choice of ‘equal area’ isn’t a very natural way of generalising the problem. A more continuous generalisation was pointed out to me by Gary Antonick at the NYT Numberplay blog
    
    http://wordplay.blogs.nytimes.com/2014/09/08/bugs/
    
    If the problem consists of two bugs which start at the same position but walk at a constant angle to the line joining them, the path length of the resulting spiral goes like sec(angle). This also simulates the problem of ants starting on the vertices of some polygons.
    
    LikeLike
  2. Li Wang says:
    
    April 29, 2016 at 2:51 am
    
    How do you get the area ?
    
    LikeLike
edwin30792 says:

February 6, 2015 at 8:06 am

What I find interesting is if N = ∞

A circle though it has no sides has an infinite amount of points, if you consider these points as sides with ants at each and try to have the ants follow the leading ant, they’d just remain on the circumference, never meeting in the center with their brothers and sisters. 😦

LikeLike