Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose I put an ant in a tiny racecar on every face of a soccer ball. Each ant then drives around the edges of her face counterclockwise. The goal is to prove that two of the ants will eventually collide (provided they aren't allowed to stand still or go arbitrarily slow).

My brother told me about this result, but I can't quite seem to prove it. Instead of a soccer ball, we should be able to use any connected graph on a sphere (provided that there are no vertices of valence 1). We may as well assume there are no vertices of valence 2 either, since you can always just fuse the two edges.

I (and some people I've talked to) have come up with a number of observations and approaches:

  • Notice that if two ants are ever on the same edge, then they will crash, so the problem is discrete. You can just keep track of which edge each ant is on, and let the ants move one at a time. Then the goal is to show that there is no way for the ants to move without crashing unless some ant only moves a finite number of times.
  • You can assume all the faces are triangles. If there is a face with more than three edges, then you can triangulate it and make the ants on the triangles move in such a way that it looks exactly the same "from the outside". If there is a 1-gon, it's easy to show the ants will crash. If there is a 2-gon, it's easy to show that you can turn it into an edge without changing whether or not there is a crash.
  • One approach is to induct on the number of faces. If there is a counterexample, I feel like you should either be able to fuse two adjacent faces or shrink one face to a point to get a smaller counterexample, but I can't get either of these approaches to work.
  • If you have a counterexample on a graph, I think you get a counterexample on the dual graph. Have the dual ant be on the next edge along which a (non-dual) ant will pass through the given vertex.
  • It feels like there might be a very slick solution using the hairy ball theorem.
share|improve this question
    
Clarification: is the ant for a given face required to start on an edge of that face, or is it allowed to start in the interior of the face? The problem doesn't seem well-defined in the latter case, so I'm assuming the former. –  Michael Lugo Oct 24 '09 at 22:12
    
@Michael: yes, let's require the ants to start on some edge. –  Anton Geraschenko Oct 25 '09 at 3:30
1  
add comment

5 Answers

up vote 22 down vote accepted

This is known as Klyachko's Car Crash Theorem. It was proved in order to prove a theorem about finitely presented groups. In fact, the result allows the ants to move at arbitrary nonzero speeds so long as they make infinitely many loops around their 2-cell. The conclusion is that there's either a collision between ants in the interior of an edge, or else there is a `complete collision', which means that there's a collision at a vertex of all ants from adjacent edges.

EDIT: Oh, it's actually important that there are two complete collisions, which is somewhat harder to prove than one (a collision in the middle of an edge is also a complete collision.)

You can read an expository article by Colin Rourke here.

share|improve this answer
    
Ye, the paper also explains my proof below -- at the place where I say "now imagine the picture" I can say "read the bottom paragraph from page 5 and two top paragraphs from page 6". –  Ilya Nikokoshev Oct 24 '09 at 23:10
add comment

The post consists of initial ideas on top and the proof at the bottom.


I think the key idea is to perform the process opposite to what you describe about subdividing into triangles. Indeed, our problem can be thought of a plane graph where all ants are moving in the counterclockwise direction except one on the outer circle which goes clockwise.

Now notice that it seems you can actually combine several areas into one, it should look the same or worse on the outside, and you get at the end two ants on the same circle moving in the opposite directions.

"The same or worse" part is conjectural, but the intuition is that assuming you have just two circles with common edge, "the best" you can do is to let one go through the edge then immediately after that let the next one proceed. If you think about how that affects the outside world, it's very similar to having a single ant going around the whole stuff.


The proof. Let's introduce some notation. First, I'll be considering ants on the plane which together form something with an outer circle. Now let's assume the ants have decided upon the schedule and they started their driving. The outer ant is drunk driver that goes in a clockwise direction.

We will prove that the crash will necessarily occur before the drunk driver makes a full cycle.

Crucial lemma. Suppose I have two areas A and B combined by an edge and a schedule of driving that includes drunk driver making a full cycle. Then it's possible to choose one of the areas, A or B, and the modification of route of drunk driver that makes a full cycle around the chosen area.

The lemma is established by drawing a picture (update: an answer that refers to a paper with the solution was posted. the answer is the same so you can read the corresponding description there). After you have the lemma, you're done, because you see that there must be a simple face (minimal area) with a sober and drunk ants which must crash.

share|improve this answer
add comment

A quick comment on the idea of "a very slick solution using the hairy ball theorem". Any such very slick proof will surely only use the fact that the Euler characteristic is non-zero, and so should apply just as well to surfaces of higher genus (at least two). For instance, if I understand it correctly, then Reid's answer above would work just as well on a higher-genus surface, by the Poincare--Hopf Theorem.

But the theorem does not hold on surfaces of higher genus.

What follows would probably be better with pictures, but I'll try to describe it without and hope for the best.

For instance, it's easy to divide a torus into two rectangles such that there are "traffic schedules" with no crashes. (OK, the Euler characteristic of a torus is zero, but bear with me.) (Also, what is to ants as a traffic schedule is to cars?)

Now consider the surface of genus two as an octagon with sides identified, as usual. You can divide this into two rectangles and two pentagons in a way that mimics two copies of the torus picture in the previous paragraph: the surface is the union of two tori with boundary, and each torus is divided into a rectangle and a pentagon. Schedule each torus as before (stretching one of the ants' route over the fifth side of the pentagon). As only one ant from each torus traverses the fifth side of the pentagon, it is easy to arrange that the ants from different tori do so at different times.

Does that make sense, or does anyone want a picture?

EDIT:

Oh, and of course it follows that the theorem is also false on any orientable surface of even higher genus, as they all cover the surface of genus two.

share|improve this answer
add comment

I want to use the hairy ball theorem in the following way. Assume for simplicity that we start at time 0 and each ant returns to its original location at time 1. Suppose no two ants ever meet; then by compactness there is ε > 0 such that no two ants are pass through the same point at times closer than ε. Let's deform each face slightly inward near its vertices so that it becomes a smooth embedding of a disc into S^2. Also assume that ants move along the boundary with positive speed (so that time defines an homeomorphism from S^1 = [0, 1] / {0, 1} to the boundary of this disc).

For each face define a vector field on the boundary by p -> Rt(p)v(p), where v(p) is the unit tangent vector to the disc at p, t(p) is the time that the ant is at point p, and Ra is rotation (clockwise around the outward vector) by 2πa radians. This vector field extends over the disc. Extend it to the rest of the sphere by making it drop off to 0 rapidly outside the disc.

The sum of all these vector fields is nonzero everywhere except possibly near the vertices, because along any edge, the angle between the vectors coming from the two faces is bounded below in terms of ε. If one could control what happens near the vertices, this would contradict the hairy ball theorem.

share|improve this answer
    
You can perturb your fields a little -- the sum is a 2-vector, the condition that it doesn't hit the zero at all times is 1 condition. There's a finite number of points. Hence yes, sum is always nonzero. –  Ilya Nikokoshev Oct 24 '09 at 23:16
    
And I think you can define the time-dependent field that would somehow get rid of your condition on top. –  Ilya Nikokoshev Oct 24 '09 at 23:18
    
As far as I can tell, you're assuming that in the duration of one complete cycle, each ant goes around its face exactly once. But it could happen (for example) that one ant goes around three times while another ant goes around twice. –  Anton Geraschenko Oct 25 '09 at 3:28
    
Yes, that also seems to be a problem... it didn't seem like a very big assumption at the time, but now I'm not sure why I thought that. –  Reid Barton Oct 25 '09 at 4:26
    
How are you extending your vector field over the disc without introducing zeros in the interior? –  HJRW Nov 22 '09 at 21:03
add comment

Say there are n faces. The phase space on which the ants are moving are on is T^n, and the ants movement is described by a curve on T^n that has speed bounded from below in any direction. Hence, it suffices to show that if you cut T^n along the collision loci, you reduce the dimension of the H^1. This is a purely combinatiorial claim, which (it seems - I did not check all the details) you can prove by induction.

share|improve this answer
1  
Remember this should somehow use the fact that the topology is spherical -- ants live happily on the plane. –  Ilya Nikokoshev Oct 24 '09 at 22:19
1  
The purely combinatorial claim is false when n = 2. There are two faces (the north and south hemispheres) and two ants. The collision locus is the diagonal and this cuts T^2 into an annulus. So we do not reduce the dimension of anything. In addition, I have no idea what inductive step you are thinking of. –  Sam Nead Nov 23 '09 at 22:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.