2010-04-06 18:13| 
27 Comments | 本文内容遵从在继续探索多边形内接图形问题之前，我们先来看一个看似无关的趣题。从水平线上的一点起笔，在这条水平线上方随意画一条折线段，最后回到水平线上（如下图）。把这个折线段想象成一座座山峰。我们以最高峰所在位置为界把整座山分成左右两部分。现在，假设有一对相恋的登山者，一个站在最左侧的山脚出（即点 0 处），一个站在最右侧山脚处（即点 0' 处）。这两个人将同时从山脚出发，同时到达山顶，并且保证在此过程中他们俩总处于同一海拔高度。不管这座山是什么形状，这种浪漫的想法总可以实现吗？
注意，在登山的过程中，登山者可以为了照顾对方而走回头路。例如，对于图中所示的小山，两个人可以按照下列方法实现同步登山。左右两个人的路线分别为：
0 → 1 → 2 → 3 → 4 → 5 → 6 → 5 → 4 → 3 → 2 → 1 → 2 → 3 → 4 → 5 → 6 → 7
0'→ 1'→ 2'→ 3'→ 2'→ 3'→ 4'→ 5'→ 6'→ 5'→ 6'→ 7'→ 8'→ 9'→ 8'→ 9'→ 10'→ 11'
事实上，不管折线段是什么样，这样的登山方式总是能实现的。就像本 Blog 之前介绍的矩形剖分问题一样，这个问题也有数学归纳证明、构造证明、图论模型证明等多种证明方式。下面我们给出一个拓扑证明，它是我所见过的最巧妙的证明方式。
以左侧登山者所在位置为横轴，以右侧登山者所在的位置为纵轴。把所有位于同一高度的点对全部标在平面上，形成连续的曲线。下面我们只需要说明，这条曲线连通了最左下角的点和最右上角的点。为此，我们只需要说明任意一条从左上角到右下角的连续曲线必定会和这条曲线相交。而这是显然的，因为一个人从山顶走到山脚，另一个人从山脚走到山顶，他俩必然会有某一时刻在同一高度“相遇”。
sofa!
沙发啊
db
“下面我们只需要说明，这条曲线连通了最左下角的点和最右上角的点。”
可以到达右上角就说明两人在山顶相遇，但是这里并没有证明曲线的存在性。
板凳放在地板上，楼上不坐我来坐
地基……
哈哈，我喜欢爬山，不喜欢登山
强大的证明，不过跟内接多边形好像是没什么关系。。
问问：这些好东西都是在哪里看到的？？
[...] This post was mentioned on Twitter by 阳阳猪的 GR Share. 阳阳猪的 GR Share said: 玩转内接多边形（四）：登山引理 一个无关的问题 http://goo.gl/CXyG [...]
actually，我发现现在抢M牛的前十是一件很有意思的东西……挤进去，呵呵~~
NB啊
这个与不动点一种证明方法是相同的。即在[0,1]区间长度为1的丝线，折叠后仍放到原来的[0,1]区间上，那么不管将铁丝怎么折叠，总有一个点仍处于折叠前的位置。这个方法与上是一样的
原来浪漫还可以这样！
这个问题确实很有趣，我曾经在top coder 网站上看到过类似的问题 当时只是想了一下 倒没去证明 看到楼主的文章 有些启发 我再去看看我的问题
我见过这个证明,在一本名为《最迷人的数学趣题》的书里
有意思。
o...
妙啊！
这个证明
人气啊 真高
http://www.tchack.net/blog
似乎有点问题,要首先证明这曲线一定是连续的才行
我觉得那两个数字一定要同奇偶才行
不错，不错，支持楼上说的
楼上二位问得有理。博主没说明白，其实他证明有交点的做法，就是在证连续。如果连续，沿连续线从左下到右上就刻画了同步登山的走法。
如果不连续，则存在从左上到右下的一条路径从间断处通过，也就是说一个人从山顶往下走，一个人从山脚往上走，居然不会出现走到同一高度的情形，显然不可能。
[...] 我们曾经用两种巧妙的方法证明了这样一个命题：任意凸多边形内均存在内接菱形。利用上次讲到的登山引理，我们可以证明一个更强的命题：任意多边形内均存在内接菱形。 [...]
由于连续性，必定存在一系列的曲线，然后利用利用类似连通性的概念证明平面被隔开了
回复地板上的nacre，存在性是Brouwer不动点定理的一维情形，当然直接证明也不难。
不错 值得考虑！