Olympiad Maths Prep

Library / /3 of 11

Combinatorics Difficulty 8.6 Shortlist Prove it IMO

In Lineland there are n1n \geqslant 1 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 2n2n 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.
Let AA and BB be two towns, with BB being to the right of AA. We say that town AA can sweep town BB away if the right bulldozer of AA can move over to BB pushing off all bulldozers it meets. Similarly, BB can sweep AA away if the left bulldozer of BB can move to AA 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.

Solutions — 3

Solution 1

Let T1,T2,,TnT_{1}, T_{2}, \ldots, T_{n} be the towns enumerated from left to right. Observe first that, if town TiT_{i} can sweep away town TjT_{j}, then TiT_{i} also can sweep away every town located between TiT_{i} and TjT_{j}.
We prove the problem statement by strong induction on nn. The base case n=1n=1 is trivial.
For the induction step, we first observe that the left bulldozer in T1T_{1} and the right bulldozer in TnT_{n} are completely useless, so we may forget them forever. Among the other 2n22n-2 bulldozers, we choose the largest one. Without loss of generality, it is the right bulldozer of some town TkT_{k} with k<nk<n.
Surely, with this large bulldozer TkT_{k} can sweep away all the towns to the right of it. Moreover, none of these towns can sweep TkT_{k} away; so they also cannot sweep away any town to the left of TkT_{k}. Thus, if we remove the towns Tk+1,Tk+2,,TnT_{k+1}, T_{k+2}, \ldots, 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 T1,T2,,TkT_{1}, T_{2}, \ldots, 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.

Solution 2

We start with the same enumeration and the same observation as in Solution 1. We also denote by i\ell_{i} and rir_{i} the sizes of the left and the right bulldozers belonging to TiT_{i}, respectively. One may easily see that no two towns TiT_{i} and TjT_{j} with i<ji<j can sweep each other away, for this would yield ri>j>rir_{i}>\ell_{j}>r_{i}.
Clearly, there is no town which can sweep TnT_{n} away from the right. Then we may choose the leftmost town TkT_{k} which cannot be swept away from the right. One can observe now that no town TiT_{i} with i>ki>k may sweep away some town TjT_{j} with j<kj<k, for otherwise TiT_{i} would be able to sweep TkT_{k} away as well.
Now we prove two claims, showing together that TkT_{k} is the unique town which cannot be swept away, and thus establishing the problem statement.

Claim 1. TkT_{k} also cannot be swept away from the left.
Proof. Let TmT_{m} be some town to the left of TkT_{k}. By the choice of TkT_{k}, town TmT_{m} can be swept away from the right by some town TpT_{p} with p>mp>m. As we have already observed, pp cannot be greater than kk. On the other hand, TmT_{m} cannot sweep TpT_{p} away, so a fortiori it cannot sweep TkT_{k} away.

Claim 2. Any town TmT_{m} with mkm \neq k can be swept away by some other town.
Proof. If m<km<k, then TmT_{m} can be swept away from the right due to the choice of TkT_{k}. In the remaining case we have m>km>k.
Let TpT_{p} be a town among Tk,Tk+1,,Tm1T_{k}, T_{k+1}, \ldots, T_{m-1} having the largest right bulldozer. We claim that TpT_{p} can sweep TmT_{m} away. If this is not the case, then rp<qr_{p}<\ell_{q} for some qq with p<qmp<q \leqslant m. But this means that q\ell_{q} is greater than all the numbers rir_{i} with kim1k \leqslant i \leqslant m-1, so TqT_{q} can sweep TkT_{k} away. This contradicts the choice of TkT_{k}.

Solution 3

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)(i), assume contrariwise that every town can be swept away. Let t1t_{1} be the leftmost town; next, for every k=1,2,k=1,2, \ldots we inductively choose tk+1t_{k+1} to be some town which can sweep tkt_{k} away. Now we claim that for every k=1,2,k=1,2, \ldots, the town tk+1t_{k+1} is to the right of tkt_{k}; this leads to the contradiction, since the number of towns is finite.
Induction on kk. The base case k=1k=1 is clear due to the choice of t1t_{1}. Assume now that for all jj with 1j<k1 \leqslant j<k, the town tj+1t_{j+1} is to the right of tjt_{j}. Suppose that tk+1t_{k+1} is situated to the left of tkt_{k}; then it lies between tjt_{j} and tj+1t_{j+1} (possibly coinciding with tjt_{j} ) for some j<kj<k. Therefore, tk+1t_{k+1} can be swept away by tj+1t_{j+1}, which shows that it cannot sweep tj+1t_{j+1} away - so tk+1t_{k+1} also cannot sweep tkt_{k} away. This contradiction proves the induction step.
To prove (ii), we also argue indirectly and choose two towns AA and BB neither of which can be swept away, with AA being to the left of BB. Consider the largest bulldozer bb between them (taking into consideration the right bulldozer of AA and the left bulldozer of BB ). Without loss of generality, bb is a left bulldozer; then it is situated in some town to the right of AA, and this town may sweep AA away since nothing prevents it from doing that. A contradiction.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.