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

标签: 趣题 Brain Storm 图论 集合 无穷 | 发表时间:2011-11-09 13:26 | 作者:Matrix67 Sosi
出处:http://www.matrix67.com/blog

    这篇文章收录了 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 也必然是可数的。

 
    值得一提的是,我们这里证明的是一个相当强的结论:对于所有含有交叉点或者分岔点的图形,它在平面上都只能画出可数个(如果不允许相交的话)。这不但可以直接推出平面上不相交的 8 字形是可数的,事实上不相交的 4 或者 6 或者 9 也都只能是可数的。

相关 [经典 证明 平面] 推荐:

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

- Sosi - Matrix67: My Blog
    这篇文章收录了 Which Way Did the Bicycle Go 趣题集中一个非常有趣的问题:是否有可能在平面上画不可数个不相交的 8. 对于任意一个 8 字形,在两个洞里各取一个有理点 P 、 Q (由于平面上的有理点是稠密的,这是总能办到的),则称这个 8 字形圈住了有理点对 (P, Q).

经典证明:Conway的士兵

- 欲望道人 - Matrix67: My Blog
    今天听说了 Conway's Soldiers ,这是 Conway 大牛在 1961 年提出的一个数学谜题(似乎 Conway 的出镜率也太高了),我觉得非常有意思,在这里跟大家介绍一下. 内容基本上来自于 Wikipedia 的相关页面.     假设有一个无限大的棋盘. 棋盘上可以放置一些象征着士兵的棋子.

经典证明:1+2+3+...+(n-1) = C(n,2)

- hhx - Matrix67: My Blog
来源:MathOverflow.

经典证明:等边三角形内一点到各顶点的距离长可构成一个三角形

- Andy - Matrix67: My Blog
    这是初中平面几何的一个经典问题:等边三角形 ABC 内有任意一点 P,求证 PA 、 PB 、 PC 的长度一定能构成一个三角形.     这里给出两种证明方法. 传统的证明方法是,把 △CPA 绕着点 C 逆时针旋转 60 度,从而旋转后的 CA 将会和 CB 重合,同时 P 点落在了 P' 的位置.

证明题

- Kyle - 《槽边往事》---比特海日志
(图库流量超标,欢迎支持:点击注册Yupoo). 是安于现在的生活并且学着享受庸常,还是甘冒下坠的风险振翅飞往远方. 这是我最近在《树洞》里经常看到的问题. 说实话,我也觉得非常惊奇,竟然有那么多人觉得现实在一点点埋葬自己的梦想,同时又没有足够的勇气跨出一步. 每次说到看不到的山那头,海的那一端,总有无数颗小心在各个地方黯然破碎.

证明0.999...=1

- Zane - Solidot
数学中最妙不可言的部分是其简洁优美的陈述,它们常常会让人惊呼“这不是真的”,例如e^(iπ)+1=0. 在《蒙大拿州数学爱好者》杂志上,两位研究人员用了28页探讨了一个已经被深入讨论过的、但常常让学生感到困惑的问题:0.999...等于1(PDF). 众所周知,循环小数0.999…等于实数1,相关的证明很多,例如:设a= 0.999...,两边同乘以10得到10a=9.99...,等式两边再减去a得到10a-a=9,即9a=9,a=1;另一个证明,1/9 = 0.111...,9 x (1/9) = 0.999...于是1 = 0.999....

经典论文 — REST

- ripwu - kernelchina
牛人Roy Thomas Fielding的博士论文,此处可以访问到英文版,中文版可以google一下. HTTP1.0,1.1版本以及URI规范的主要作者,Apache的co-founder. 在写这篇论文之前已经很牛了,笔者不明白的是这种档次牛人还要读博士,文凭有这么重要吗. 文中没有任何令人眼花的数学公式和统计图表,实际上是一篇描述URI,HTTP设计经验教训总结的文章.

经典空姐照

- renwen - 东西

jstl标签经典

- - CSDN博客推荐文章
库 :Core(核心库). 描述 : 标签是一个最常用的标签,用于在   JSP   中显示数据.  它的作用是用来替代通过 JSP 内   置对象 out 或者 <%=%> 标签来输出对象的值. 用于指定在使用  标记输出诸如“ < ”、“ > ”、“ ’ ”、“” ”和“ & ”之类的字符(在  HTML  和  XML  中具有特殊意义)时是否应该进行转义.

sql经典语句

- - 数据库 - ITeye博客
3、说明:备份sql server. --- 创建 备份数据的 device. table tab_new like tab_old (使用旧表创建新表). DB2中列加上后数据类型也不能改变,唯一能改变的是增加. 注:索引是不可更改的,想更改必须删除重新建. 10、说明:几个简单的基本的sql语句.