Maths Olympiad Prep

Library / /4 of 9

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Benelux Mathematical Olympiad

Problem:
Let nn be a positive integer. There are nn 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 nn.

Solutions — 2

Solution 1

Solution:
The order of the ants along the line does not change; denote by v1,v2,,vnv_{1}, v_{2}, \ldots, v_{n} the respective speeds of ants 1,2,,n1,2, \ldots, n in this order. If vi1<vi>vi+1v_{i-1}<v_{i}>v_{i+1} for some i{2,,n1}i \in\{2, \ldots, n-1\}, then, at each stage, ant ii can catch up with ants i1i-1 or i+1i+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 definining the order of the ants, (i) v1vnv_{1} \geqslant \cdots \geqslant v_{n} or (ii) v1vk1>vkvnv_{1} \geqslant \cdots \geqslant v_{k-1}>v_{k} \leqslant \cdots \leqslant v_{n} for some k{2,,n1}k \in\{2, \ldots, n-1\}. We need the following observation:
Claim. If v1vmv_{1} \geqslant \cdots \geqslant v_{m}, then ants m1m-1 and mm collide at most m1m-1 times.

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

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

Now take a coordinate xx along the line, and put ants at x=1,2,,nx=1,2, \ldots, n with positive initial velocities and speeds v1==vn1=1,vn=εv_{1}=\cdots=v_{n-1}=1, v_{n}=\varepsilon, for some ε\varepsilon. For ε=0\varepsilon=0, collisions occur according to the pattern shown below for n=5n=5, which clearly extends to all values of nn in such a way that ants mm and m+1m+1 collide exactly mm times for m=1,2,,n1m=1,2, \ldots, n-1. This yield 1+2++(n1)=n(n1)/21+2+\cdots+(n-1)=n(n-1) / 2 collisions in total. For all sufficiently small ε>0\varepsilon>0, the number of collisions remains equal to n(n1)/2n(n-1) / 2.

Figure 1

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

Solution 2

Solution:
We show that there are at most n(n1)/2n(n-1) / 2 collisions if the number of collisions is finite as in Solution 1.

To show that the upper bound of n(n1)/2n(n-1) / 2 collisions can be attained, we construct, inductively, an example of nn ants colliding n(n1)/2n(n-1) / 2 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 1,2,,n1,2, \ldots, n from left to right. For n=1n=1 this is trivial. For n2n \geqslant 2, we use the construction for n1n-1 ants (now labelled 2,3,,n2,3, \ldots, n ). 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 (n1)(n2)/2(n-1)(n-2) / 2 collisions of the other n1n-1 ants. Now the following events happen (in this order) for i=1,2,,n2i=1,2, \ldots, n-2 : ants ii and i+1i+1 collide, after which ant ii moves to the left and ant i+1i+1 moves to the right. These collisions do happen because the speeds of the ants decrease from left to right. Then ants n1n-1 and nn also collide, resulting in ant n1n-1 moving to the left. This shows that there are (at least) (n1)(n2)/2+(n1)=n(n1)/2(n-1)(n-2) / 2+(n-1)=n(n-1) / 2 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 nn are moving towards the left after the collisions, this completes the inductive construction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.