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 7 of 8: Use rows for A and columns for B

Previous step Next step

In plain words

Horizontal adjacent links make each row one A-chain, while vertical adjacent links make each column one B-chain; both companies use exactly n(n−1) cars.

A:(i,j)\to(i,j+1),\qquad B:(i,j)\to(i+1,j).

Detailed analysis

Let A operate the n(n−1) cars from (i,j) to (i,j+1) for 1≤i≤n and 1≤j<n, and let B operate the n(n−1) cars from (i,j) to (i+1,j) for 1≤i<n and 1≤j≤n. Along an A-car the altitude increases by n, and along a B-car it increases by 1. Moreover, within each block of starting altitudes the corresponding finishing altitudes preserve the same order, and different blocks do not overlap; hence each company satisfies the required monotonicity condition that higher starts have higher finishes.