# Proving exactly one town which cannot be swept away by other one

Solution IMO 2015 (combinatoric shortlist problem)

**Problem 1:**

In Line land there are towns, arranged along a road running from left to right. Each town has a left bulldozer (put to the left of the town and facing left) and a right bulldozer (put to the right of the town and facing right). The sizes of the 2n bulldozers are distinct. Every time when a right and a left bulldozer confront each other, the larger bulldozer pushes the smaller one off the road. On the other hand, the bulldozers are quite unprotected at their rears; so, if a bulldozer reaches the rear end of another one, the first one pushes the second one off the road, regardless of their sizes.

Also Read:

Let A and B be two towns, with B being to the right of A. We say that town A can sweep town B away if the right bulldozer of A can move over to B pushing off all bulldozers it meets. Similarly, B can sweep A away if the left bulldozer of B can move to A pushing off all bulldozers of all towns on its way.

Prove that there is exactly one town which cannot be swept away by any other one.

(Shortlist problem combinatoric in IMO 2015)

**Solution. **

Let T_{1}, T_{2ΒΈ…, }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_{i} 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}, … , 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}, … , 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.

**Also Read : combinatoric shortlist Problem IMO 2015**