IMO 2015 Shortlist C1
In Lineland there are n ě 1 towns, arranged along a road running from left to right. Each town has a left bulldozer (put...
Category: Combinatorics
Problem
In Lineland there are n ě 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. 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. (Estonia)