第4题

设整数

n > 1

。山坡上有

n^2

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

A

和

B

各自运营

k

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

A

的

k

条缆车线路有

k

个不同的起点和

k

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

B

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

k

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

第 8/8 步：完成下界构造

上一步下一步

通俗地说

被 A 连接的站点对恰好是同一行中的站点对，被 B 连接的站点对恰好是同一列中的站点对；不同站点不可能同时满足两个条件。

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

详细分析

在 A 中，每一行是一条路径，所以两个不同站点被 A 连接，当且仅当它们第一坐标 i 相同。在 B 中，每一列是一条路径，所以两个不同站点被 B 连接，当且仅当它们第二坐标 j 相同。不同站点不可能同时具有相同的 i 和相同的 j。因此当 k₀=n²−n 时，可能不存在同时被两家公司连接的站点对；而前面的论证表明 k=n²−n+1 总是足够。故能保证的最小值是 n²−n+1。