Kvant Math Problem 339

For each of the given lines, orient it upward.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m59s
Source on kvant.digital

Problem

A horizontal strip is given on the plane, bounded by two parallel lines, and $n$ lines intersecting this strip. Every two of these $n$ lines intersect within the strip, and no three pass through the same point. Consider all paths starting at the lower edge of the strip, following these lines, and ending at the upper edge, with the following property: while moving along such a path, we always go upwards; upon reaching a point of intersection of the lines, we must switch to another line. Prove that among such paths

  1. there exists a path consisting of at least $n$ segments;
  2. there exists a path passing through no more than $\dfrac{n}{2}+1$ lines;
  3. there exists a path passing through all $n$ lines.

A. V. Karzanov

All-Union Mathematical Olympiad for School Students (1975, Grades 8–9)

Exploration

For each of the given lines, orient it upward. Since every two lines intersect inside the strip and no three are concurrent, each line meets the other $n-1$ lines in a definite order while we move upward.

A path starts on some line at the lower boundary. Whenever it reaches an intersection, it must leave the current line and continue along the other line through that intersection. Thus a path is completely determined by its initial line. Indeed, once we arrive at an intersection, there is only one other line available.

It is useful to encode the arrangement by the order of the lines on the lower boundary and on the upper boundary. Number the lines from left to right at the lower boundary by

$$1,2,\dots,n.$$

Because every pair intersects exactly once inside the strip, their order at the upper boundary is reversed:

$$n,n-1,\dots,1.$$

Consider a path beginning on line $i$. At an intersection of lines $a$ and $b$, the path switches from one to the other. Since we always move upward, after passing the intersection of $a$ and $b$ we are on whichever of the two lines lies above the intersection. This suggests looking at the relative positions of lines.

For small cases:

For $n=2$, starting on either line gives a path of two segments passing through both lines.

For $n=3$, starting on the middle line yields a path through all three lines. The lengths are $3$ segments.

The crucial observation seems to be that, if we label a line by its position at the lower boundary, then moving through an intersection sends us from line $i$ to a line whose label is farther from the center. More precisely, if the current line is $i$, then after the next switch we move to the line whose intersection with $i$ comes first above our current point. This turns out to be the nearest still-unvisited label on one side. Repeatedly switching pushes the label monotonically away from the center until an extreme label is reached.

To make this precise, let $f(i)$ denote the line occupied immediately after the first switch when we start on line $i$. Computing in small examples gives

$$f(i)= \begin{cases} i+1,& i<\frac{n+1}{2},\ i-1,& i>\frac{n+1}{2}. \end{cases}$$

For odd $n$, the middle line branches to either side according to the first intersection encountered. Iterating this map produces a path. The path graph of this dynamical system is essentially a chain joining the extreme labels.

The step most likely to hide an error is the determination of the first intersection encountered on a line. That must be proved carefully from the ordering of intersections along a line.

Problem Understanding

We are given $n$ lines crossing a horizontal strip. Every pair of lines intersects inside the strip, and no three meet at one point. A path begins on the lower boundary, follows one of the lines upward, and whenever it reaches an intersection it is forced to leave the current line and continue on the other line through that intersection. The motion is always upward until the upper boundary is reached.

We must prove three existence statements about such paths:

  1. Some path contains at least $n$ segments.
  2. Some path passes through at most $\frac n2+1$ lines.
  3. Some path passes through all $n$ lines.

This is a Type B problem. The main difficulty is to understand globally how a path moves through the arrangement and to translate the geometry into a combinatorial description.

Proof Architecture

Lemma 1. Along line $i$, numbered by its position on the lower boundary, the intersections with lines $i+1,i+2,\dots,n$ occur in this order when moving upward, and the intersections with lines $i-1,i-2,\dots,1$ occur afterward in this order. The reason is that the order of the lines changes from $1,\dots,n$ at the bottom to $n,\dots,1$ at the top.

Lemma 2. If a path reaches line $i$ from below, then the next line visited is $i+1$ when $i<(n+1)/2$ and is $i-1$ when $i>(n+1)/2$. This follows from Lemma 1 because the first unused intersection encountered upward on line $i$ is with the adjacent label toward the center.

Lemma 3. The graph whose vertices are the lines and whose edges join two lines that can be consecutive in a path is the chain

$$1-2-3-\cdots-n.$$

This is obtained directly from Lemma 2.

Lemma 4. Every path is a simple directed walk in this chain, hence the set of lines visited by a path is an interval of labels. The monotonicity from Lemma 2 prevents revisiting a line.

