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

KeyTo9_Fans

这个问题的讨论时限到了，下面公布我的证明。

我有$2$个版本的证明：

1、自然语言版本

这个版本把第一个序列称为“四连通路径”，第二个序列称为“八连通路径”，$N$称为棋盘的行，$M$称为棋盘的列，$(i,j)$就是棋盘的第$i$行第$j$列。



2、数学语言版本

这个版本从定义出发，完全用数学语言来证明。由于需要分别讨论的情况很多，因此篇幅很长。

hujunhua

暂时只看了文字版，觉得下图不能由你的操作方法进行缩减。是我理解有问题吗？


但愿数学版是成立的。

hujunhua

八连通称为黑子，四连通称为白子。
文字版还需要补充简化操作：应简化为没有枝的路径，不靠棋盘边的黑子周围只保留2个黑子，不靠棋盘边的白子周围只保留2个白子。删除子时保证剩下的仍然符合约束条件。
如此一来，黑龙和白龙都只有两个端。

KeyTo9_Fans

路径是有顺序的，下图的第$1$张图用蓝线标出了白棋的四连通路径是如何依次经过棋盘上的点的。



第$1$张图属于情况$3$，应该旋转$90$度。

旋转后，四连通路径仍然连接上下两边，只是起点（终点）不在第一行（最后一行）。

于是要简化，只保留路径于最后一次经过第一行到最先一次经过最后一行的那一段。

简化后，四连通路径的长度减小了。