1
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 6
    $\begingroup$ Answer is 1 sec. You may think that ants freely pass, without any colliding. $\endgroup$
    – Petya
    Commented Mar 15, 2010 at 17:50
  • 11
    $\begingroup$ Imagine that colliding ants switch hats. Then the hats ignore each other and fall off within 1 second. $\endgroup$
    – Douglas Zare
    Commented Mar 15, 2010 at 17:50
  • 8
    $\begingroup$ Those are extremely fast ants! $\endgroup$
    – Harald Hanche-Olsen
    Commented Mar 15, 2010 at 17:53
  • 5
    $\begingroup$ Instead of "Intuitively an answer can be arrived at" it would be much better to say "I think the answer is ___, because ..." $\endgroup$
    – Reid Barton
    Commented Mar 15, 2010 at 18:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Commented Mar 15, 2010 at 19:27

1 Answer 1

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ Sorry, I did not update the browser window and did not notice that the puzzle is already solved in comments. $\endgroup$
    – Sergei Ivanov
    Commented Mar 15, 2010 at 18:37
  • $\begingroup$ 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. $\endgroup$
    – Ashish
    Commented Mar 15, 2010 at 19:43
  • $\begingroup$ 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. $\endgroup$
    – Sergei Ivanov
    Commented Mar 15, 2010 at 20:53
  • $\begingroup$ There are formal proofs of the Jordan curve theorem. For a discussion see Hales' paper "The Jordan curve theorem, formally and informally". $\endgroup$
    – Sam Nead
    Commented Mar 15, 2010 at 21:17
  • $\begingroup$ 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. $\endgroup$
    – Anonymous
    Commented Mar 15, 2010 at 21:21

Not the answer you're looking for? Browse other questions tagged .