12th Czech-Polish-Slovak Mathematics Competition

First we introduce some notation. Call each 100 m segment of a street an arrow, and each place where two streets meet a crossroad. If an arrow has the same direction as the street $WS$ or $WN$ (that is, it runs from the upper left to the bottom right or from the bottom left to the upper right), it is called a forward arrow, otherwise it is a back arrow.

In the solution we will use the following obvious lemma: Let the set of all crossroads be split into two sets $A$ and $B$ such that $W\in A$ and $E\in B$. Then the number of times the car drives along an arrow from $A$ to $B$ is one more than the number of times the car drives along an arrow from $B$ to $A$.

Let us split the set of all crossroads of Mar del Plata into two sets $A$ and $B$ by a vertical (i.e. north-south) line connecting two points located $100k+50$ m from $W$ – one on the $WN$ street and one on the $WS$ street – for some $k\in \{0,1,\dots ,n-1\}$. Fig. 5a and 5b show the splitting line for $k=3$ and $k=4$ respectively.

Fig. 5a

Fig. 5b

If $k$ is odd then the line intersects $k+1$ forward arrows (going from $\mathcal{A}$ to $\mathcal{B}$) and $k+1$ back arrows (going from $\mathcal{B}$ to $\mathcal{A}$). Even if the car would pass all the $k+1$ forward arrows, by the lemma, it can pass at most $k$ back arrows. Hence, at least one of the back arrows remains unpassed.

If $k\ge 2$ is even then the line intersects $k+2$ forward arrows and $k$ back arrows. The two northernmost forward arrows intersected by the line begin in the crossroad which has only one incoming arrow. This crossroad can be passed only once, hence one of the two northernmost forward arrows remains unpassed. The same holds for the two southernmost forward arrows. So we have at most $k$ forward arrows passed by the car and by the lemma at most $k-1$ back arrows. Together, we have at least 3 unpassed arrows at this level.

For $k=0$, we have only two forward arrows starting in $W$ intersected by the line. Clearly only one of them could be passed by the car and one remains unpassed.

In a similar way, we split the set of all crossroads by a vertical line connecting two points located $100k+50$ m from $E$ – one on the $SE$ street and one on the $NE$ street – for some $k\in \{0,1,\dots ,n-1\}$. The situation is sketched on Fig. 6a and 6b $k=3$ and $k=4$ respectively.

Fig. 6a

Fig. 6b

If $k$ is odd then the line intersects $k+1$ forward arrows and $k+1$ back arrows, and at least one of the back arrows remains unpassed.

If $k\ge 2$ is even then the line intersects $k+2$ forward arrows and $k$ back arrows. The two northernmost forward arrows end in the crossroad with only one outgoing arrow, hence one of them remains unpassed. The same holds for the two southernmost forward arrows. Again, we have at most $k$ forward arrows and at most $k-1$ back arrows passed by the car, which results in 3 unpassed arrows at this level.

For $k=0$, we have two forward arrows ending in $E$, only one of them could be passed by the car and one remains unpassed.

There is one unpassed arrow for any odd $k$, three for any even $k\ge 2$, and one for $k=0$, and all this happens twice. As $n$ is even and $k\in \{0,1,\dots ,n-1\}$, altogether, we have $$2\left(\frac{1}{2}n+3\left(\frac{1}{2}n-1\right)+1\right)=4n-4$$ unpassed arrows. The total number of arrows is $n\cdot 2(n+1)$, hence, the car cannot pass more than $$n\cdot 2(n+1)-(4n-4)=2n^2-2n+4$$ arrows.

On the other hand, there are many possible routes of the car consisting of $2n^2-2n+4$ arrows. One is sketched on Fig. 7 for $n=6$. When we use the same pattern in general case, the route can be subdivided into $\frac{1}{2}n$ parts by the crossroads lying on the $WS$ street located $200k$ m from $W$ for $k=1,2,\dots ,\frac{1}{2}n-1$.

Fig. 7

The first $\frac{1}{2}n-1$ parts differ only by shifting. Each of them consist of $n$ arrows of the same direction as $WN$, $n$ arrows of the opposite direction as $WN$, and $2(n-1)$ arrows perpendicular to $WN$. The last part consists of $n$ arrows of the same direction as $WN$ and $2(n+1)$ arrows perpendicular to $WN$. Therefore, the number of arrows on the entire route is $$(\frac{1}{2}n-1)(2n+2(n-1))+n+2(n+1)=2n^2-2n+4.$$

Answer. The length of the longest possible route of the car is $\frac{1}{10}(2n^2-2n+4)$ km.