56th International Mathematical Olympiad Shortlisted Problems

Let $T_1,T_2,\dots ,T_n$ be the towns enumerated from left to right. Observe first that, if town $T_i$ can sweep away town $T_j$, then $T_i$ also can sweep away every town located between $T_i$ and $T_j$. We prove the problem statement by strong induction on $n$. The base case $n=1$ is trivial. For the induction step, we first observe that the left bulldozer in $T_1$ and the right bulldozer in $T_n$ are completely useless, so we may forget them forever. Among the other $2n-2$ bulldozers, we choose the largest one. Without loss of generality, it is the right bulldozer of some town $T_k$ with $k<n$. Surely, with this large bulldozer $T_k$ can sweep away all the towns to the right of it. Moreover, none of these towns can sweep $T_k$ away; so they also cannot sweep away any town to the left of $T_k$. Thus, if we remove the towns $T_{k+1},T_{k+2},\dots ,T_n$, none of the remaining towns would change its status of being (un)sweepable away by the others. Applying the induction hypothesis to the remaining towns, we find a unique town among $T_1,T_2,\dots ,T_k$ which cannot be swept away. By the above reasons, it is also the unique such town in the initial situation. Thus the induction step is established.

---

Alternative solution.

We start with the same enumeration and the same observation as in Solution 1. We also denote by ${\ell }_i$ and $r_i$ the sizes of the left and the right bulldozers belonging to $T_i$, respectively. One may easily see that no two towns $T_i$ and $T_j$ with $i<j$ can sweep each other away, for this would yield $r_i>{\ell }_j>r_i$. Clearly, there is no town which can sweep $T_n$ away from the right. Then we may choose the leftmost town $T_k$ which cannot be swept away from the right. One can observe now that no town $T_i$ with $i>k$ may sweep away some town $T_j$ with $j<k$, for otherwise $T_i$ would be able to sweep $T_k$ away as well. Now we prove two claims, showing together that $T_k$ is the unique town which cannot be swept away, and thus establishing the problem statement.

Claim 1. $T_k$ also cannot be swept away from the left. Proof. Let $T_m$ be some town to the left of $T_k$. By the choice of $T_k$, town $T_m$ can be swept away from the right by some town $T_p$ with $p>m$. As we have already observed, $p$ cannot be greater than $k$. On the other hand, $T_m$ cannot sweep $T_p$ away, so a fortiori it cannot sweep $T_k$ away.

Claim 2. Any town $T_m$ with $m\ne k$ can be swept away by some other town. Proof. If $m<k$, then $T_m$ can be swept away from the right due to the choice of $T_k$. In the remaining case we have $m>k$. Let $T_p$ be a town among $T_k,T_{k+1},\dots ,T_{m-1}$ having the largest right bulldozer. We claim that $T_p$ can sweep $T_m$ away. If this is not the case, then $r_p<{\ell }_q$ for some $q$ with $p<q⩽m$. But this means that ${\ell }_q$ is greater than all the numbers $r_i$ with $k⩽i⩽m-1$, so $T_q$ can sweep $T_k$ away. This contradicts the choice of $T_k$.

---

Alternative solution.

We separately prove that (i) there exists a town which cannot be swept away, and that (ii) there is at most one such town. We also make use of the two observations from the previous solutions. To prove $(i)$, assume contrariwise that every town can be swept away. Let $t_1$ be the leftmost town; next, for every $k=1,2,\dots$ we inductively choose $t_{k+1}$ to be some town which can sweep $t_k$ away. Now we claim that for every $k=1,2,\dots$, the town $t_{k+1}$ is to the right of $t_k$; this leads to the contradiction, since the number of towns is finite. Induction on $k$. The base case $k=1$ is clear due to the choice of $t_1$. Assume now that for all $j$ with $1⩽j<k$, the town $t_{j+1}$ is to the right of $t_j$. Suppose that $t_{k+1}$ is situated to the left of $t_k$; then it lies between $t_j$ and $t_{j+1}$ (possibly coinciding with $t_j$ ) for some $j<k$. Therefore, $t_{k+1}$ can be swept away by $t_{j+1}$, which shows that it cannot sweep $t_{j+1}$ away - so $t_{k+1}$ also cannot sweep $t_k$ away. This contradiction proves the induction step. To prove (ii), we also argue indirectly and choose two towns $A$ and $B$ neither of which can be swept away, with $A$ being to the left of $B$. Consider the largest bulldozer $b$ between them (taking into consideration the right bulldozer of $A$ and the left bulldozer of $B$ ). Without loss of generality, $b$ is a left bulldozer; then it is situated in some town to the right of $A$, and this town may sweep $A$ away since nothing prevents it from doing that. A contradiction.