Problem:
Let be a positive integer. There are ants walking along a line at constant nonzero speeds. Different ants need not walk at the same speed or walk in the same direction. Whenever two or more ants collide, all the ants involved in this collision instantly change directions. (Different ants need not be moving in opposite directions when they collide, since a faster ant may catch up with a slower one that is moving in the same direction.) The ants keep walking indefinitely.
Assuming that the total number of collisions is finite, determine the largest possible number of collisions in terms of .
Solutions — 2
Solution 1
Solution:
The order of the ants along the line does not change; denote by the respective speeds of ants in this order. If for some , then, at each stage, ant can catch up with ants or irrespective of the latters' directions of motion, so the number of collisions is infinite. Hence, if the number of collisions is finite, then, up to switching the direction definining the order of the ants, (i) or (ii) for some . We need the following observation:
Claim. If , then ants and collide at most times.
Proof. The proof goes by induction on , the case being trivial. Since , ants and can only collide if the former is moving towards the latter. Hence, between successive collisions with ant , ant must reverse direction by colliding with ant . Since ants and collide at most times by the inductive hypothesis, ants and collide at most times.
Hence, in case (i), there are at most collisions. In case (ii), applying the claim to ants and also to ants by switching their order, the number of collisions is at most .
Now take a coordinate along the line, and put ants at with positive initial velocities and speeds , for some . For , collisions occur according to the pattern shown below for , which clearly extends to all values of in such a way that ants and collide exactly times for . This yield collisions in total. For all sufficiently small , the number of collisions remains equal to .

This shows that the upper bound obtained above can be attained. If the number of collisions is finite, the largest possible number of collisions is therefore indeed .
Solution 2
Solution:
We show that there are at most collisions if the number of collisions is finite as in Solution 1.
To show that the upper bound of collisions can be attained, we construct, inductively, an example of ants colliding times, the speeds of the ants decrease from left to right, and after all collisions all ants move towards the left, with the possible exception of the rightmost ant. In every case, we will label the ants from left to right. For this is trivial. For , we use the construction for ants (now labelled ). We add ant 1 on the left, moving towards the right, faster than all other ants (so that the speeds of the ants still decrease from left to right), and in such a way that its first collision (with ant 2) happens after all collisions of the other ants. Now the following events happen (in this order) for : ants and collide, after which ant moves to the left and ant moves to the right. These collisions do happen because the speeds of the ants decrease from left to right. Then ants and also collide, resulting in ant moving to the left. This shows that there are (at least) collisions. There are in fact no more collisions since the speeds of the ants decrease from left to right; alternatively, this follows from the upper bound proved previously. Since all ants except ant are moving towards the left after the collisions, this completes the inductive construction.