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 ------------------------------------------------------------- Future note: * I incorrectly interpreted the problem statement so that all buldozers can be moving simultaneously in their direction, possibly in various speeds which can also vary over time. Two directions: (UQ) uniqueness (EX) existence UQ could be easier. Let's assume that A < B, A cannot sweep B away and vice versa. WLOG A has a bigger right-buldozer than B has left-buldozer. But there can be towns in the middle with an even bigger buldozers... So it can probably happen that A and B cannot sweep each other but they can be both swept by a town in the middle. Let's assume that A cannot be swept out by any town on its right, denoted T1, T2, T3, ... so A_r (denoting right buldozer of A) A_r > T1_l T2 can certainly sweep it if T2_l > A_r and T2_l > T1_r * is it also necessary condition? * not really, there could be a very weak buldozer in the back that could destroy A_r * but that means that A was already swept away from the left, so we can in some sense assume that there is no buldozer in the back of A_r * there is a buldozer in the back of T1_r: A_r, * if A_r > T1_l, then A_r can destroy T1_r, and then A_r is the only buldozer in the way of T2_l. * so if we already assume A_r > T1_l, T2 can sweep A iff T2_l > A_r. To handle the the potential buldozer in the back of A, let us define "X can sweep Y first" meaning that the buldozer of X can be the first buldozer passing through Y. Note that a town can be swept away by another town iff it can be swept by another town first. It looks that we can prove the following proposition: Again the setup: town A somewhere, T1, T2, ..., are the towns on the right of it. None of T1, ..., Tn can sweep A first iff (A_r > T1_l and ... and A_r > Tn_l). Proof by induction (attempt): * Assume validity for n-1. * proving implication <- This does not even require induction. * The buldozer A_r cannot be destroyed from the back until another town from the left of A sweeps A first. * And since A_r is bigger that all the Ti_l, it will protect A from them. * proving implication -> Let's prove the contrapositive: * If A_r < Ti_l for some i=1, ..., n, then A can be swepr by one of the cities T1, ..., Tn first. * Actually, we show that it is the left-most city Ti satisfying the condition. * Since A_r > T_j for all j S1_r and ... and A_l > Sk_r and A_r > T1_l and ... and A_r > Tn_l. Nice, we have converted the dynamic condition to just some inequalities. Now it should not be difficult. Uniqueness: It cannot happen that A_r > B_l and vice versa, so they cannot be both towns which cannot be swept away. Existence... really? There have to be some counterexample. Let's have three towns in the order A, B, C, and try to make it a way that none of the towns is "protected" (shortcut for cannot be swept away) A is not protected, so A_r < B_l B is not protected, so B_r < C_l C is not protected, so C_l < A_r B_r < C_l < A_r < B_l 6A3 -- 4B1 -- 2C5 is it really the case that none of the towns is protected? C can sweep away A and B: A -->34<-- B -->12<-- C A ---4<--- B ---2<--- C A ---42<-- B(s) ----- C (s = swept away) A ---2<--- B(s) ----- C <2 A(s) ----- B(s) ----- C And similarly, A can sweep away C: A3 ------ 4B -->12<-- C A3 ------ 4B ---2<--- C A3 ----42< B(s) ----- C A3 ----2<- B(s) ----- C A -->32<-- B(s) ----- C A --->3--- B(s) ----- C A -------- B(s) -->3- C A -------- B(s) ----- C(s) >3 I guess I misinterpreted the problem statement :-( -------------------------------------------------------- I asked for clarification of the problem, this post on an AOPS forum helps: "Ah, the wording confused me. It's not saying that there is no sequence of bulldozer moves that will allow town A's bulldozer to get to town B. Instead, only one bulldozer is allowed to move at all." Oh, it is an entirely different problem :-) With this, uniqueness should be easy. A, B in this order, both are protected. WLOG A_r > B_l. but B is protected, so there is some C between A and B such that C_l > A_r but A is protected, so there is some D between A and C such that D_r > C_l but B is protected... this can go indefinitely, creating an infinite increasing sequence B_l < A_r < C_l < D_r < ... Hopefully, there is a more straightforward argument: * take the biggest buldozer between cities A and B (including A_r and B_l) * if this buldozer is facing left, A is not protected * if it is facing right, B is not protected * uniqueness proved Existence: Let's assume (for contradiction) that no town is protected. So the first A town is not protected, what does it means? -> There is a town B such that B_l is bigger than all right buldozers on the left of it. But also B is not protected. By assumption, B is protected from the left, so -> There is a town C on the right of B such that C_l is bigger than all right buldozers between B and C. Does it means that C is protected from the left? * Yes, no right buldozer before B can sweep C away (B_l is blocking it) and no right buldozer between B and C can sweep C away (C_l is blocking it) But C is not protected. -> There is a town D on the right of C such that D_l is bigger than all right buldozers between C and D. This again leads to an impossible infinite progress. Let's try to make it more formal. Let X be such a city that X_l can get to the left edge of Lineland, and X_l is as big as possible. (1) Then X_l is protected from the left? (hopefully from the reachability of the right edge) (2) Then X_l is protected from the right? (hopefully from the maximality) 2: Not really, the size of X_l is not the key factor, there can be Y on the left of X such that X_r < Y_l < X_l, and Y can sweep X away. So I wanted the maximality condition to be "and X is the right-most city satisfying this condition." Does 2 works then? Assume there is Y on the right of X such that Y can sweep X away. Does it imply that Y_l can get to the left edge of the lineland? * not really, Y_l can be relatively small (just bigger than X_r). * It is not the right condition yet. What do I want? The last city of my infinite progress A, B, C, ... They are all protected from the left, and I want the right-most one. Other experiment: Let X be the right-most city protected from the left. Does X have to be protected from the left? Assume the opposite: * There is Y on the right of X such that Y_l > X_r. * I want to prove that Y is protected from the left. * Y cannot be swept away by a buldozer on the left of X since X is protected from the left. * Y cannot be swept away by a buldozer between X and Y because... * Well I actually wanted to assume that Y can sweep X away. * So Y_l is bigger than all right-buldozers between X and Y. * Yeah, contradiction Problem solved! Just to make it clear: * Let X be the right-most city protected from the left. * If X is not protected from the right, there is a city Y on the right of X which can sweep X away. * Y cannot be swept away by a buldozer on the left of X since X is protected from the left. * Y cannot be swept away by a buldozer between X and Y since X can sweep Y away. * Therefore, Y cannot be swept away from the left. * This contradicts the assumption that X is the right-most city with the property. * Therefore, no such Y exists and X is protected from the right.