求证两个整数坐标序列有公共元素
(a_1,b_1)，(a_2,b_2)，……，(a_n,b_n)是一个整数坐标序列，满足：1<=a_i<=N，1<=b_i<=M，i=1,2,3,...,n
$a_1=1$，$a_n=N$
$|a_i-a_(i+1)|+|b_i-b_(i+1)|=1$，$i=1,2,3,...,n-1$
$(c_1,d_1)$，$(c_2,d_2)$，……，$(c_m,d_m)$是另一个整数坐标序列，满足：
$1<=c_i<=N$，$1<=d_i<=M$，$i=1,2,3,...,m$
$d_1=1$，$d_m=M$
$|c_i-c_(i+1)|<=1$，$|d_i-d_(i+1)|<=1$，$i=1,2,3,...,m-1$
求证：两个坐标序列有公共元素。（即存在$i$、$j$使得$a_i=c_j$、$b_i=d_j$） 这个好像画图是很显然的 假想在(ai,bi)点放上围棋黑子。棋盘大小为左下角(1,1)，右上角(N，M)。
|ai-ai+1|+|bi-bi+1|=1 ---->(ai,bi)与(ai+1|, bi+1)是相连的棋子。所以从(a1,b1)到(an|, bn)是一串连通的n颗黑棋。由于第1子在第1列，第n子在第N列，所以黑棋连续横跨整个棋盘。
假想在(ci,di)点放上围棋白子, 同理可得白棋连续纵贯整个棋盘。
所以黑白棋龙必然相交。 呵呵，有那么必然吗？
要注意一下$(a_i,b_i)$和$(a_{i+1},b_{i+1})$的关系与$(c_i,d_i)$和$(c_{i+1},d_{i+1})$的关系是不一样的：
$|a_i-a_{i+1}|+|b_i-b_{i+1}|=1$
$|c_i-c_{i+1}|<=1$，$|d_i-d_{i+1}|<=1$
如果第一个序列也像第二个序列那样，结论就不成立了。
如下图所示：
黑棋连续横跨整个棋盘的同时，白棋连续纵贯整个棋盘。 有那么必然吧
第一个关系从左到右形成横断，考虑第二个关系穿越的那一步即可 呵呵，有那么必然吗？
要注意一下$(a_i,b_i)$和$(a_{i+1},b_{i+1})$的关系与$(c_i,d_i)$和$(c_{i+1},d_{i+1})$的关系是不一样的：
$|a_i-a_{i+1}|+|b_i-b_{i+1}|=1$
$|c_i-c_{i+1}|
KeyTo9_Fans 发表于 2010-3-29 19:35 http://bbs.emath.ac.cn/images/common/back.gif
哦，是我疏忽了，我以为白棋是$|c_i-c_{i+1}|+|d_i-d_{i+1}|<=1$
$|c_i-c_{i+1}|<=1$，$|d_i-d_{i+1}|<=1$, 那么白棋的联络比黑棋要弱一些，但不疏于尖(围棋术语)，所以与黑棋还是要相交的。 这个题目直观的用图解方法很显然，通常我们可以直接使用而不需要去证明它。
但是如果要求严格去证明之，可以采用如下方法。
对于给定的折线S:${(c_i,d_i)}$，首先如果它自相交，可以去除一些点，使得余下部分保持原来性质但是不会自相交。此后，非常容易可以将矩形内部所有点被分成3类，S上面部分的点，S上的点和S下面的点。
然后容易证明如果${(a_i,b_i)}$序列中一个点是S上面的，那么下一个点不能是S下面的 请大家继续，我非常想弄清这个问题。 去除多余的点，使得路径不自相交，这一步做得很好。
可是将矩形内部所有点分$3$类就说不清楚了。
因为路径是可以随便绕的，想绕多复杂就有多复杂。
所以很难说清楚哪些点是上面的，哪些点是下面的。
再下一步，如果一个点是上面的，怎样说明下一个点不能是下面的？ 有点难度等我考虑考虑
页:
[1]
2