本
文
摘
要
这是抖音之前一个很流行的问题，能否用一条连续的线，将图中所有的点遍历过一遍。要求不能经过x点，只能用水平和竖直的线段相连，不能交叉，且只能经过一个点一次。
显然，对于这样的题目，一般都是无解的，否则就失去了这种题存在的意义【手动狗头】。我们可以简单尝试一下
果然不太行。
那怎么证明这题无解呢？
注意到题目是5×5的点集，如果我们稍微改变下点集的尺寸，看会发生什么结果？
额，好像很轻松就连上了。看来x点的影响不仅仅是局部，如果是局部的话，那么我们在外面多加几行点应该不会改变无解的结果。
对于这种题，老山直觉地采用奇偶法，把原图变成奇偶相间的点，如下图，我们把奇点标成绿色，偶点标成蓝色。
为了给个奇点和偶点的定义，我们可以给这些点给成（1,1）到（5,5）的坐标。如果x坐标值和y坐标值和为偶数，则为偶点，和为奇数，则为奇点。
当我们在图上连线的时候，所有的线段必然是一边是奇点一边是偶点。对于这个显而易见的结论，老山也做个简单的证明。定义线段两端点为出发点和终点，由于线段是水平或垂直，所以终点的坐标是出发点的x坐标±1或是y坐标±1变化来的，因此两点的坐标和必然差1，根据奇偶点的定义，必然是一个奇点一个偶点。
那么，对于图上一条连续的线，必然是奇偶点相同或者奇偶点数目差1。而图中原本有12个奇点和13个偶点，但有个奇点又被x替代。因此原题要求的连线需要通过11个奇点和13个偶点。这显然是不可能的。证毕。
在解题中，我们通常需要抓住一些恒定不变的属性。这道题，我们便是抓住了图上线均由奇偶点差为0或1的属性，来证否这个命题的。
本文的所有图都使用python做的，由于代码比较简单，就不给github了，直接贴在下面。
import matplotlib.pyplot as plt plt.xkcd() def draw(savepath, odd_color=r, even_color=r, line=None, imax=5, jmax=5): plt.figure(figsize=(imax, jmax)) odd_x, odd_y, even_x, even_y = [], [], [], [] for i in range(imax): for j in range(jmax): if (i==1) and (j==jmax-1): continue if (i+j)%2 ==0: even_x.append(i) even_y.append(j) else: odd_x.append(i) odd_y.append(j) plt.plot(odd_x, odd_y, f{odd_color}o) plt.plot(even_x, even_y, f{even_color}o) plt.plot([1], [jmax-1], f{odd_color if jmax%2!=0 else even_color}x, markersize=8) if line: plt.plot([p[0] for p in line], [p[1] for p in line], m-, linewidth=2) plt.axis(off) plt.savefig(savepath) if __name__=="__main__": line_show = [(0, 4), (0, 3), (1, 3), (1, 2)] draw(test0.png, r, r, line_show, 5, 5) line_try = [(0, 4), (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (1, 1), (1, 2), (1, 3), (2, 3), (2, 2), (2, 1), (2, 0), (3, 0), (4, 0), (4, 1), (3, 1), (3, 2), (4, 2), (4, 3), (3, 3), (3, 4), (2, 4)] draw(test1.png, r, r, line_try, 5, 5) line_56 = [(0, 5), (0, 4), (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (2, 4), (2, 3), (2, 2), (2, 1), (2, 0), (3, 0), (4, 0), (4, 1), (3, 1), (3, 2), (4, 2), (4, 3), (3, 3), (3, 4), (4, 4), (4, 5), (3, 5), (2, 5)] draw(test2.png, r, r, line_56, 5, 6) draw(test3.png, g, b, None, 5, 5) draw(test4.png, g, b, line_show, 5, 5)老山会致力做关于数学趣题、python编程和深度学习相关的内容，尽我所能深入分析，绝不浅尝辄止。如果您对老山的文章感兴趣，不妨加个关注~
