1. XenForo 1.5.14 中文版——支持中文搜索!现已发布!查看详情
  2. Xenforo 爱好者讨论群:215909318 XenForo专区

从迷宫入口进去,沿着右手边的墙走,是否能走到出口?

本帖由 漂亮的石头2015-02-09 发布。版面名称:知乎日报

  1. 漂亮的石头

    漂亮的石头 版主 管理成员

    注册:
    2012-02-10
    帖子:
    486,020
    赞:
    46
    [​IMG] 王筝,数学系在读

    对于这种迷宫,题主的方法是一定可行的。

    [​IMG]

    (图片来自百度搜索)

    要求有两个:

    第一,迷宫是一个有外墙的矩形,并且仅有一个出口,一个入口。

    第二,迷宫至少要有一个解。

    以上图为例做一下说明。首先把墙想象成一个个气球或者是气泡,墙的边界肯定是一个一个的圈,彼此肯定不会相交。第一个要求保证了这一点。

    考虑入口处的 A 点和出口处的 B 点

    [​IMG]

    因为第二个要求,解一定至少存在一个。因此整个图里面墙一定不止一片。用拓扑的话来说,墙的连通分支一定不只一个。因为解是从入口到出口的,所以外墙不会在同一个分支里。如下图,外墙上一定有黑色的部分。

    而 A 和 B 一定在同一个连通分支里面,因为 A 和 B 能通过边框上的墙连接起来。我们可以在这个图中把这一片墙标出来,就是蓝色的部分。第二个要求保证了蓝色部分一定不是全部。

    [​IMG]

    注意一点,拓扑上来讲,蓝色的这一片不一定同胚于 D^2 的,因为可能中间是有洞的,但是没关系,我们关心的是她的各个边界中的其中一个。事实上,我们已经找到了一半的边界,也就是迷宫的外墙。如下图的红线

    [​IMG]

    而前面已经说了,每一条边界一定是一个封闭曲线,因此我们一定可以把上面的红线补成一段完整的曲线。补出来的那一部分一定全部落在迷宫里面,若不然,那么就会跑到黑色的部分去了,但是蓝色和黑色不是同一个分支,这是不可能的。

    也就是说,红线的另外一半恰好全部落在迷宫内部,这就是迷宫的解了。

    因为这一半是墙的边界,因此沿着她走的时候一定是可以扶墙的。而扶墙的时候不用换手,这是蓝色部分的墙可定向保证的。由于一开始是右手扶着进去,因此就一直是右手扶墙了。

    以上。

    查看知乎原文
     
正在加载...