一个树林里有 100 个村庄，它们之间有 1000 条小路，每条小路都连接着两个不同的村庄。每条小路 e 都有一条难度系数 l(e) ，所有小路的难度系数都不相同。现在有一个探险家，他想要选择一条长度为 20 的路径，使得所经过的小路的难度系数不断增加。求证：他总能找到这样的路径。
探险家可以任意选择路径的起点和终点。
为了证明这个结论，让我们在 100 个村庄里各放置一个探险家，然后按照难度系数从小到大的顺序依次清点树林中的 1000 条小路，每点到一条小路 u-v ，就交换小路两端的两个探险家的位置，让位于 u 的探险家移动到 v 去，让位于 v 的探险家移动到 u 去。遍历完所有的小路后，每个探险家的移动轨迹就都构成了一个难度系数不断递增的路径。由于每次点到一条小路时，我们都会让其中两个探险家各移动一步，因此最终所有探险家一共移动了 2000 步，换句话说所有 100 条路径的总长度是 2000 。显然，不可能每条路径的长度都小于 20 ，因而其中一定有一条路径，它的长度至少是 20 。
这个谜题来自 Peter Winkler ，出处见这里。
竟然有沙发。。。
板凳
这些都是很不错的组合题啊
题目的要求是长度刚好为20的路径，但是并不一定存在这路径吧，只能证明一定存在长度不小于20的路径。
如果我是想求长度最长的路径，应该用什么算法？
文中求出的100条路径中的最大值，很可能不是真正最长的那条
@地板，一条长度大于20的难度递增路径，必然包含一条子路径起长度等于20。所以找到一条长度不小于20的难度递增路径，等于找到了一条长度等于20的难度递增路径。
帅。
不錯，用抽屜原理來證明
同理可證，任意遞增或遞減(例: 增x3,減x4,增x5,減x3,增x5)，總長度為20的路徑都能給出，只要更改”依次清點”的順序即可。在手頭毫無特定訊息－－道路的連接態或權重－－的狀況下，能夠得知這樣的性質，妙矣。
很有创意的证明过程
今年(2014)俄罗斯9年级第8题也是这种方法
没有监督的时候也要严格要求自己。