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 8 of 8: Finish the lower-bound construction

Previous step Next step

In plain words

A-linked pairs are exactly pairs in one row, and B-linked pairs are exactly pairs in one column; distinct stations cannot satisfy both conditions.

P\sim_A Q\Longleftrightarrow i_P=i_Q,\qquad P\sim_B Q\Longleftrightarrow j_P=j_Q.

Detailed analysis

Under A, each row is one path, so two distinct stations are A-linked exactly when they have the same first coordinate i. Under B, each column is one path, so two distinct stations are B-linked exactly when they have the same second coordinate j. A distinct pair cannot have both the same i and the same j. Thus for k₀=n²−n there need not be any pair linked by both companies, while the preceding argument proves k=n²−n+1 always suffices. Therefore the smallest guaranteed value is n²−n+1.