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 n\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 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 T1, T2ΒΈ…, Tn be the towns enumerated from left to right. Observe first that, if town Ti can sweep away town Tj, then Ti also can sweep away every town located between Ti and Tj.

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 Ti and the right bulldozer in Tn 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 Tk with k < n.

Surely, with this large bulldozer Tk can sweep away all the towns to the right of it. Moreover, none of these towns can sweep Tk away; so they also cannot sweep away any town to the left of Tk. Thus, if we remove the towns Tk+1, Tk+2, … , Tn, 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, … , Tk 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

×

Like us on Facebook

%d bloggers like this: