Let $n$ be a positive integer. There are $n$ 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 $n$.
The order of the ants along the line does not change; denote by \( v_{1}, v_{2}, \ldots, v_{n} \) the respective speeds of ants \( 1, 2, \ldots, n \) in this order. If \( v_{i-1} v_{i+1} \) for some \( i \in \{2, \ldots, n-1\} \), then, at each stage, ant \( i \) can catch up with ants \( i-1 \) or \( i+1 \) 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 defining the order of the ants, (i) \( v_{1} \geqslant \cdots \geqslant v_{n} \) or (ii) \( v_{1} \geqslant \cdots \geqslant v_{k-1} > v_{k} \leqslant \cdots \leqslant v_{n} \) for some \( k \in \{2, \ldots, n-1\} \). We need the following observation:

Claim. If \( v_{1} \geqslant \cdots \geqslant v_{m} \), then ants \( m-1 \) and \( m \) collide at most \( m-1 \) times.

Proof. The proof goes by induction on \( m \), the case \( m=1 \) being trivial. Since \( v_{m-1} \geqslant v_{m} \), ants \( m-1 \) and \( m \) can only collide if the former is moving towards the latter. Hence, between successive collisions with ant \( m \), ant \( m-1 \) must reverse direction by colliding with ant \( m-2 \). Since ants \( m-1 \) and \( m-2 \) collide at most \( (m-1)-1 = m-2 \) times by the inductive hypothesis, ants \( m \) and \( m-1 \) collide at most \( (m-2) + 1 = m-1 \) times.

Hence, in case (i), there are at most \( 0 + 1 + \cdots + (n-1) = n(n-1) / 2 \) collisions. In case (ii), applying the claim to ants \( 1, 2, \ldots, k \) and also to ants \( n, n-1, \ldots, k \) by switching their order, the number of collisions is at most \( k(k-1) / 2 + (n-k+1)(n-k) / 2 = n(n-1) / 2 - (k-1)(n-k) \). Since \( (k-1)(n-k) \geq 0 \), the number of collisions remains equal to \( n(n-1) / 2 \).

![](https://cdn.mathpix.com/cropped/2024_04_17_a4bb6022e2f5b324b7ecg-4.jpg?height=291&width=686&top_left_y=2270&top_left_x=685)

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 \( n(n-1) / 2 \).

## BxMO 2022: Problems and Solutions

#