We use induction on $n$. The base case is trivial. Call the largest bulldozer the BFB (Big Friendly Bulldozer). WLOG the BFB is a left bulldozer. Among the set $R$ of towns to the right of the BFB, by the induction hypothesis, there is a town $T\in R$ which cannot be swept away by any other town in $R$. But $T$ cannot be swept away by any right bulldozer of a town to the left of the BFB, so $T$ cannot be swept away by any of the $n$ towns.

Alternatively, one can also just tail induct... really trivial problem, but it gave everyone a good laugh. The base case $n=1$ is clear, so now assume we have $n+1$ towns $T_1$ to $T_{n+1}$. Suppose $T_k$ is the unique town which cannot be swept away by any of the other first $n$ towns. In particular, all right bulldozers of $T_1$ through $T_{k-1}$ cannot move past $T_k$ $(\star)$. Now, we consider two cases: If the left bulldozer of $T_{n+1}$ can sweep away all the right bulldozers between $T_k$ and $T_{n+1}$, i.e. $T_{n+1}$ can sweep away $T_k$, then it follows that $T_{n+1}$ is invincible by $(\star)$. In the other case, take the largest right bulldozer $R$ to the right of $T_k$, bigger than the left bulldozer of $T_n$. Now all towns to right of $T_k$ are not invincible, thus by $(\star)$ it follows that $R$ can sweep away everything up to $T_n$, and then $T_{n+1}$ by hypothesis.

Consider the first right bulldozer and the second left bulldozer. Since one of these is bigger either the first or second town will be swept away and its remaining bulldozer of the town swept away can be removed as it is unprotected. Thus we reduce the number of towns and the solution follows by induction. ($n=1$ is trivial) Does this work?

mssmath wrote: Consider the first right bulldozer and the second left bulldozer. Since one of these is bigger either the first or second town will be swept away and its remaining bulldozer of the town swept away can be removed as it is unprotected. Thus we reduce the number of towns and the solution follows by induction. ($n=1$ is trivial) Does this work? Yeah, that's what I got. Also notice how the solution is shorter than the problem.

An extension I have yet to solve: form the directed graph with vertices being the towns, labelle $1,2,\ldots,n$, where we have an edge from $A$ to $B$ if $A$ can sweep away $B$. How many graphs are there for each $n$? Unrelated: The situation in this problem is about as real-life applicable as it gets in math.

Note that in Australian Team Selection Test the problem is phrased in terms of elephants instead of bulldozers. Photo Cred: Me.

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. Otherwise it's easy to create a counterexample. Dots are towns: 1.7 8.2 3.5 If 3 moves first and pushes 8, then 7 is free to sweep the rest and the left town stays intact. If 8 moves first, then 3 sweeps the rest.

