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$.
Problem
Source: BxMO 2022, Problem 2
Tags: BxMO, combinatorics
tinsalopek
02.05.2022 11:44
solution?
tinsalopek
02.05.2022 14:04
.......................
Jalil_Huseynov
02.05.2022 16:54
Wrong solution....
Lepuslapis
02.05.2022 22:35
The previous answers are wrong. The correct answer is $\dfrac{n(n-1)}{2}$.
The order of the ants along the line does not change; denote by $v_1,v_2,\dots,v_n$ the respective speeds of ants $1,2,\dots,n$ in this order. If $v_{i-1}<v_i>v_{i+1}$ for some $i\in\{2,\dots,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,\dots,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. $\Box$
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,\dots,k$ and also to ants $n,n-1,\dots,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)<n(n-1)/2$.
Now take a coordinate $x$ along the line, and put ants at $x=1,2,\dots,n$ with positive initial velocities and speeds ${v_1=\cdots=v_{n-1}=1,v_n=\varepsilon}$, for some $\varepsilon$. For $\varepsilon=0$, collisions occur according to the pattern shown in the attachment for $n=5$, which clearly extends to all values of $n$ in such a way that ants $m$ and $m+1$ collide exactly $m$ times for $m=1,2,\dots,n-1$. This yield $1+2+\cdots+(n-1)=n(n-1)/2$ collisions in total. For all sufficiently small $\varepsilon>0$, the number of collisions remains equal to $n(n-1)/2$. $\Box$
Attachments:
