Problem 1059

215. Let $A_{1}, A_{2}, \ldots, A_{n}$ be the points of intersection of the lines with the lower edge of the strip, numbered in order (from left to right), and $B_{1}, B_{2}, \ldots, B_{n}$ be the points of intersection with the upper edge (also from left to right). We will number the paths starting from points $A_{1}, A_{2}, \ldots, A_{n}$ in order with the numbers $1, 2, \ldots, n$. From the rules of constructing the paths, the following properties follow.

$1^{\circ}$ Each segment of each line is traversed by exactly one path.

$2^{\circ}$ Adjacent paths, the $k$-th and $(k+1)$-th, touch at vertices, and the $k$-th path always lies to the left of the $(k+1)$-th path (for each $k=1, 2, \ldots, n-1$). Non-adjacent paths do not have any common points.

$3^{\circ}$ The $k$-th path ends at point $B_{k}$.

Now let's prove all the statements of the problem.

a) Consider all paths with odd numbers. According to property $1^{\circ}$, they cannot have common points, and their number is at least $n / 2$.

b) Let's count the total number of segments on all paths in two ways. Each segment $A_{i} B_{n+1-t}$ of one of the lines is divided by points of intersection with the other lines into $n$ segments. Therefore, the total number of segments is $n^{2}$. According to $1^{\circ}$, we should get the same sum $n^{2}$ by summing the number of segments in all $n$ paths. Therefore, at least one of the summands will be no less than $n$.

Of course, statement b) also follows from g).

c) Let's estimate the number of segments in the two extreme paths, the 1st and the $n$-th.

These paths bound convex sets lying to the left of the 1st path and to the right of the $n$-th path; the first path lies within the angle $A_{1} P B_{1}$, and the second within the angle $A_{n} P B_{n}$, where $P$ is the point of intersection of the lines $A_{1} B_{n}$ and $A_{n} B_{1}$. The other lines $A_{2} B_{n-1}, A_{3} B_{n-2}, \ldots, A_{n-1} B_{2}$ can have a common segment only with one of the two extreme paths (specifically, with the one that lies on the other side of this line from the point $P$). Therefore, the total number of segments in the two extreme paths is no more than $4 + (n-2)$ segments. Therefore, in one of them, there are no more than $\frac{n}{2} + 1$ segments.

d) Consider the middle path, i.e., the path with number $m = (n+1) / 2$ if $n$ is odd and $m = n / 2$ if $n$ is even, and prove that it passes through all the lines (Fig. 89). Indeed, it divides the strip into two regions: each of the segments $A_{1} B_{n}$ and $A_{2} B_{n-1}, \ldots, A_{n} B_{1}$ starts in one of the regions (possibly on the boundary) and ends in the other and, therefore, has a common point with the middle path, and hence (by the rule of constructing paths) - a common segment.

$\nabla$ It would be interesting to obtain good lower and upper bounds for the number of segments in the maximum (by the number of segments) path.

!

Fig. 89