求证两个整数坐标序列有公共元素

KeyTo9_Fans

$(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$）

mathe

这个好像画图是很显然的

hujunhua

假想在(a_i,b_i)点放上围棋黑子。棋盘大小为左下角(1,1)，右上角(N，M)。

|a_i-a_i+1|+|b_i-b_i+1|=1 ---->(a_i,b_i)与(a_i+1|, b_i+1)是相连的棋子。所以从(a₁,b₁)到(a_n|, b_n)是一串连通的n颗黑棋。由于第1子在第1列，第n子在第N列，所以黑棋连续横跨整个棋盘。
假想在(c_i,d_i)点放上围棋白子, 同理可得白棋连续纵贯整个棋盘。

所以黑白棋龙必然相交。

KeyTo9_Fans

呵呵，有那么必然吗？

要注意一下$(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$

如果第一个序列也像第二个序列那样，结论就不成立了。

如下图所示：



黑棋连续横跨整个棋盘的同时，白棋连续纵贯整个棋盘。

shshsh_0510

有那么必然吧
第一个关系从左到右形成横断，考虑第二个关系穿越的那一步即可

hujunhua

呵呵，有那么必然吗？

要注意一下$(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

哦，是我疏忽了，我以为白棋是$|c_i-c_{i+1}|+|d_i-d_{i+1}|<=1$
$|c_i-c_{i+1}|<=1$，$|d_i-d_{i+1}|<=1$, 那么白棋的联络比黑棋要弱一些，但不疏于尖(围棋术语)，所以与黑棋还是要相交的。

mathe

这个题目直观的用图解方法很显然，通常我们可以直接使用而不需要去证明它。
但是如果要求严格去证明之，可以采用如下方法。
对于给定的折线S:${(c_i,d_i)}$，首先如果它自相交，可以去除一些点，使得余下部分保持原来性质但是不会自相交。此后，非常容易可以将矩形内部所有点被分成3类，S上面部分的点，S上的点和S下面的点。
然后容易证明如果${(a_i,b_i)}$序列中一个点是S上面的，那么下一个点不能是S下面的

ftg1029

请大家继续，我非常想弄清这个问题。

KeyTo9_Fans

去除多余的点，使得路径不自相交，这一步做得很好。

可是将矩形内部所有点分$3$类就说不清楚了。

因为路径是可以随便绕的，想绕多复杂就有多复杂。

所以很难说清楚哪些点是上面的，哪些点是下面的。

再下一步，如果一个点是上面的，怎样说明下一个点不能是下面的？

dalaopeng

有点难度  等我考虑考虑