MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi everybody,

Kindly forgive me if this question is too trivial for this forum. But I am just curious to find the right solution.

There are n ants ( of negligible width ) on 1m rod. They move at 1m/s and if they collide they reverse their direction without any delay. The ants fall off when they approach the end of the rod.

What will be the maximum time required for all ants to fall off ?

Intuitively an answer can be arrived at.

But is there a formal proof or solution for this ? How does one approach this problem for a mathematical proof ?

Thanks in advance, Ashish

share|cite|improve this question

closed as too localized by Steve Huntsman, Reid Barton, Yemon Choi, Scott Morrison Mar 15 '10 at 21:11

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

Answer is 1 sec. You may think that ants freely pass, without any colliding. – Petya Mar 15 '10 at 17:50
Imagine that colliding ants switch hats. Then the hats ignore each other and fall off within 1 second. – Douglas Zare Mar 15 '10 at 17:50
Those are extremely fast ants! – Harald Hanche-Olsen Mar 15 '10 at 17:53
Instead of "Intuitively an answer can be arrived at" it would be much better to say "I think the answer is ___, because ..." – Reid Barton Mar 15 '10 at 18:04
Douglas, when I first read your comment I thought you were saying something about the hats falling off of the ants and got terribly confused. – Qiaochu Yuan Mar 15 '10 at 19:27

Answer: 1 second. It does not matter if they reverse their directions or move through each other. After a collision of ants A and B, A moves exactly as B would without the collision, and vice versa. So if you "exchange identities" of ants on each collision, you just see they move forward until they fall.

By the way, this is a partial case of an interesting dynamical system where you allow the ants to have different masses and velocities, and to reflect from each other according to the laws of classical mechanics. And this generalization is a partial case of a billiard dynamical system. In higher dimensions (where ants are balls moving in the space) problems like how to estimate the total number of collisions get very hard and require some really modern mathematics (Alexandrov spaces in particular).

share|cite|improve this answer
Sorry, I did not update the browser window and did not notice that the puzzle is already solved in comments. – Sergei Ivanov Mar 15 '10 at 18:37
The intuitive answer which I knew is this one. i.e one can assume that ants pass freely without collision. But I am somehow not convinced of this being a formal proof for this problem. But yes, assuming that there is such a proof, one can say on its basis that it appears as if the ants move on freely without collision. – Ashish Mar 15 '10 at 19:43
There are no fully formalized proofs except for the most basic, algebraic-style things - search for "formalized mathematics" or "machine verified proofs". A practical definition of a mathematical proof is "a text that an expert mathematician can formalize down to any level of detail if paid enough". Ants switching hats is a perfect proof, that every sensible person would prefer over a long and messy series of symbols expressing the same idea in a formalized language. – Sergei Ivanov Mar 15 '10 at 20:53
There are formal proofs of the Jordan curve theorem. For a discussion see Hales' paper "The Jordan curve theorem, formally and informally". – Sam Nead Mar 15 '10 at 21:17
The hats-switching proof is not only mathematically correct but also goes to the essence of the matter. Hence it can also easily answer other related questions such as how many head-bumps occurred before all the ants fell of the rod. – Anonymous Mar 15 '10 at 21:21

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