第4题

设整数

n > 1

。山坡上有

n^2

个站点，它们的海拔高度各不相同。两家缆车公司

A

和

B

各自运营

k

条缆车线路；每条缆车线路把乘客从某个站点直接送到更高的站点，中途不停靠。

A

的

k

条缆车线路有

k

个不同的起点和

k

个不同的终点，并且起点越高的缆车，其终点也越高。同样的条件对

B

也成立。如果可以从较低的站点出发，只使用该公司的一条或多条缆车线路（不允许其他任何站点间的移动）到达较高的站点，就说这两个站点被该公司连接。求最小的正整数

k

，使得无论两家公司如何运营，都能保证存在两个同时被两家公司连接的站点。

第 7/8 步：让 A 用行、B 用列

上一步下一步

通俗地说

横向连接相邻站点使每一行成为 A 链，纵向连接相邻站点使每一列成为 B 链；两家公司都恰好使用 n(n−1) 条缆车。

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

详细分析

令 A 运营从 (i,j) 到 (i,j+1) 的 n(n−1) 条缆车，其中 1≤i≤n、1≤j<n；令 B 运营从 (i,j) 到 (i+1,j) 的 n(n−1) 条缆车，其中 1≤i<n、1≤j≤n。沿 A 缆车海拔增加 n，沿 B 缆车海拔增加1。此外，在每个起点海拔区间内，对应终点海拔的顺序保持不变，不同区间彼此不重叠；因此两家公司都满足“起点越高终点越高”的单调条件。