趣题：证明边权递增的路径始终存在

一个树林里有 100 个村庄，它们之间有 1000 条小路，每条小路都连接着两个不同的村庄。每条小路 e 都有一条难度系数 l(e) ，所有小路的难度系数都不相同。现在有一个探险家，他想要选择一条长度为 20 的路径，使得所经过的小路的难度系数不断增加。求证：他总能找到这样的路径。

探险家可以任意选择路径的起点和终点。

为了证明这个结论，让我们在 100 个村庄里各放置一个探险家，然后按照难度系数从小到大的顺序依次清点树林中的 1000 条小路，每点到一条小路 u-v ，就交换小路两端的两个探险家的位置，让位于 u 的探险家移动到 v 去，让位于 v 的探险家移动到 u 去。遍历完所有的小路后，每个探险家的移动轨迹就都构成了一个难度系数不断递增的路径。由于每次点到一条小路时，我们都会让其中两个探险家各移动一步，因此最终所有探险家一共移动了 2000 步，换句话说所有 100 条路径的总长度是 2000 。显然，不可能每条路径的长度都小于 20 ，因而其中一定有一条路径，它的长度至少是 20 。

这个谜题来自 Peter Winkler ，出处见这里。