« Vrati se

In Lineland there are n\geq1 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 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 A and B be two towns, with B 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 town B can sweep town A away if the left bulldozer of B can move over to A 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)

Slični zadaci