Problem 4

There is an integer

n > 1

. There are

n^2

stations on a slope of a mountain, all at different altitudes. Each of two cable car companies,

A

and

B

, operates

k

cable cars; each cable car provides a transfer from one of the stations to a higher one (with no intermediate stops). The

k

cable cars of

A

have

k

different starting points and

k

different finishing points, and a cable car which starts higher also finishes higher. The same conditions hold for

B

. We say that two stations are linked by a company if one can start from the lower station and reach the higher one by using one or more cars of that company (no other movements between stations are allowed). Determine the smallest positive integer

k

for which one can guarantee that there are two stations that are linked by both companies.

Step 1 of 8: Represent each company by increasing chains

Previous step Next step

In plain words

Distinct starting and finishing points prevent branching, while every car goes uphill, so a company's network is a collection of simple increasing paths.

\text{Each company's cars form vertex-disjoint directed paths.}

Detailed analysis

For one company, every station is the starting point of at most one car and the finishing point of at most one car. Orient each car from lower to higher altitude. Thus every vertex has indegree and outdegree at most one; because altitude strictly increases along every edge, directed cycles are impossible. The components are therefore vertex-disjoint directed paths, including isolated stations. Two stations are linked by that company exactly when they lie in the same path component.