当我们进一步考虑内接菱形时，情况有了一些变化——证明任意多边形内均存在内接菱形没有前几个问题那么容易了。但我们可以轻易证明一个弱化版的命题：任意凸多边形内均存在内接菱形。下面将给出这个命题的两种不同的证明，它们都相当经典。
证明 1 ：考虑凸多边形内的一条水平线段由上至下扫过，这条线段的中点所形成的轨迹就是一条连接凸多边形最顶端与最底端的折线段。类似地，考虑一条从左至右移动的竖直线段，它的中点就构成了从凸多边形最左端到最右端的连线。显然，这两条连线会有一个交点，也就是说我们找到了两条互相垂直且中点重合的线段，它们对应的四个端点显然就是一个菱形的四个顶点。
大家或许知道 Banach-Tarski 悖论——把一个三维球分成有限多份并重新拼成两个和原来一模一样大的球——这个悖论告诉我们利用选择公理我们能够推出看上去多么不合逻辑的东西。今天我听说了另一个类似的悖论叫做 Sierpinski-Mazurkiewicz 悖论，它的结论在直观上同样令人难以接受，并且推导不依赖于选择公理。
Sierpinski-Mazurkiewicz 悖论是说，存在平面上的一个点集 S ，我们能把它划分成两个子集 A 和 B ，使得 A 旋转 1 弧度后与 S 完全重合， B 平移一个单位后也与 S 完全相同。换句话说，存在这么一个点集，我们能把它分成两个与自身一模一样的子集！这听上去实在是不可思议，然而构造却极其简单。
紧接着，我们想问：是否任意一个多边形内都能找到内接矩形呢？有意思的是，答案也是肯定的。但此时，前一节我们用到的两种证明方法现在都派不上用场了，我们需要用到一些全新的手段。下面这个证明真可谓是巧妙到了诡异的地步，真不知是谁想出来的。
对于多边形边界上的任意两点 A(x1, y1) 、 B(x2, y2) ，作出它们在三维空间中所对应的点 ((x1+x2)/2, (y1+y2)/2, √(x1-x2)^2+(y1-y2)^2) 。换句话说，把多边形放在水平面 z=0 上，对于多边形上的每一组无序点对 A 、 B ，在线段 AB 中点的正上方 |AB| 处作一个点。再把这个多边形本身加进去，我们就得到了一个三维空间中的封闭曲面。
可以看到，图中所示的例子中，这个曲面与自身相交了。这就表明，存在多边形边界上的两组点对 A 、 B 和 C 、 D ，它们满足线段 AB 和 CD 的中点重合，并且两线段一样长。这样，四边形 ABCD 就是多边形的一个内接矩形了。下面我们将说明，这个曲面一定会与自身相交。
时常感叹，造物者一定是一个数学家，能把数学之美如此完美地融入自然界。
国外网友制作的这个短片向大家展示了大自然中令人震撼的数学之美，非常漂亮，值得一看：
YouTube 链接：http://www.youtube.com/watch?v=kkGeOWYOFoA
这本电子书的第五章非常牛 B ，里面讲到了一系列与多边形的内接图形有关的定理及其证明。有意思的是，同样是研究多边形的内接图形，当具体的研究对象不同时，证明手段也各有各的精彩，并且十分难得的是，这些证明都极具欣赏价值。读完这些巧妙的证明后，我迫不及待地想与大家分享。这里我们先来热热身，看一看最简单的情况：一个多边形内是否总能内接一个等边三角形。
答案是肯定的，任意一个多边形内总存在一个内接等边三角形。一个非常直观的证明是，令 P 为多边形边界上的一点， Q 点为多边形上的一个动点。以 PQ 为边作等边三角形，把这个三角形的第三点记作 R 。当 Q 离 P 点充分近的时候， R 显然在多边形内部；当 Q 点运动到离 P 点最远处 Q' 时，多边形内的任意一点到 P 的距离都比 PQ' 小，因此此时 R 点只可能在多边形外。但 R 的运动轨迹显然是连续的，因此在运动过程中它一定经过了多边形的边界。此时，我们就找到了多边形边界上的三个点 P 、 Q 、 R ，它们组成了一个等边三角形。
引言 什么是算法
如何寻找稳定的婚姻搭配
据说，一本书开篇就直言不讳地谈起两性的话题，这本书准能畅销。有幸的是，在众多可以用来引入“算法”的话题中，我最喜欢的那一个还真与两性有那么一些关系。假如你是一个媒人，有若干个单身男子登门求助，还有同样多的单身女子也前来征婚。如果你已经知道这些女孩在每个男人心目中的排名，以及男孩们在每个女孩心中的排名(1)，你应该怎样为他们牵线配对呢？
最好的配对方案当然是，每个人的另一半正好都是自己的“第一选择”。这虽然很完美，但绝大多数情况下都不可能实现。比方说，男 1 号的最爱是女 1 号，而女 1 号的最爱不是男 1 号，这两个人的最佳选择就不可能被同时满足。如果出现了好几个男人的最爱都是同一个女孩儿的情况，这几个男人的首选也不会同时得到满足。当这种最为理想的配对方案无法实现时，怎样的配对方案才能令人满意呢？
其实，找的对象太完美不见得是个好事儿，和谐才是婚姻的关键。如果男 1 号和女 1 号各自有各自的对象，但男 1 号觉得，比起自己现在的对象，女 1 号更好一些；女 1 号也发现，在自己心目中，男 1 号的排名比现男友更靠前一些。这样一来，这两人就可能会发生外遇，最后扔下各自现在的对象，一起私奔了——因为这个结果对他们两人都更好一些。在一种男女配对的方案中，如果出现了这种情况，我们就说婚姻搭配是不稳定的。作为一个红娘，你深深地知道，对象介绍得不好没有关系，就怕婚姻关系不稳定。给客户牵线配对时，虽然不能让每个人都得到最合适的，但婚姻搭配必须得是稳定的。换句话说，对于每一个人，在他心目中比他当前的伴侣更好的异性，都不会认为他也是一个更好的选择。现在，我们的问题就是：稳定的婚姻搭配总是存在吗？应该怎样寻找出一个稳定的婚姻搭配？
显然，过 Pizza 的圆心作四条直线，把一个周角平分成八等份，则整个 Pizza 饼也被分成了八等份。我们也很容易联想到，如果过圆心外的一点做出四条直线，并且同样满足每两条相邻直线夹 45 度角，那么这八块 Pizza 饼显然是不一样大的。考验你直觉的时候到了：你认为蓝色面积之和与红色面积之和相比，哪个大一些呢？
早上好！今天是 3 月 14 日，一年一度的圆周率日。为了和大家庆祝这个日子，我下载了一个 JavaScript 俄罗斯方块游戏 Js Tetris 的源代码，并且小小地修改了一下。那 7 种四联骨牌已经不复存在了，你将看到圆周率中的数字一个接一个地依次落下。这恐怕有希望成为史上最变态的俄罗斯方块了吧。
游戏改造完毕后，我自己居然沉迷了好久。把积木换成数字后游戏变得不是一般的困难，有很多小技巧有待大家慢慢去摸索。我个人的最好成绩是第 32 位。你呢？
Matrix67 |
2010-03-30 22:48 | 
