第4题

设整数

n > 1

。山坡上有

n^2

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

A

和

B

各自运营

k

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

A

的

k

条缆车线路有

k

个不同的起点和

k

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

B

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

k

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

第 5/8 步：应用抽屉原理

通俗地说

C 中的 n+1 个站点必须分配到仅有的 n−1 条 B 链中，所以有两个站点落在同一条 B 链上。

n+1>n-1\quad\Longrightarrow\quad \exists P,Q\in C\text{ in one B-chain}.

详细分析

把 C 中至少 n+1 个站点分配到 n−1 条 B 链中。由于 n+1>n−1，抽屉原理保证 C 中有两个不同站点 P、Q 落在同一条 B 链上。它们同在 C 中，所以被 A 连接；又同在一条 B 链中，所以也被 B 连接。