Some comments: 1. Nice solutions, but some of you forgot to prove the uniqueness part (i.e., that there exists at most one town that cannot be swept away). 2. Here is a straightforward generalization of the problem: Instead of placing the $n$ towns along a linear road, we allow them to be the vertices of an (undirected) tree (with the edges being roads). In other words, we work in the following setting: Let $T$ be an undirected tree with $n$ vertices. For each vertex $v$ and each edge $e$ incident with $v$, we place a bulldozer on $e$ pointing out of $v$. (Thus, there will be two bulldozers on each edge. In total, there are $2n-2$ bulldozers. This slightly deviates from the setting of the original problem, which has $2n$ bulldozers; however, the difference is irrelevant, since the left bulldozer of the leftmost town and the right bulldozer of the rightmost town never move and thus can be discarded.) We assume that the $2n-2$ bulldozers have pairwise distinct sizes. Bulldozers can move along the edges of $T$. When a bulldozer $a$ frontally collides with a bulldozer $b$, the larger of the two stays on the road, while the smaller one gets pushed out (and disappears). When a bulldozer $a$ rear-ends a bulldozer $b$, the bulldozer $a$ stays on the road, while the bulldozer $b$ gets pushed out (and disappears). We say that a town $A$ sweeps a town $B$ away if $A \neq B$, and the bulldozer pointing from $A$ in the direction of $B$ can drive all the way to $B$ without getting pushed out (assuming that all other bulldozers don't move of their own volition). ("All the way to $B$" means "all the way along the path from $A$ to $B$"; this path is unique since $T$ is a tree.) A town $B$ is said to be unswept if there exists no town $A$ that can sweep $B$ away. Again, we claim that there is exactly one unswept town. The simplest proof is probably the following: Let $c$ be the largest of all $2n-2$ bulldozers, and let $C$ be the town which this bulldozer $c$ is pointing out of. Let $S$ be the subgraph of $T$ formed by all towns $D$ such that the path from $C$ to $D$ does not contain the bulldozer $c$. Then, $S$ is a subtree of $T$, and the town $C$ sweeps every town in $T \setminus S$ away (using the bulldozer $c$). Thus, it is easy to see that the unswept towns of $T$ are precisely the unswept towns of $S$. Thus, we have reduced our problem to a smaller one (since the tree $S$ has fewer vertices than $T$). By induction, we can reduce this further and further, until no more bulldozer remains, at which point we have $n = 1$ and thus only one town left. This will be the unique unswept town. Notice how this argument looks like the construction of a real number using nested intervals! 3. MellowMelon, in post #8, asks how many "sweep graphs" there are for each $n$. Here are the numbers for small $n$: For n = 1 , there are 1 sweep matrices. For n = 2 , there are 2 sweep matrices. For n = 3 , there are 7 sweep matrices. For n = 4 , there are 34 sweep matrices. For n = 5 , there are 205 sweep matrices. (I have reencoded the "sweep graphs" as "sweep matrices"). Here is the Sage code that generated them: r""" This is about counting the number of "bulldozer digraphs" as introduced by MellowMellon in AoPS post http://artofproblemsolving.com/community/c6h1268873p6629378 . We encode these digraphs as matrices, which we call sweep matrices. Let `n` be a positive integer. A *bulldozer array* will mean a list of `2n-2` distinct numbers. We imagine `n` towns numbered `0, 1, \ldots, n-1` arranged along a (linear) road running from left to right. Each town has two bulldozers guarding it, as explained in IMO 2015 Shortlist problem C1 (see http://artofproblemsolving.com/community/c6h1268873p6622370 ), except that (unlike in the problem) town `0` has no left bulldozer and town `n-1` has no right bulldozer (since these two bulldozers would never be used anyway). The sizes of the `2n-2` bulldozers (from left to right) form a bulldozer array. The `0`-th entry of the array (we are counting from `0`) is the size of the right bulldozer of town `0`; the `1`-st entry is the size of the left bulldozer of town `1`; the `2`-nd entry is the size of the right bulldozer of town `1`; and so on. The *sweep matrix* of a bulldozer array is the `n \times n`-matrix defined as follows: Its `(i, j)`-th entry (where, again, we count rows and columns from `0`) is `1` if town `i` sweeps town `j`, and is `0` otherwise. (We say that no town sweeps itself.) """ def sweep_matrix(bs): r""" Return the sweep matrix of a given bulldozer array ``bs``. The matrix is returned as a tuple of rows (which, themselves, are encoded as tuples). EXAMPLES:: sage: sweep_matrix([4, 1, 3, 2, 5, 6]) ((0, 1, 1, 0), (0, 0, 1, 0), (0, 0, 0, 0), (1, 1, 1, 0)) """ n = len(bs) // 2 + 1 M = [[0 for _ in range(n)] for _ in range(n)] # I know ``xrange`` is faster, but Sage is moving to # Python3 soon, so let's speak the common tongue. for i in range(1, n): bs2i1 = bs[2*i-1] # size of left bulldozer of `i` for j in range(i): # Does i sweep j? (right-to-left) if all(bs2i1 > bs[2*k] for k in range(j, i)): M[i][j] = 1 bs2j = bs[2*j] # size of right bulldozer of `j` # Does j sweep i? (left-to-right) if all(bs2j > bs[2*k+1] for k in range(j, i)): M[j][i] = 1 return tuple(tuple(us) for us in M) def all_sweep_matrices(n): r""" Return a list of the sweep matrices of all possible bulldozer arrays for a given `n`. This list can have duplicates. """ from itertools import permutations return [sweep_matrix(bs) for bs in permutations(range(2*n-2))] def number_of_sweep_matrices(n): r""" Return the number of all sweep matrices for all possible bulldozer arrays for a given `n`. """ return len(uniq(all_sweep_matrices(n))) def sequence(): for n in range(1, 6): print "For n = ", n, ", there are ", number_of_sweep_matrices(n), " sweep matrices." The OEIS does not know such a sequence, so maybe there is no good formula. Better code could probably be written to get further values. 4. There are variants of this problem that might be worth studying: - What if the outcome of a frontal collision between two bulldozers $a$ and $b$ is determined not by a comparison of their sizes, but by the $\left(a,b\right)$-th entry of some matrix? What if this matrix is "antisymmetric", in the sense that if a moving bulldozer $a$ pushes a standing bulldozer $b$ off the road, then a standing bulldozer $a$ would also push a moving bulldozer $b$ off the road? What should we require of the matrix for the claim to remain true? - Can we characterize the possible "sweep matrices" somehow?

ABCDE wrote: 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. As everyone else, I will induct too. Just framing things a bit differently. Let the statement be true for $k \le n$. Let the towns be labelled $T_i$ from left to right and their left and right bulldozer $l_i,r_i$ respectively. Now we have to prove the statement for $n+1$ towns.. Consider the rightmost town $T_{n+1}$ and let some $r_j$ collide with $l_{n+1}$ Then there are two cases : $l_{n+1}$ derails all such $r_j$. Then obviously $T_{n+1}$ is the new winner town ! If some $r_j$ derails $l_{n+1}$. Then obviously since there is no other bulldozer between this point and $T_{n+1}$, $r_j$ sweeps $T_{n+1}$ Since there are no bulldozers between $T_j$ and $T_{n+1}$, The first $j$ towns live unaffected by the remaining towns. And hence by inducton we are done.

It's a shame there are no non-induction solutions. Especially since this problem just screams Extremal Principle. A very elegant and pretty solution found by some other people during the Bangladesh TSTs: At some point, only two bulldozers will remain on the road: a left bulldozer and a right bulldozer rolling on towards infinity. We prove that these belong to the same town. Consider that last left bulldozer $L$, and let it belong to town $T$. Now none of the right bulldozers from towns to the left of $T$ ever cross $L$ on the road, so they never reach $T$. Thus if a left bulldozer from the right of $T$ ever crossed it, it would have a clear path to kick $L$ in the rear end. This doesn't happen, so no left bulldozer ever crosses $T$. Now, the right bulldozer of $T$ can't be pushed off the road by another right bulldozer (such a bulldozer would have to cross $L$), and if it is pushed off by a left bulldozer that bulldozer would cross $T$. Thus the right bulldozer of $T$ is never pushed off i.e. it stays till the end. Thus no bulldozer ever crosses $T$ i.e. $T$ cannot be swept away by any other town. Also since the bulldozers of $T$ move on towards infinity all towns besides $T$ are swept, thus we have exactly one town that cannot be swept away. (QED) My own solution is a more natural application of the extremal principle. Turns out the town whose bulldozers together cross the largest number of towns will stand at the end, or else we'd contradict the maximality of towns crossed by owned bulldozers. It's pretty long-winded however, so I won't post it here. The argument is pretty standard, so if you should be able to discover it on your own. liberator wrote: We use induction on $n$. The base case is trivial. Call the largest bulldozer the BFB (Big Friendly Bulldozer). WLOG the BFB is a left bulldozer. Among the set $R$ of towns to the right of the BFB, by the induction hypothesis, there is a town $T\in R$ which cannot be swept away by any other town in $R$. But $T$ cannot be swept away by any right bulldozer of a town to the left of the BFB, so $T$ cannot be swept away by any of the $n$ towns. I'm probably missing something, but I think there's a flaw in the argument. What if another left bulldozer from $R$ sneaks up on the BFB and pushes it off from the rear end? Then it might fall down to a right bulldozer from the left of the BFB, allowing the right bulldozers to invade into $R$... The flaw is pretty easy to fix, but you do have to fix it or miss out on those sweet points

Here is an algorithmic proof. Perform the following algorithm 1) Remove the left bulldozer of the leftmost town and right bulldozer of the rightmost town.(They don't matter anyway) 2) Then choose the bulldozer of the largest size. Now if its the right bulldozer of some town then remove all the towns right of it, if its the left bulldozer of some town then remove all the towns left of it. Clearly this algorithm strictly decreases number of towns therefore at last only 1 town will remain. Its easy to show that this town cannot be swept by contradiction and clearly all other towns can be swept (why?)

liberator wrote: We use induction on $n$. The base case is trivial. Call the largest bulldozer the BFB (Big Friendly Bulldozer). WLOG the BFB is a left bulldozer. Among the set $R$ of towns to the right of the BFB, by the induction hypothesis, there is a town $T\in R$ which cannot be swept away by any other town in $R$. But $T$ cannot be swept away by any right bulldozer of a town to the left of the BFB, so $T$ cannot be swept away by any of the $n$ towns. What if T is the left bulldozer of the leftmost town then you can't apply inductive hypothesis. But you can fix it just by taking cases.

Basically ditto everybody else, but posting for storage. We prove the result by strong induction on $n$. The base case ($n = 1$) is trivial. Now, suppose the result holds for all $n = i \leq k$, for some $k$. We will show the result for $n = k + 1$. Number the towns $1, 2, \cdots, n = k + 1$ from left to right. Let $r$ be the size of the right bulldozer with the largest size among the towns $1, 2, \cdots, k$, and let $l$ be the size of the left bulldozer with the largest size among the towns $2, 3, \cdots, k + 1$. Let $A$ be $l$'s town. Assume $l > r$ (the case $l < r$ is identical). Since $l$ will push any right bulldozer to its left off the road, $A$ can sweep away all towns to its left. Also, none of the bulldozers to the left of the bulldozer $l$ can push it off the road, so $A$ cannot be swept away by any towns to its left. This implies that none of the towns to $A$'s left can sweep away any towns to $A$'s right. Now, by the inductive hypothesis on the towns between $A$ and $k + 1$ inclusive, at most one of these towns can be swept away by another of these towns. Let this town be $S$. Now, all of the towns to $A$'s left can be swept away by $A$, and none of these towns can sweep any town to $A$'s right away. This implies that $S$ is the only town that cannot be swept away by any other town. This completes the proof. $\Box$

Can someone see if my solution works? I think it is basically post #4's (mssmath) idea.

We perform induction on $n$. The base case $n = 1$ is trivial. Now suppose the claim holds for $k$ towns for all $1 \le k \le n$. We will show that it also holds for $n + 1$ towns, which will complete the induction. Let $a_i$ and $b_i$ denote the left and right bulldozers respectively of town $t_i$. WLOG let the towns be arranged $t_1, t_2, \dots , t_n$ in that order. We will show that, regardless of where we insert $t_{n + 1}$, the claim will still hold. Denote the left and right bulldozers of $t_{n + 1}$ by $x$ and $y$ respectively. Say that, in the original configuration of $n$ towns, town $t_k$ was the only remaining town. WLOG assume that $t_{n + 1}$ is placed to the right of $t_k$. All towns to the left of $t_k$ are still swept away. We have the following $2$ cases. In one case, $x < b_{k}$, which means that bulldozer $b_{k}$ sweeps away bulldozer $x$ and eventually sweeps away bulldozer $y$. Hence the only remaining town is $k$. The tricky case is when $x > b_{k}$. Suppose that town $t_{n + 1}$ is placed in between towns $t_{i}$ and $t_{i + 1}$. Then bulldozer $b_{k}$ sweeps away towns $k + 1$ to $i$. Once encountering bulldozer $x$, it will get swept away, so town $k$ gets swept away. Now all towns to the left of town $t_{n + 1}$ get swept away so by our induction hypothesis there exists a town in $\{t_{n + 1}, t_{i + 1}, \dots t_{n} \}$ which doesn't get swept away, and we are done. $\blacksquare$

Ok I had to open this thread to realise that this problem was a joke...

This was legit my biggest facepalm ever.

aops29 wrote: \(\overrightarrow{v_iv_j}\) is an edge if and only if \(\overrightarrow{v_{i+k}v_{i+k+1}}\) are edges too, for all \(1\leq k \leq j-i-1\). Why is that the case in the bulldozer problem? A town with a big bulldozer can plow through a lot of terrain that intermediate towns with smaller bulldozers might get bogged down in.

Here we go... Let's induct on $n$, the number of towns. For $n=1$, the single town is the unique victor. So assume that exactly one town will not be swept away for $n-1\geq 1$ towns. We show this must be true for $n (>1)$ towns as well. Number the towns $1,2,\dots, n$, starting from the leftmost town. Let $L_k,R_k$ be the sizes of the left and right bulldozers of town $k$ respectively, $1\leq k\leq n$. Now consider the smallest $i>1$ such that $L_i>R_{i-1}$. If this $i$ exists, then if $i=2$, town $2$ will sweep town $1$ away, and so we may remove town $1$ and apply the induction hypothesis on the remaining towns. If $i>2$, then we have $L_i>R_{i-1}$ and $L_{i-1}<R_{i-2}$. Thus both towns $i-2$ and $i$ will be able to sweep town $i-1$ away, and so we may remove town $i-1$ (since town $i-1$ cannot sweep away any other town) and apply the hypothesis on the remaining towns. If no such $i>1$ exists, then $R_1>L_2, R_2>L_3,\dots, R_{n-1}>L_n$. Then for $1\leq j\leq n-1$, town $j$ will be able to sweep away town $j+1$. But note that town $1$ will not be swept away by any other town $k>1$ since the left bulldozer of town $k$ will not be able to push the right bulldozer of town $k-1$ (since $L_k<R_{k-1}$). Thus town $1$ will be the only town that won't be swept away by any other town. Thus we are done. $\blacksquare$

We use induction, with base case n=1 trivial. Let's suppose it's true for n=k-1, we prove it for n=k. First, note that if the largest bulldozer is from town k or 1, either it goes towards the other towns, which sweeps everything and only town k is left, or it goes away, and since it's at the edge it has no meaning, so just pretend it did not exist. Now, take the largest bulldozer, WLOG it goes right, and let it be from town $i<k$. Since it sweeps everything to the right, we can just apply the inductive hypothesis to towns 1,2,...,i, and we're done. $\blacksquare$

First, note that the base cases $n=1$ and $n=2$ are trivial, so assume $n \geq 3$. Label the towns in order from $1$ to $n$, and let the $i$th town have a left bulldozer of size $x_i$, and a right bulldozer of size $y_i$. Claim: There is a town that cannot push any other town. Proof: Consider the set A of all $i$ such that $y_i < x_{i+1}$, and $n \in A$. Then consider the set $B$ of all $j$ such that $y_j > x_{j+1}$. Then obviously, we have that $A$ and $B$ are complements of the set $\{ 1, 2, \dots, n \}$. If $|B| = 0$, then the answer to our claim is town $1$. So, assume that $|A|, |B| > 1$. Then there must exist an $i$ such that $i \in B$, but $i+1 \in A$ (because we have that $n \in A$, and we can do a proof by contradiction). This is the $i$ that we want. $\square$ Now, we can use induction. Suppose the problem is true for $n$. Then to show it is true for $n+1$, consider the town that cannot push away any other town among the $n+1$ towns. We can just delete this town (it does not affect the answer) and we end up in the case for $n$ towns, thus completing the induction. $\blacksquare$

cute problem Consider the case with $k$ bulldozers. Out of the first right bulldozer and second left bulldozer, one of them will push the other one off the road, sweep the respective town, and also push the other bulldozer of the town it just swept off the road. This effectively removes one of the towns, reducing our case down to $k-1$ bulldozers. Since the case with $1$ towns has exactly one town which cannot be swept away, we are done. $\square$

We proceed by using induction. $n=1$, $2$ cases are clear. Assume for all $\le n$. We prove for $n+1$. We select the leftmost $n$ towers. This gives us a town, say $A$, that is not sweepable by any of the other $n-1$ towns. Call the rightmost town among the $n+1$ towns as $B$. Note that all the twons to the left of $A$ cannot reach beyond $A$. If $B$ sweeps $A$ then $B$ is our desired town. Otherwise, if $B$ cannot sweep $A$, then there is a town $P$ between $A$ and $B$ at which $B$'s bulldozer stops. But then $B$ can be swept by the bulldozer of $P$. So then $A$ is our desired town.

We proceed with induction on $n \ge 1$ towns. The $n = 1$ is obvious. Assume the claim is true for $n = k$ where $k$ is some nonnegative integer. For any configuration of bulldozers on $n = k + 1$ towns, let $T_i$ for integers $1 \le i \le k + 1$ be the $i$-th town from the left. It suffices to show that either $T_1$ or $T_{k + 1}$ can be swept away, allowing us to reduce to the $n = k$ case which induction finishes. Let $B$ be the largest bulldozer that is not the left bulldozer of $T_1$ or the right bulldozer of $T_{k + 1}$. Without loss of generality, assume it is a left bulldozer. Then $T_1$ can be swept away, as $B$ knocks off any left and right bulldozer on the way to $T_1$. Hence, the induction is finished. Our proof is complete.

We will induct, the case of $n = 1$ being trivial. Consider the largest bulldozer, $A$, that is not the $1^{\text{st}}$ or the $2n^{\text{th}}$ bulldozer. Without loss of generality assume $A$ is right-facing. Then clearly all towns to the right of $A$ can be swept away by $A$. Moreover, no bulldozer from towns to the right of $A$ may sweep a town to the left of $A$. Thus we may delete all towns to the right of $A$, as they do not affect the ``sweepability" of any of the towns to the left of $A$, and are ``sweepable" themselves. Thus inducting downwards, we finish.

literally just take the largest bulldozer and remove all the towns it can sweep away. keep inducting downwards, gg

Here is a slightly contrived solution. If a town has both its buldozers having the largest two labels, no other town can sweep it. Otherwise, consider the town $A$ that has one of its buldozers with the largest label and its other buldozer with some label that is less than the $2$nd largest. Without loss of generality, assume the largest buldozer is the left buldozer of town $A.$ For a town $B$ to the right of it to be able to sweep $A,$ then its left buldozer must be larger than the right buldozer of town $A.$ It follows $B$ sweeps all towns to the left of it. Now we can consider the right buldozer of $B$ and repeat the aforementioned process. Observe that this process must eventually terminate due to the finiteness of the towns and the uniqueness of the labels. The above process guarantees that all towns to the left of the new considered town to be swept away, and terminates when there is no town to the right of the town currently being considered that can sweep it away. Thus, this town cannot be swept away by any other one, and we are done.

Most of the people use induction. My solution is nice. Solution: there are finite number of towns. So we consider the rightmost town to be P. We consider a left to right moving bulldozer which crosses town P to be B. Let the town having initially B in its right, name it A. The solution is A will never be swept away.(Not very hard to prove)

Funny problem I guess. Induct by spliting the set of towns at the largest left bulldozer, since no right bulldozer can pass we succeeded in reducing number of towns.

We prove this by strong induction. The claim is obvious for $n = 1,2$. For the inductive step, consider the $2n - 2$ bulldozers that are facing at least one other bulldozer. Take the largest out of these bulldozers, without loss of generality let it face right, let the town it is at be $A$. Let the endpoint towns be $X,Y$, with $X$ on the left. If $X = A$, then the unique town that works is $X$, since we can clearly just knock out everything to the right and no one can knock out $X$ since its being protected by the biggest bulldozer. Otherwise, we the inductive hypothesis tells us exactly one town between $X,A$ cannot be knocked out by a town in $X,A$. We then see no towns outside of $X,A$ can be knocked out by another town (since the only other towns are in $A,Y$, and they are all getting blocked by the biggest bulldozer), so the unique town in $X,A$ that cannot be knocked out by a town in $X,A$ also cannot be knocked out by any other town, so this is our desired town. We have also shown all other towns can be knocked out, so we are done.

Most Brilliant Solution: Let $P$ be a point left of the leftmost town. The last bulldozer which crosses $P$ is let's say $A$. The most closest town on the left of $A$ is the town which wouldn't be destroyed. $\square$ (I don't know why is everyone using induction)

We show this by induction on $n.$ The base case, $n=1,$ is trivial. Now, suppose that our proposition holds for all $n \leq k$ for some positive integer $k.$ Then suppose we had $k+1$ towns $T_1, T_2, \cdots, T_{k+1}$ arranged from left to right. Then WLOG, let the bulldozer of size $2n$ be moving towards the right. If it was from a town $T_i$ with $1 \leq i \leq k,$ then clearly by our inductive hypothesis there is a unique town $P$ among the first $i$ towns that are not sweeped by any other town. Note that towns $T_j$ with $j > i$ will not sweep $P,$ and $P$ is unique, because the bulldozer of size $2n$ is largest and hence will sweep every single one of these towns, as well as stop any bulldozer from these towns to sweep $P.$ Now, suppose that the bulldozer of size $2n$ was from town $T_{k+1}.$ Then we can apply the same logic to the bulldozer of size $2n-1,$ and if that doesn't work, we use the next largest bulldozer, etc. Therefore, our induction is done. QED

I think this is a new solution. Other option is that it doesn't work. Sweeping produces a strict partial order on the towns, and any finite poset has a maximal element. Uniqueness follows by both bulldozers from such a town being unstoppable.

First, we claim that there can be no more than one town in a line which is unsweepable, i.e. it cannot be swept away by any other town. Suppose for the sake of contradiction that towns $A$ and $B$ sweep each other away. Then the right bulldozer of $A$ must be bigger than the left bulldozer of $B$, and the left bulldozer of $B$ must be bigger than the right bulldozer of $A$, which is absurd. Thus, it suffices to prove there is at least one town which is unsweepable. We proceed by induction, with the base case of 1 town being trivial. Assume that a line of $1,2,\dots,k$ towns has one town which is unsweepable (inductive hypothesis). Consider a line of $k+1$ towns $T_1,T_2,\dots,T_{k+1}$, and suppose the largest bulldozer $B$ belongs to town $T_n$. By symmetry, WLOG $B$ is a left bulldozer. If $B$ does not belong to $T_1$, then $T_n$ can sweep all of the towns to its left, and $T_n$ cannot be swept away by any town to its left. Therefore we can delete the towns to the left of $T_n$ without affecting whether any other towns are swept away or not, leaving a line of at most $k$ towns, which contains an unsweepable town by the inductive hypothesis. If $B$ belongs to $T_1$, consider the second largest bulldozer $C$ belonging to $T_m\neq T_1$. Similarly, if $C$ is a left bulldozer, then $T_m$ can sweep away every town to its left, and $T_m$ cannot be swept away by any town to its left, so we can delete the towns to the left of $T_m$ and apply the inductive hypothesis on the line of at most $k$ towns. If $C$ is a right bulldozer, if it does not belong to $T_{k+1}$, then $T_m$ can sweep away every town to its right without getting swept away by them, so we can delete these towns and apply the inductive hypothesis. Finally, if $C$ is a right bulldozer belonging to $T_{k+1}$, consider the third largest bulldozer $D$ belonging to $T_p\neq T_1,T_{k+1}$. Using similar reasoning as with $C$, $D$ can sweep away a nonzero number of towns to the left or right of $T_p$ while protecting it from getting swept away from the left/right. Hence we can delete these swept towns and apply the inductive hypothesis, showing that in all cases, the line of $k+1$ towns has an unsweepable town. This concludes the inductive step and the proof.