Vrftsjtryk

You are driving a car in a city with $N$ long, straight streets. No two streets are parallel so there is an intersection (crossroads) for each pair of streets. Each intersection has only two intersecting streets. No street has strict north-south direction.

There is only one driving rule: when you reach the intersection you have to make a turn so that the next street takes you eastwards (north-east, east, south-east, does not matter). On a map, it means that you have to keep driving to the right side of the map.

Prove that it is always possible to make a drive through the city that visits all the streets at least once.

Here is a city with $N$=6 streets. Some fairly complicated routes do not visit all the streets (blue route does not visit street $a$. But the red route will take you through all streets.

I tried to solve the problem in the following way: Each street consists of segments created by intersecting streets. I have assigned a collor to each street. Obviously, each street has 6 segments and I have represented each segment with a colored dot:

Look at the "long" routes, i.e. routes starting from some west-most street segment. Each such route represents a sequence of segments (colored dots). There are 6 such routes, one for each street in the city:

...or, with the streets removed:

I was able to conclude several things from the final graph:

• There are $N$ different colors (with exactly $N$ vertices having one color), $N$ polygonal chains, $N^2$ colored vertices.


• The chains do not intersect (this can be proved fairly easily)


• In a single chain, there are at least two vertices between any two vertices of the same color.


• This basically means that in any chain you will find 3 different colors for any four consecutive vertices.

Based on that I still could not prove that one chain must have vertices with all possible colors. Which probably means that my approach is 100% wrong. But the problem is still interesting.

Misha's Answer is essentially correct, but I felt the need to elaborate a bit and fill in some details.

With $n$ lines there are $n$ routes: one for each road, starting at the west-most point of that road and heading east.

Now, if you draw a vertical line to the west of all the intersections, then the order in which that line intersects with the streets (and of course it will intersect with all streets) will order the routes from 'north' to 'south'. In fact, these intersection points can be seen as the 'starting point' for each route. Notice that if we do the same to the east oa ll street intersections, we would get what could be considered the 'end points' of the routes, and they would be in the exact reverse order, going from north to south.

Now, notice the following claims are all true:

I. Each street segment is traversed by exactly one route: if you start on that street segment, then there is only one way to continue that route east, and there is only one way to continue going west, and this is of course one of the routes

II. Every intersection will get visited by exactly two of the routes: from any intersection there are two street segments going east, and since by I. each street segment belongs to exactly one route, that means exactly two routes go through an intersection.

III. Two routes will never cross each other: if they would, that would mean that both routes would have to go straight at some intersection, which is against the rules.

IV. There will never be an intersection between two consecutive routes (i.e. south of one route, and north of the other): if there was, then consider any of the routes going through that intersection: this route would have to cross one of them going back to the starting point, which again by III is impossible

V. There cannot be two consecutive routes and two different streets $A$ and $B$ where one route is completely north of $A$, and the other completely south of $B$: (this is the central argument in Misha's Answer) if this were to occur, then the intersection of $A$ and $B$ would be completely between the two consecutive routes, which by IV is impossible.

OK, so finally (again, as in Misha's answer), consider the successive routes starting with the northern-most one. Clearly the northern-most one cannot be completely to the south of some street, so if there is something wrong with it, then it must be because it is completely north of some street. Now, as long as the route under consideration is completely to the north of some street $A$, consider its successive route. This street $A$ will at some point be included by some route as we go down the list of routes, (since every street is traversed by some route). Moreover, if the current route is still completely north of street some $A$, it is impossible for its successor route to go completely south of some different street $B$, for that would go against V, and so by the time we reach a route that includes street $A$, we have not gone completely to the south of some street $B$. This process we can continue for any other street that we are still completely to the north of, and again, it is impossible to ever end up to the south of some other street. Hence, at some point all streets must be included in some route.

We consider only the routes that start very far to the left (further than any intersection point) and end very far to the right (further than any intersection point). Routes that don't work because they didn't go far enough in one direction or the other are not interesting.

Each route that fails, fails for one of two reasons:

1. It always stays strictly below a certain street, never touching it.


2. It always stays strictly above a certain street, never touching it.

These two reasons can't both be true for the same route. Any two streets intersect, so the region that's strictly above street $X$ but strictly below street $Y$ doesn't go all the way from left to right: it can't contain an entire route.

So we can can classify the bad routes into "too-low" routes that fail because they always stay below some streets, and "too-high" routes that fail because they always stay above some streets.

You've already observed that there are $N$ routes, which can be ordered vertically, and never cross (though they can touch): if route $r$ starts above route $s$, then it will always stay above route $s$. In particular, if a route is "too-low", then so is every route below it; if a route is "too-high", then so is every route above it.

Suppose that route $r$ is above route $s$, and route $r$ is "too-high" because it always stays above street $X$, while route $s$ is "too-low" because it always stays below street $Y$. Then the intersection point of $X$ and $Y$ must be below route $r$ but above route $s$. Therefore there is another route between $r$ and $s$ going through that intersection point. (Alternatively, if $X$ and $Y$ are the same street, then the route that begins on that street must be between $r$ and $s$.) In other words, a "too-high" route is never next to a "too-low" route.

The highest route can't be "too-low" because there's nothing above it; if it fails, it fails because it's "too-high". Similarly, the lowest route must be "too-low" if it fails. Therefore, going from top to bottom, we must switch from "too-high" to "too-low" at some point. To do so, there must be at least one route in between that is neither "too-high" nor "too-low": that route must visit every street.