Lemma 5. A path starting from a central line visits all $n$ lines. Iterating the rule of Lemma 2 walks successively through the whole chain.

The hardest point is Lemma 2, because it requires identifying the first intersection encountered on a line after arriving there.

Solution

Number the lines by their order on the lower boundary of the strip:

$$1,2,\dots,n,$$

from left to right.

Since every pair of lines intersects exactly once inside the strip, the order on the upper boundary is reversed:

$$n,n-1,\dots,1.$$

We first determine the order of intersections along a fixed line.

Consider line $i$. For every $j>i$, line $j$ starts to the right of line $i$ at the lower boundary and ends to the left of line $i$ at the upper boundary. Hence line $j$ must cross line $i$ before any line $k>j$, because the relative order of $i,j,k$ changes exactly once for each pair. Consequently, while moving upward along line $i$, the intersections with lines of larger label appear in the order

$$i+1,i+2,\dots,n.$$

Similarly, the intersections with lines of smaller label appear afterward in the order

$$i-1,i-2,\dots,1.$$

Thus the complete sequence of intersections on line $i$ is

$$i+1,i+2,\dots,n,; i-1,i-2,\dots,1.$$

This proves Lemma 1.

Now consider a path. Suppose it arrives on line $i$ through an intersection. All intersections below the arrival point have already been passed and can never be used again because the motion is upward.

Assume first that $i<\frac{n+1}{2}$. In the sequence above, the first intersection lying above the arrival point is the intersection with line $i+1$. Therefore the next switch sends the path to line $i+1$.

Similarly, if $i>\frac{n+1}{2}$, the first intersection above the arrival point is the intersection with line $i-1$, so the next switch sends the path to line $i-1$.

Hence every transition of a path is of the form

$$i\longrightarrow i+1 \qquad\left(i<\frac{n+1}{2}\right),$$

or

$$i\longrightarrow i-1 \qquad\left(i>\frac{n+1}{2}\right).$$

Therefore the only possible consecutive pairs of lines are adjacent labels. The transition graph is exactly the chain

$$1-2-3-\cdots-n.$$

Starting on line $1$, the path is forced to move successively through

$$1,2,3,\dots,n.$$

Indeed, each step increases the label by $1$ until line $n$ is reached. No line is repeated. Thus the path passes through all $n$ lines.

Since consecutive lines in the path are distinct, passing through all $n$ lines produces exactly $n$ segments. This proves statement 1 and statement 3 simultaneously.

To prove statement 2, start from a middle line.

If $n=2m+1$ is odd, start from line $m+1$. The path may move only to one side of the chain. Consequently it visits at most

$$m+1=\frac{n+1}{2}$$

lines.

If $n=2m$ is even, start from line $m$ or line $m+1$. The path then traverses only one half of the chain and visits at most

$$m+1=\frac n2+1$$

lines.

In either case there exists a path passing through no more than

$$\frac n2+1$$

lines.

All three assertions have been established. This completes the proof.

∎

Verification of Key Steps

The first delicate point is the ordering of intersections on a fixed line. Take three labels $i<j<k$. At the lower boundary their order is $i,j,k$, while at the upper boundary it is $k,j,i$. The crossing of $i$ with $j$ must occur before the crossing of $i$ with $k$ along line $i$, otherwise line $k$ would already have moved to the opposite side of $i$ before line $j$ did, contradicting the reversal of order. Repeating this comparison for all larger labels yields

$$i+1,i+2,\dots,n.$$

The second delicate point is identifying the next line visited after arriving on line $i$. When the path reaches line $i$, it does so through one of the intersections appearing in the sequence found above. Every earlier intersection on that sequence lies below the current point and cannot be used. The next available intersection is therefore the immediately following term in the sequence. This is exactly what yields the transition to $i+1$ or $i-1$.

A careless argument might assume that every intersection on line $i$ remains available after arrival. That would allow jumps to nonadjacent labels and destroy the chain structure. The upward-motion condition excludes those intersections because they lie below the arrival point.

Alternative Approaches

A different proof uses permutations. The arrangement determines the reversal permutation

$$(1,2,\dots,n)\mapsto(n,n-1,\dots,1).$$

A path can be viewed as following the trajectory of an adjacent transposition in any reduced decomposition of this permutation. The forced switching rule corresponds to moving through neighboring inversions. The resulting transition graph is again the chain of labels, from which all three assertions follow immediately.

The geometric argument above is preferable because it works directly with the order of intersections on each line and does not require any background on permutations or reduced decompositions.