Here's a short solution: We say a wall $v$ is above another wall $w$ if some point on $v$ is directly above a point on $w$. (This relation is anti-symmetric, as walls do not intersect). CLAIM (Iran TST 2010): There exists a lowest wall, i.e.\ a wall not above any other walls. Proof: Assume not. Then we get a directed cycle of some length $n \ge 3$: it's possible to construct a series of points $P_i$, $Q_i$, for $i = 1, \dots, n$ (indices modulo $n$), such that the point $Q_i$ is directly above $P_{i+1}$ for each $i$, the segment $\overline{Q_iP_{i+1}}$ does not intersect any wall in its interior, and finally each segment $\overline{P_iQ_i}$ is contained inside a wall. This gives us a broken line on $2n$ vertices which is not self-intersecting. Now consider the leftmost vertical segment $\overline{Q_iP_{i+1}}$ and the rightmost vertical segment $\overline{Q_jP_{j+1}}$. The broken line gives a path from $P_{i+1}$ to $Q_j$, as well as a path from $P_{j+1}$ to $Q_i$. These clearly must intersect, contradiction. $\square$. Thus if the bulldozer eventually moves upwards indefinitely, it may never hit the bottom side of the lowest wall. Similarly, if the bulldozer eventually moves downwards indefinitely, it may never hit the upper side of the highest wall.

Here was my solution during the test (sorry I can't explain it very well without diagrams):

Here's another way to see why there must be a lowest wall: Let $S$ be the set of endpoints of the walls. Let $T$ be the set of points $X$ in $S$ such that no point of any wall is directly below $X$. Project the points in $T$ onto the x-axis. Colour a point of projection blue if it originates from the left endpoint of a wall, and red if it originates from the right endpoint of a wall. Clearly the leftmost point on the x-axis is blue, and the rightmost point on the x-axis is red, so there are two consecutive points which are blue and red in that order from left to right. Let these points have x-coordinates $a, b$ where $a < b$. If there is a point in $S$ with x-coordinate between $a$ and $b$, is a point in $T$ with x-coordinate between $a$ and $b$, a contradiction. So the consecutive blue and red points come from the same wall, so this wall is a lowest wall.

What is "moves in the $+x$ direction" meaning, and the definition of "above wall" is not clear for me, for example, in the figure, $A$ is above $C$ so $v$ above $u$ but $C$ is above $B$ so $u$ is above $v$, Am I misunderstanding something?

Vietnamisalwaysinmyheart wrote: What is "moves in the $+x$ direction" meaning It moves due east on the Cartesian plane. Quote: and the definition of "above wall" is not clear for me, for example, in the figure, $A$ is above $C$ so $v$ above $u$ but $C$ is above $B$ so $u$ is above $v$, Am I misunderstanding something? Yes. It means "directly above", meaning that there is a point $P$ on the first wall and $Q$ on the second wall such that $PQ$ is vertical, and $P$ is above $Q$.

A simple solution: Assume the contrary, that is, both sides of every wall is hit. Wall A is "below" wall B if there exists some value of x such that the y-coordinate of the corresponding point on A is smaller than that of B. Wall A is "above" wall B if there exists some value of x such that the y-coordinate of the corresponding point on A is greater than that of B. Since there are finitely many walls, there is some wall that has no walls below it (indeed, if there was, then we could find another wall below it and repeat the argument without repeating the same wall). Consider the under side of the wall. At some time, the bulldozer must hit that side of the wall. The bulldozer could not have come from moving in the positive y direction as there are no walls below it. Thus, it must have come from the right/left, in which case it bounces off that wall and never hits another wall. Similarly, we can repeat this argument for the wall with no walls above it. Thus, the bulldozer "never hits another wall" twice, but this is absurd, so we have reached a contradiction. Edit: Whoops, didn't see v_Enhance's solution above

What Happens when bulldozer hits the endpoint of the segment?

Quote: What Happens when bulldozer hits the endpoint of the segment? Actually, it's well known that a segment, as an open interval, does not contain endpoints.

@K_Mirrorheart Thanks! I thought "segment" is same as "closed interval"

Can someobody please check if this solution works? v_Enhance wrote: In the coordinate plane are finitely many walls; which are disjoint line segments, none of which are parallel to either axis. A bulldozer starts at an arbitrary point and moves in the $+x$ direction. Every time it hits a wall, it turns at a right angle to its path, away from the wall, and continues moving. (Thus the bulldozer always moves parallel to the axes.) Prove that it is impossible for the bulldozer to hit both sides of every wall. Proposed by Linus Hamilton and David Stoner Assume on the contrary. Consider all the walls and their right endpoints. Choose the wall $w$ whose rightmost point is the most right; i.e. the wall such that if the $x$-coordinate of this rightmost endpoint is $c,$ then all the walls lie completely on the left of the line $x=c.$ Such a point exists since there are only finitely many walls each of which has a finite length. Assume wlog that $w$ is tilted towards the right, as shown. Now consider the path of the bulldozer. Consider all the points at which the path intersects $w$ on the lower side. Choose the point closest to the line $x=c$ and connect the path at that point. Then the figure must look something like this (the direction of the path could be towards the right or left, doesn't matter.) [asy][asy] unitsize(0.75cm); int x=3; int y=1; int t=2; draw((0,0)--(x,x), blue); draw((x,0-y)--(x,y+x)); draw((x/2, x/2-t)--(x/2,x/2)); draw((x/2,x/2)--(x+0.5,x/2)); dot((x/2,x/2)); [/asy][/asy] At this point, notice that if this path does not leave the line $x=c,$ then we must have an obstruction by another wall. However, both of these cases (type of wall) lead the path to intersect $w$ at a point that is closer to $x=c$ than the point we choose, contradicting our assumption. (For the second figure, we use the fact that both sides of the wall are intersected by the path.) [asy][asy] unitsize(0.75cm); draw((-2,-2)--(1,1), blue); draw((1,-3)--(1,2)); draw((-0.5, -1.5)--(0.5,-0.5), red); draw((-0.8,-3)--(-0.8,-0.8)); dot((-0.8,-0.8)); draw((-0.8,-0.8)--(0.2,-0.8)); draw((0.2,-0.8)--(0.2,0.2)); dot((0.2,0.2)); int x=6; draw((-2+x,-2)--(1+x,1), blue); draw((1+x,-3)--(1+x,2)); draw((-0.3+x,-0.5)--(0.5+x, -1.5), red); draw((-0.8+x,-3)--(-0.8+x,-0.8)); dot((-0.8+x,-0.8)); draw((-0.8+x,-0.8)--(-0.1+x,-0.8)); draw((-0.1+x,-0.8)--(-0.1+x,-1.4)); draw((0.2+x,-1.05)--(0.2+x,0.2)); draw((0.2+x,-1.05)--(0.8+x,-1.05)); dot((0.2+x,0.2)); [/asy][/asy] Note: If after hitting the obstruction wall, if the path faces another obstruction while moving towards $w,$ we can see that the new obstruction behaves in a similar way as the current obstruction and nothing changes. Keep doing this and since the number of walls is finite, hence one wall would eventually have no obstruction above it. Then this diagram works for that case. Hence the path must leave the line $x=c.$ Notice that in the right of this line, the path has to be a straight line since there is no wall there. So fix any point on the path here. This would be one endpoint of the path. We can do the same argument for the leftmost wall and so we would find two endpoints that determine this path; one on the left of the leftmost line and the second on the right of the rightmost line (the one mentioned above). We can also perform a similar argument for the topmost and bottommost line and determine two distinct endpoints for the same path of the bulldozer. This is a contradiction since the path is nothing but a broken straight line. $\blacksquare$

My solution: First of all we denote the midpoint of the wall as the wall. Claim:There is a wall that is to the left of every wall. Proof:Assume to the contrary.Consider a line parallel to Y axis and stat moving this line towards $-X$ direction.This line will stop moving once it passes through all points towards the left of its initial position.(There are finitely such points).But according to our assumption the line must move on forever.Contradiction. Now consider this leftmost point. Case (1) this wall makes an acute angle with the positive direction.Then to reach the opposite side of the wall it must approach the wall from above or from the left.But since it is the leftmost point,the other side needs to be approached only from above.But for this there should be a point directly above this point Repeat the same argument with this new point.There's no point to the left of this new point so we can repeat the argument and we get that there are infinite points above the original point which is a contradiction. Case (2).Similar approach can be taken for the obtuse case.Here we get that there are infinite walls below Done!

Suppose there exists a configuration of walls for which the bulldozer hits both sides of each. Define the ``down-area'' and ``right-area'' of a wall $W$ (the wall is red) to be all points directly down and right to the wall:

Consider a point $P$ in the down-area of the red that is a point of the blue line. Then the blue line is a line passing through $P$, and can rotate to at most the position shown above (or the left side, in which case the argument is isomorphic). The down-area of the blue line cannot intersect the up-area of the red line's up-area, even past the right vertex of the red line, as shown. $\blacksquare$ Iteratively apply Claim 1 to create a chain of walls, one each below than the next. Since there are only finitely many walls, this chain must be a cycle. We claim there cannot be such a cycle of walls. Suppose $W_1\to W_2\to \cdots \to W_n\to W_1$ is a cycle of walls, each below the next. By Claim 2, the down-area of $W_2$ does not intersect the up-area of $W_1$. Also, the down-area of $W_3$ does not intersect the up-area of $W_2$, and hence also bounded not intersecting the up-area of $W_1$, since then $W_3$ would intersect $W_2$. Continuing with this logic, the down-area of $W$ does not intersect the up-area of $W_1$ for any $W$ in the chain. This contradicts that the chain cycles back to $W_1$.

Notice that every wall has a top side and a bottom side. To say, if a bulldozer was moving horizontally, hits the side of a line segment, and starts moving in the $+y$ direction, then the side it hit was a top side. A similar definition is given to the bottom side. Now, consider the maximal top side. We can rigorously define the maximal top side as follows. For any segment $a$ and $b$ in our set, we say $a<b$ if the top side of $a$ faces the bottom side of $b$. It is immediate that $a<b$ and $b<c$ implies $c<a$ so there are both maximal and minimal elements. Notice that it cannot be the case that the bulldozer hits the bottom side of the minimal wall while moving in the $+y$ direction, this is true by minimality. Clearly, the bottom side of the minimal wall can not be hit while the bulldozer is moving in the $-y$ direction. Thus, a bulldozer can only hit the bottom face of the minimal wall if moving in the $\pm x$ direction. So, once the bulldozer hits the bottom side of the minimal wall, it will move in the $-y$ direction. By minimality, there are no walls in the $-y$ direction from the bottom side of the minimal wall. So, the bottom side of the minimal wall is the last side of the wall that will ever be hit. But, by a similar line of logic, the top side of the maximal wall will be the last side that will be hit. Thus, a bulldozer cannot hit both the bottom side of the minimal wall and the top side of the maximal wall.

Solved with squareman. Suppose the bulldozer can hit both sides of each wall. Let the $n$ walls be $\ell_1, \ell_2, \ldots , \ell_n$. For every wall $\ell_i$, there is another wall $\ell_j$ whose lowest point is below the topmost point on $\ell_i$ because otherwise, the bulldozer either only ever hits the bottom surface of $\ell_i$ out of any surface from any wall (only if it comes from the bottom) or never hits it at all (because it cannot come from the side). Say for wall $\ell_i$, the wall $\ell_{f(i)}$ has a point below the topmost point of $\ell_i$. Since there are a finite number of walls, it follows that in the infinite sequence $i, f(i), f^2(i), \ldots $ there are $m, n$ for which $f^m(i) = f^n(i)$, so there is a cycle\[\ell_{a_1} \to \ell_{a_2} \to \ldots \to \ell_{a_T} \to \ell_{a_1}\]of walls for some $T \leq n$ such that each wall has a point lower than the topmost point of the one preceding it. Construct a path as follows (possible by our previous finding of a cycle of walls beneath each other): Draw a vertical segment $A_1B_1$ with $A_1$ on $\ell_{a_1}$ and $B_1$ on $\ell_{a_2}$, then vertical $A_2B_2$ with $A_2$ on $\ell_{a_2}$ and $B_2$ on $\ell_{a_3}$, and so on, until vertical $A_TB_T$ with $A_T$ on $\ell_{a_T}$ and $B_T$ on $\ell_{a_1}$. Note that $A_1B_1\ldots A_TB_T$ is a nonintersecting cycle, but this is impossible since this is also a broken line polygon that returns to its starting point by this. Therefore we have a contradiction, as desired.

Wizard_32 wrote: Can someobody please check if this solution works? v_Enhance wrote: In the coordinate plane are finitely many walls; which are disjoint line segments, none of which are parallel to either axis. A bulldozer starts at an arbitrary point and moves in the $+x$ direction. Every time it hits a wall, it turns at a right angle to its path, away from the wall, and continues moving. (Thus the bulldozer always moves parallel to the axes.) Prove that it is impossible for the bulldozer to hit both sides of every wall. Proposed by Linus Hamilton and David Stoner Assume on the contrary. Consider all the walls and their right endpoints. Choose the wall $w$ whose rightmost point is the most right; i.e. the wall such that if the $x$-coordinate of this rightmost endpoint is $c,$ then all the walls lie completely on the left of the line $x=c.$ Such a point exists since there are only finitely many walls each of which has a finite length. Assume wlog that $w$ is tilted towards the right, as shown. Now consider the path of the bulldozer. Consider all the points at which the path intersects $w$ on the lower side. Choose the point closest to the line $x=c$ and connect the path at that point. Then the figure must look something like this (the direction of the path could be towards the right or left, doesn't matter.) [asy][asy] unitsize(0.75cm); int x=3; int y=1; int t=2; draw((0,0)--(x,x), blue); draw((x,0-y)--(x,y+x)); draw((x/2, x/2-t)--(x/2,x/2)); draw((x/2,x/2)--(x+0.5,x/2)); dot((x/2,x/2)); [/asy][/asy] At this point, notice that if this path does not leave the line $x=c,$ then we must have an obstruction by another wall. However, both of these cases (type of wall) lead the path to intersect $w$ at a point that is closer to $x=c$ than the point we choose, contradicting our assumption. (For the second figure, we use the fact that both sides of the wall are intersected by the path.) [asy][asy] unitsize(0.75cm); draw((-2,-2)--(1,1), blue); draw((1,-3)--(1,2)); draw((-0.5, -1.5)--(0.5,-0.5), red); draw((-0.8,-3)--(-0.8,-0.8)); dot((-0.8,-0.8)); draw((-0.8,-0.8)--(0.2,-0.8)); draw((0.2,-0.8)--(0.2,0.2)); dot((0.2,0.2)); int x=6; draw((-2+x,-2)--(1+x,1), blue); draw((1+x,-3)--(1+x,2)); draw((-0.3+x,-0.5)--(0.5+x, -1.5), red); draw((-0.8+x,-3)--(-0.8+x,-0.8)); dot((-0.8+x,-0.8)); draw((-0.8+x,-0.8)--(-0.1+x,-0.8)); draw((-0.1+x,-0.8)--(-0.1+x,-1.4)); draw((0.2+x,-1.05)--(0.2+x,0.2)); draw((0.2+x,-1.05)--(0.8+x,-1.05)); dot((0.2+x,0.2)); [/asy][/asy] Note: If after hitting the obstruction wall, if the path faces another obstruction while moving towards $w,$ we can see that the new obstruction behaves in a similar way as the current obstruction and nothing changes. Keep doing this and since the number of walls is finite, hence one wall would eventually have no obstruction above it. Then this diagram works for that case. Hence the path must leave the line $x=c.$ Notice that in the right of this line, the path has to be a straight line since there is no wall there. So fix any point on the path here. This would be one endpoint of the path. We can do the same argument for the leftmost wall and so we would find two endpoints that determine this path; one on the left of the leftmost line and the second on the right of the rightmost line (the one mentioned above). We can also perform a similar argument for the topmost and bottommost line and determine two distinct endpoints for the same path of the bulldozer. This is a contradiction since the path is nothing but a broken straight line. $\blacksquare$ I have a doubt in the red part of the solution. It might happen that the path intersect the lower side of $w$ infinitely many times, so such a "closest" point might not exist. So how to handle such cases ?

Suppose we have a laser very far in the $+y$ direction pointing in the direction of $-y$ that records the distance to the closest wall in the beam of the laser—call this value $f(x)$ when the laser has $x$-coordinate $x$, where we abuse notation and let $f(x)=-\infty$ if there is no wall (in practice, we can replate $\infty$ with a suffiicently large number). Because of the disjoint condition, the graph of $y=f(x)$ should have a number of jump discontinuities at certain points. It is easy to see that, going from $-\infty$ to $+\infty$ if we have an "upwards" jump discontinuity followed immediately by a "downwards" jump discontinuity, then between those two discontinuities the laser passes over a complete wall. Moreover, the first discontinuity is an upwards one (going from $-\infty$) and the last discontinuity is downwards (going to $-\infty$), at some point we in fact must have an upwards discontinuity followed by a downwards one (otherwise every discontinuity is upwards which is impossible). Thus there exists some wall whose $+y$-facing side is "$+y$-exposed", meaning that there is no point which is directly above ($+y$) this wall. Likewise, there is a wall whose $-y$-facing side is "$-y$-exposed". Because the bulldozer starts moving in the $+x$ direction, if the $+y$-exposed side is hit, then the bulldozer continues indefinitely in the $+y$ direction and doesn't hit anything else. But if the $-y$-exposed side is hit, then the bulldozer also continues indefinitely in the $-y$ direction. Both of these statements cannot be simultaneously true, hence one of these two walls is not hit by the bulldozer. Thus the bulldozer cannot hit both sides of every wall, as desired. $\blacksquare$

Sketch: Observe that there exists a cycle of walls $\{w_i\}$ such that for every $w_i$ and $w_{i+1}$, there exists a horizontal line $h_i$ that intersects both of them, with the $h_i \cap w_{i+1}$ to the right of $h_i \cap w_i$ (WLOG), and $h_i$ intersecting with no other wall between $w_{i+1}$ and $w_i$ (take $w_{i+1}$ to be the nearest wall that "shares" y-coordinates with $w_i$). Essentially, $$h_1 \cap w_1 \rightarrow h_1 \cap w_2 \rightarrow h_2 \cap w_2 \rightarrow h_2 \cap w_3 \cdots$$traces out a non-intersecting polygon where every other side points in the $+x$ direction; this essentially reduces the problem to Iran TST 2010/7 (from DCW-Local), which can be solved by taking two extremal parallel sides.

Note that each side of a wall being hit corresponds to $2$ specific axis directions. Fix one of the $4$ axis directions. For two walls, say that one is above another if going along the axis direction from some point on the first wall hits the other wall. Claim: There is at least $1$ wall with no other wall above it. Proof. This is equivalent to showing that there does not exist a cycle of walls such that consecutive walls are above each other. Suppose such a cycle of walls $a_1, a_2, \dots, a_n$ exists such that $a_{i+1}$ is above $a_i$ cyclically. Shift each $a_{i+1}$ down minimally until it touches $a_i$ noncyclically. By discarding the portions of the wall that don't lie between the intersection points of the now shifted walls, we end up with a path. However, then by going along the path, this eventually allows us to get to a point on $a_n$ that is below $a_1$. By considering the axis perpendicular to the fixed axis, this that for some two adjacent walls $a_i$ and $a_{i+1}$, going along them has opposite effects on the coordinate along the perpendicular axis. However, this implies that $a_i$ is above $a_{i+1}$, contradiction. $\blacksquare$ Then, for each axis direction there is a wall with no other wall above it in that direction. For the sake of contradiction assume that the bulldozer hits every side. Then, at each maximal wall, the bulldozer must hit it and then go off into infinity at one of its side. However, there are four axis directions and the bulldozer can only go off into infinity in two, contradiction.

Define an order $\succ$ on the walls $w_i$ as follows: let $w_i \succ w_j$ if there exists a point on $w_i$ strictly below a point on $w_j$. Clearly $\succ$ is anti-symmetric. Claim. There exists a wall $w$ such that $w \succ w_i$ for any $w_i$ for which the order is defined. Proof. Suppose not; then, there exists a cycle $w_1 \succ w_2 \succ \cdots \succ w_n \succ w_1$. It follows that there exists distinct points $A_i \in w_i$ and $B_i \in w_{i+1}$ such that $\overline{A_iB_i}$ points downwards for every $i$. This yields a contradiction by 2010 Iran TST/7. $\blacksquare$ So there exists a ``lowest wall" $w$. Similarly there exists a ``highest wall" $u$. Assume that the statement is true; then, the bulldozer hits the underside of $w$ and the overside of $u$ at some point that is not the beginning. (This is where the $+x$ direction becomes important!) But after each of these interactions, the bulldozer can not hit any more walls, which is an obvious contradiction.

We say a wall v is above another wall w if some point on v is directly above a point on w. (This relation is anti-symmetric, as walls do not intersect). The critical claim is as follows: Claim — There exists a lowest wall, i.e. a wall not above any other walls. Proof. Assume not. Then we get a directed cycle of some length $n$ ≥ 3: it’s possible to construct a series of points $P_i$,$Q_i$, for $i = 1, . . . , n$ (indices modulo $n$), such that the point $Q_i$ is directly above $P_i+1$ for each i, the segment $Q_iP_i+1$ does not intersect anywall in its interior, and finally each segment $P_i Q_i$ is contained inside a wall. This gives us a broken line on $2n$ vertices which is not self-intersecting. Now consider the leftmost vertical segment $Q_iP_i+1$ and the rightmost vertical segment $Q_jP_j+1$. The broken line gives a path from $P_i+1$ to $Q_j$ , as well as a path from $P_j+1$ to $Q_i$ . These clearly must intersect, contradiction. Remark. This claim is Iran TST 2010. Thus if the bulldozer eventually moves upwards indefinitely, it may never hit the bottom side of the lowest wall. Similarly, if the bulldozer eventually moves downwards indefinitely, it may never hit the upper side of the highest wall.

The idea is to show that there exists a lowest wall (a wall with all points not above any other directly vertical points), which can be proved by assuming not, looking at points that form a cycle $P_1Q_1P_2Q_2...P_nQ_n$ where $P_iQ_i$ is part of a wall and $Q_iP_{i+1}$ is a vertical segment that doesn't intersect any other walls. Then taking the leftmost vert segment and rightmost, the path going bottom of leftmost to top of rightmost must intersect top of leftmost to bottom of rightmost, contradiction. Now if the bulldozer is eventually infinitely upward it can't hit the bottom of lowest wall, for otherwise that would have to be the first wall it hits, but that means it goes infinitely downward from there, contradiction. Similarly it can't hit top of topmost wall if infinitely downward, done. um yaoaops and awesomeming and all those people can u pls stop making me feel bad about not solving harder problems i see u post so manyyy

Solved with alsk: Draw a rectangular fence containing every segment in its interior (which the bulldozer can plow through). Call a segment "exposed" to a fence if, for every point on the segment, the foot from the segment to that fence doesn't pass through any other segments. Claim: for each of the four fences, there is a segment exposed to it. Proof: Consider just the top fence. Give each segment a unique color and project a shadow of that color from the segment to the top fence. Then, consider the sequence of colors (from left to right) that is present on the top fence. Firstly, note that any sequence cannot contain $a, \dots, b, \dots, a, \dots, b$ where $a$ and $b$ are two distinct colors. The first section of $b$ in between the two $a$'s inplies that segment $b$ is above segment $a$. But then, at the second region of $a$, segment $b$ must be underneath segment $a$, contradiction. Now consider a pair of same-color regions which has a minimal number of regions in between them. (Or, if no color appears twice, take the whole sequence.) Then, all $n$ regions in this range occur once. Now, in this range of distinct colors, draw an arrow at the line between any two consecutive regions $X$ and $Y$. If $X$ covers $Y$, draw an arrow from $X$ to $Y$, or vice versa. (Or, if neither covers the other, draw no arrow.) There are $n-1$ arrows and $n$ regions, so some region is not pointed to, which is our exposed region/segment. $\qquad \square$ Claim: no segment can be exposed to two adjacent fence. Proof: It is impossible for the bulldozer to bounce on the side of the segment exposed to both fences. $\qquad \square$ The bulldozer can crash through the fence at most twice (at most one entry, at most one exit), but bouncing on the outside of the four exposed segments means it has to crash through the fences at least four times, contradiction. (can't the bulldozer turn any number of degrees, not just 90?)

hi solved with Upwgs_2008