Monday, September 15, 2008

Answer: Circling Bugs

The mathematical answer to yesterday's problem about the circling bugs is much prettier than the previous one about the demon and lake. We might as well just solve the problem for "n" bugs, then let n=4 for the square. It is a bit of a special case, though, which you might be able to solve completely by intuition.

We'll let n bugs be distributed uniformly around a unit circle, and set the units of time so their walking speed is one. Each begins chasing its nearest neighbor. Because the situation is exactly the same for every bug, the shape cannot distort. If it starts out a square, it stays a square. It can only get larger or smaller, translate, or rotate.

Also by symmetry, it can't translate. Which way would it go? If you let it translate in the direction of one bug, you're being unfair to all the others, but the problem is perfectly equable.

The shape will rotate and change size. Begin by imagining the case of infinitely many bugs, all point-sized, that form a complete circle. Then if they chase the bug in front of them, they'll simply march around the circle without it ever changing size at all.

If there are finite bugs, the shape must shrink as it rotates. In the case of a circle, the bug can never get any closer to the next guy he's chasing, because whoever he's chasing is running directly away from him at the same speed. But for a finite-sided object, the chased bug isn't running directly away any more. He's running at an angle, so the distance between the bugs decreases. Hence, the shape shrinks.

Down to business: find the equation for the motion of a bug.

Let's write an equation for its velocity in polar coordinates. If the position of the bug is (r,&theta), then the position of the next bug is (r,&theta+2&pi/n). Skipping a step or two, the velocity of the bug is (-sin[&pi/n],cos[&pi/n]). You get that by taking the geometric fact that the exterior angle of a regular n-gon is 2&pi/n, and noticing the deviation of the bug's path from a pure circular motion is exactly half that.

The bugs all start a distance of one from the center, so they will all meet there after a time (and distance walked) 1/sin(&pi/n). If there are lots of bugs, we can make a small-angle approximation to get n/&pi. More bugs, longer to meet.

Integrating the velocity above (and remembering that things are a little more complicated in polar coordinates, because d&theta/dt = v&theta/r(t)), we have, for a bug that begins at (1,0)
p(t) = (1-sin[&pi/n]*t,-cot[&pi/n]*ln[1-sin(&pi/n)t])
A logarithmic spiral.

For the case n=4, our formula says the bugs will walk a distance 21/2 before colliding. In this special case, the motion of the bug "running away" is at a right angle. He isn't running away at all, so much as trying to execute a circular orbit. So, from a bug's perspective, the distance between the bugs shrinks just as fast as it would if the one he were chasing were simply stationary.

No comments: