玩转内接多边形(一):任意多边形内均存在内接正三角形

    这本电子书的第五章非常牛 B ,里面讲到了一系列与多边形的内接图形有关的定理及其证明。有意思的是,同样是研究多边形的内接图形,当具体的研究对象不同时,证明手段也各有各的精彩,并且十分难得的是,这些证明都极具欣赏价值。读完这些巧妙的证明后,我迫不及待地想与大家分享。这里我们先来热热身,看一看最简单的情况:一个多边形内是否总能内接一个等边三角形。

 
 
 

    答案是肯定的,任意一个多边形内总存在一个内接等边三角形。一个非常直观的证明是,令 P 为多边形边界上的一点, Q 点为多边形上的一个动点。以 PQ 为边作等边三角形,把这个三角形的第三点记作 R 。当 Q 离 P 点充分近的时候, R 显然在多边形内部;当 Q 点运动到离 P 点最远处 Q’ 时,多边形内的任意一点到 P 的距离都比 PQ’ 小,因此此时 R 点只可能在多边形外。但 R 的运动轨迹显然是连续的,因此在运动过程中它一定经过了多边形的边界。此时,我们就找到了多边形边界上的三个点 P 、 Q 、 R ,它们组成了一个等边三角形。

Read more…

什么是算法:如何寻找稳定的婚姻搭配

引言 什么是算法
如何寻找稳定的婚姻搭配

 
    据说,一本书开篇就直言不讳地谈起两性的话题,这本书准能畅销。有幸的是,在众多可以用来引入“算法”的话题中,我最喜欢的那一个还真与两性有那么一些关系。假如你是一个媒人,有若干个单身男子登门求助,还有同样多的单身女子也前来征婚。如果你已经知道这些女孩在每个男人心目中的排名,以及男孩们在每个女孩心中的排名(1),你应该怎样为他们牵线配对呢?
    最好的配对方案当然是,每个人的另一半正好都是自己的“第一选择”。这虽然很完美,但绝大多数情况下都不可能实现。比方说,男 1 号的最爱是女 1 号,而女 1 号的最爱不是男 1 号,这两个人的最佳选择就不可能被同时满足。如果出现了好几个男人的最爱都是同一个女孩儿的情况,这几个男人的首选也不会同时得到满足。当这种最为理想的配对方案无法实现时,怎样的配对方案才能令人满意呢?
    其实,找的对象太完美不见得是个好事儿,和谐才是婚姻的关键。如果男 1 号和女 1 号各自有各自的对象,但男 1 号觉得,比起自己现在的对象,女 1 号更好一些;女 1 号也发现,在自己心目中,男 1 号的排名比现男友更靠前一些。这样一来,这两人就可能会发生外遇,最后扔下各自现在的对象,一起私奔了——因为这个结果对他们两人都更好一些。在一种男女配对的方案中,如果出现了这种情况,我们就说婚姻搭配是不稳定的。作为一个红娘,你深深地知道,对象介绍得不好没有关系,就怕婚姻关系不稳定。给客户牵线配对时,虽然不能让每个人都得到最合适的,但婚姻搭配必须得是稳定的。换句话说,对于每一个人,在他心目中比他当前的伴侣更好的异性,都不会认为他也是一个更好的选择。现在,我们的问题就是:稳定的婚姻搭配总是存在吗?应该怎样寻找出一个稳定的婚姻搭配?

Read more…

也说Pizza问题:分享几个漂亮的证明

    显然,过 Pizza 的圆心作四条直线,把一个周角平分成八等份,则整个 Pizza 饼也被分成了八等份。我们也很容易联想到,如果过圆心外的一点做出四条直线,并且同样满足每两条相邻直线夹 45 度角,那么这八块 Pizza 饼显然是不一样大的。考验你直觉的时候到了:你认为蓝色面积之和与红色面积之和相比,哪个大一些呢?

  

Read more…