12
$\begingroup$

There are $N$ bugs in a plane. All bugs are moving at the same constant (nonzero) speed, but no two bugs are moving in the same direction (velocity vectors are of the same speed, but no two are parallel).

Prove that at some point in time $N$ bugs will form convex polygon.

Edit: Can you loosen up any of the conditions so that the statement still holds?

  • 0
    Could be worse, could've been snakes.2010-10-20

3 Answers 3

1

Suppose the bugs all started at the origin, then they would form a convex polygon at all times after $t = 0$. It should be noted we have some wiggle room - we may move any bug a small distance (proportional to time) and the polygon will remain convex.

Since our bugs lie initially within a circle, let them walk far enough that they are within the wiggle room of the convex polygon that would have been formed had they started at the origin. Hence the bugs form a convex polygon.

10

The counterexample I thought I had here doesn't work.

Here is a proof. Since none of the bugs are moving in the same direction, any pair of lines determined by the velocity vectors intersect. Let $C$ denote the convex hull of these intersection points. Since after waiting a sufficiently long period of time the bugs will be arbitrarily far away from $C$, if we "zoom out" far enough $C$ will become arbitrarily small with respect to the convex hull of the location of the bugs. It follows that we can assume that $C$ is arbitrarily small to begin with.

We now claim that the bugs eventually form a convex polygon in which the angle at each vertex is strictly less than $\pi$. To do this it suffices to examine a configuration of three bugs $a, b, c$ in consecutive counterclockwise order. Pick a coordinate system in which the centroid of $C$ is the origin and $b$ travels in the positive $y$-direction (hence $a$ travels to the right and $c$ travels to the left). Then it is easy to see that regardless of where $a, b, c$ initially begin along their routes, $b$ will eventually have $y$-coordinate greater than either $a$ or $c$, so angle $abc$ will eventually be strictly less than $\pi$.

It follows that by waiting sufficiently long the bugs will always form a convex polygon. In fact, the bugs are approximating the convex polygon whose vertices are the unit velocity vectors of the bugs.

  • 0
    (cont.) and the subspace of X where C is a point is dense. But to specify the topologies on X and Y and to prove that f is continuous really takes more effort than it's worth considering that the second half of the argument tells you precisely what f does.2010-08-12
8

Assuming no bugs get squashed in the process:

At $\lim_{t\to\infty}$ when $t$ is time, the bugs' beginning points shrink to $\frac{P}{t} = 0$ as observed when zoomed out. This means the final position of each bug lies on $\sqrt{r^2 + (vt)^2}$, or on the edge of a huge circle. Thus, you can see that all the bugs make a convex polygon (or $N$-gon) since a circle can be thought of as a regular (and convex) $\infty$-gon.

Of course this isn't the most vigorous proof in the world, but it's written in the style that most humans can understand.

  • 0
    @Jones, they can. This simply means it will take longer time for the bugs to form a convex polygon. In other words, the angles between the bugs will increase to 180 degrees as time passes.2010-08-12