IMO Shortlist 2015 problem C1
In Lineland 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
bulldozers are distinct. Every time when a left and right bulldozer confront each other, the larger bulldozer pushes the smaller one off the road. On the other hand, 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 and
be two towns, with
to the right of
. We say that town
can sweep town
away if the right bulldozer of
can move over to
pushing off all bulldozers it meets. Similarly town
can sweep town
away if the left bulldozer of
can move over to
pushing off all bulldozers of all towns on its way.
Prove that there is exactly one town that cannot be swept away by any other one.
(Estonia)