技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 经典证明:能否在平面上写下不可数个不相交的Y?

经典证明:能否在平面上写下不可数个不相交的Y?

浏览:1994次  出处信息

     这篇文章收录了 Which Way Did the Bicycle Go 趣题集中一个非常有趣的问题:是否有可能在平面上画不可数个不相交的 8 ?答案是否定的。证明方法非常简单。对于任意一个 8 字形,在两个洞里各取一个有理点 P 、 Q (由于平面上的有理点是稠密的,这是总能办到的),则称这个 8 字形圈住了有理点对 (P, Q) 。注意到由于 8 字形不能相交,因此两个 8 字形不可能圈住同一对有理点。由于平面上的有理点对是可数的,因此 8 字形的数量也是可数的。

    

     注意到,平面上显然能够容下不可数个不相交的直线段,也显然能够容下不可数个不相交的圆(比方说一系列同心圆)。在 Mathematical Puzzles 一书里, Peter Winkler 提出了这样一个问题:我们能在平面上写下不可数个不相交的字母 Y 吗?

    

      

      

      

      

      

      

      

      

         答案是否定的。下面有一个漂亮的证明,这是由 Randy Dougherty 给出的。让我们先来看一个经典结论:假设平面上有三个红点和三个蓝点,那么我们绝不可能用线条把每一个红点和每一个蓝点都连起来,并且保证这 9 根线条互不相交(不信的话你可以试一试)。从图论的角度来说,就是完全二分图 K3,3 不是一个平面图。利用 Euler 公式我们可以很快证明这一点:把一个平面图的顶点数、边数和区域数(包括最外面那个无限大的区域)分别记为 V 、 E 、 F ,则 Euler 公式告诉我们 F = E - V + 2 。由于每条边都同属于两个区域,因而所有区域的平均边数为 2E / F 。在完全二分图 K3,3 中有 6 个顶点和 9 条边,若它是一个平面图,则它应该有 9 - 6 + 2 = 5 个区域,于是每个区域平均拥有 18/5 条边。这说明该图中至少存在一个边数小于 4 的区域,但对于一个二分图来说这是不可能的。

     我们把一个 Y 看作是由一个中心点、三个手臂和三个端点构成的。现在,对于平面上的每一个 Y ,我们都给它画出三个有理圆(圆心的两坐标和半径的长度都是有理数),让每个圆都圈住 Y 的其中一个端点,并且不包含 Y 的另外两臂。注意到,平面上的有理点是稠密的,半径的长度也可以任意小,因此这总是能办到的。不过,这些有理圆完全有可能和别的 Y 相交,也有可能和别的有理圆相交。我们甚至不能排除这样的情况:其中一个 Y 的某个有理圆和另一个 Y 的某个有理圆是同一个有理圆!不过,下面我们会给大家证明,三个不相交的 Y 绝不可能拥有同一组有理圆。

    

     如图,假设三个 Y 对应了同一组圆。我们修改每一个 Y 的每一条臂,让它在碰到有理圆后直接连接到这个圆的圆心。现在,把三个圆心染成红色,把三个 Y 的中心点染成蓝色,则这 9 条(修改后的)手臂就连接了所有可能的红蓝点对。然而,前面我们已经说过, K3,3 不可能是一个平面图。因此,这三个 Y 必然会相交。

     由于平面上的有理圆是可数的,因而平面上不相交的 Y 也必然是可数的。

QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
后一篇:Scala很难 >>
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1