据说，17世纪时，大数学家Fermat曾向意大利的物理学家和数学家Torricelli提出过这样一个问题：在已知锐角三角形ABC内求一点P，使得PA+PB+PC最小。Torricelli证明了，这个点是存在的，且∠APB=∠BPC=∠CPA=120°。他还指出，若分别以AB、BC、AC为边向外作等边三角形ABC'、BCA'、ACB'，则AA'、BB'、CC'三线共点，交点即为所求的点P。这个点后来被称为Fermat点，通常记作F。这个定理有很多种证明，这里我们先介绍一种比较简单的证明方法。
  
    考虑三角形内任一点P，将△ABP绕点B旋转60°得到△C'BP'。显然，△BPP'是等边三角形，PB=P'P；同时，PA也转移到了C'P'，于是PA+PB+PC=C'P'+P'P+PC，P点到三个顶点的距离和转换为了一条从C'到C的折线段。注意C'的位置是和P无关的（C'AB始终成等边三角形），因此折线段C'P'PC的长度的最小值即为CC'的长度。这个最小值是可以达到的，即P和P'可以恰好落在CC'上。如果点P在CC'上且∠APB=120°，则旋转之后∠C'P'B也等于120°，正好与∠BP'P组成一个平角，于是C'、P'、P、C四个点都在一条直线上，C'P'+P'P+PC达到最小。这个点就是我们要求的Fermat点F。注意这个点F满足以下两条性质：在等边三角形顶点C'与原三角形顶点C的连线上，对AB张角为120°。由对称性，∠BFC和∠CFA也都等于120°，且点F同时也在BB'和CC'上。这也说明了为什么AA'、BB'、CC'三线共点。

  
    这个题目真正有趣的地方在于，它有一个非常简单的物理解法。我们可以用Fermat原理来说明，为什么Fermat点F满足∠AFB=∠BFC=∠CFA=120°。假设我们固定AF的长度，那么F点的轨迹是一个以A为圆心的圆。当BF+FC达到最小时，路径B->F->C必然符合光的传播性质，反射点F满足入射角等于反射角，也就是说AF的延长线（即法线）平分∠BFC。同样地，固定BF的长度，则要想AF+FC最小，BF的延长线必须平分∠AFC。类似地，还有CF的延长线平分∠AFB。只有上述三个角平分关系同时成立时，AF+BF+CF才能达到最小，否则我总可以调整它们间的角度使其变得更优。再加上对顶角相等，我们立即看到，右图中所有这6个角全都等于60°。这样，我们就得到了先前证明的结论：存在点F使得它到A、B、C的距离和最小，此时∠AFB=∠BFC=∠CFA=120°。

    上面的这个问题有一个扩展，叫做广义Fermat点问题。考虑平面上n个点A1, A2, …, An，每个点都有一个权值W1, W2, …, Wn，广义Fermat点是这样的一个点P，它使得ΣPAi*Wi达到最小。广义Fermat点更具一般性，有非常高的实用价值。比如，城区里有n个住宅区，第i个住宅区里有Wi个人，问邮局设在哪里可以使所有人到邮局的总路程最短。目前，广义Fermat点问题还没有一般结论，但它可以通过力学模拟法完美解决。我们可以用力学模拟法说明，这个广义Fermat点是唯一存在的。事实上，我们可以建立力学模型找出这个点来。
  
    取一块木板，在木板上标出n个点所在的位置，各钻一个小孔。再找n条同样长的细绳，把所有绳子的其中一头扎结于一点；第i根绳子从木板上点Ai处的小孔穿过去，绳子另一头系上一个重Wi的砝码。所有准备工作就绪后，把木板水平悬在空中，此力学系统平衡后绳结所在的位置即为所求的点P。这是为什么呢？
    道理很简单。重物悬挂的位置有尽可能往低处走的趋向，此时重力势能转化为动能；当整个系统静止时，势能应该达到最小。假如我们用Hi来表示静止时第i个砝码离地面的距离，那么此时ΣHi*Wi达到最小。由于木板与地板之间的距离一定，因此ΣLi*Wi达到最大。又由于绳长为定值，所以ΣPAi*Wi达到最小。

Matrix67原创
做人要厚道，转贴请注明出处

    前两篇文章中，我们提到了两个用杠杆原理解决数学问题的例子。这篇文章将从另一个物理领域出发，探索光学的一个重要原理与几何极值问题的关系。
    物理学的美不仅仅表现在简洁的公式上。我们还惊奇地发现，很多物理现象都是按照使某个变量达到极值的方式发生。一个典型的例子就是Fermat原理，它指出了光的传播路径的一个重要规律：光总是沿着所花时间最短的路径传播。这里我们将简单介绍一下Fermat原理，该系列后面的文章里将会用到这一原理。
    Fermat原理俗称“最快到达原理”、“最小时间原理”，意思是光线传播的路径总是满足这样一个规律：它总能使光在最短的时间内到达目的地。这个原理完美地统一了直线传播定律、反射定律和Snell定律，解释了为什么光线总是沿直线传播，为什么入射角等于反射角，以及光线在不同介质间传播为什么会发生折射现象。
    在Ted Chiang的著名科幻小说The Story of Your Life里有这样一段形象的描述：

    “好，这是一条光线从空气射进水中所走的路线。在碰到水面前，光线沿着直线前进；水有不同的折射率，所以光改变了前进方向。你以前听过这个，对吗？”
    我点点头，“当然。”
    “现在关于光所走路线有个有趣的性质。这条路线是这两点之间可能的最快的路线。”
    “又来了？”
    “想象一下，光线沿着这条路线前进。”他在图解中加了条虚线。
    “这条假想中的路线比光实际走的路线要短。但是光在水中前进的速度比在空气中小，而这条假想的路线的很大一部分是在水中的，所以光沿着这条假想的路线所花的时间要比沿着实际路线要长。”
    “好，我明白了。”
    “现在想象一下，假设光沿和另一条路线前进。”他画了第二条虚线。
    “这条路线减少了在水中的比例，但总长增加了。光沿着这条假想的路线所花的时间也要比沿着实际路线要长。”
    Gary放下粉笔，用蘸着粉笔屑的手指指着黑板上的图解，“任何假想的路线都比实际的要花更多的时间。换一句话说，光线走的路线是最有可能走得走快的一条。这就是Fermat定理的最小时间原理。”

    你发现Fermat原理有什么奇怪的地方了吗？你是不是感觉Fermat原理很诡异，但自己也说不清楚到底是为什么诡异？仔细想想你会发现，“最快到达”这种原理显然是不符合我们的行为方式的：假如我是光，我的传播规律是“最快到达”，但此时我要传播到哪里还不知道呢。Ted Chiang的小说对此也做出了详细的描述：

    “然而我仍要问你关于Fermat定理的东西。它的一些东西让我感到奇怪，但我不能正确指出那是什么。它只是不像是物理法则。”
     Gary的眼睛闪了一下，“我打赌我知道你想谈什么，”他用筷子把锅贴夹成两半，“你习惯于用起因和结果来思考折射：光照到水面上是起因，方向的变化是结果。但Fermat定理听上去很古怪，因为它以目的的形式来描述光的行为。它就像是光线的指挥官，‘你应该将抵达目的的时间最小化或最大化。’”
    我想了一下，“继续说。”
    “这是物理法则的一个老问题。人们在17世纪Fermat定理第一次成形时就一直在谈论它。Planck写了好几卷。本质是，普通的物理法则的表述是具有因果关系的，而像Fermat定理的可变法则具有目的性，几乎是目的论。”
    “嗯，这样解释道挺有趣。让我想一下。”我拿起一支标签笔，在餐巾纸上画了幅图解，就是Gary在我的黑板上画的那幅，“好，”我想我很大声地说道，“那么让我们假设光的目的是要沿着最快的路线前进。这样的话，光如何走呢？”
    “好吧，假若按人类行为学来说，光得检验每条可能的路线并计算每条得花多少时间。”他从盘子里戳起最后一块锅贴。
    “那样做的话，”我继续道，“光线得知道目的在哪儿。假如目的地在某某其他地方，最快的路线就会不同。”
    Gary再次点点头，“完全正确。‘最快的路线’的概念是无意义的，除非有特定的目的地。计算沿着一条假想的路线需多长时间也需要关于在这条路线上有什么东西的信息，比如水面在哪？”
    我继续看着纸巾上的图解，“在光开始移动前，它得事先知道所有这一切，对吗？”
    “这样说来，”Gary说，“光线不能沿着老路前进，然后再在后来返回。因为引起这样行为的路线不是最快的。在一开始光就已经做好了全部的计算。”
    我心中暗想，在光线能够选择它移动的方向前，它已经知道它最终会在那里结束。我知道这让我想起了什么，我抬起头看着Gary，“这让我困扰。”

  
    上面的论述似乎很抽象。我们来看一个实际的数学问题。这个问题有点怪，和其它的问题很不一样。给出一个点A，给出两个圆O1、O2，再给定O1上的一点B，问O2上是否存在一点C，使得B点的位置恰好能让AB+BC达到最小，也即对于O1上异于B的任一点B'都有AB'+B'C > AB+BC。你一时间可能找不到这个点C，这很正常，但光可以立即找到这个点C。因为从Fermat原理的角度看，光的思维方式是“逆向”的，这个别扭的题目正好顺应了它的思维方式。只要沿AB发射一条光线，在圆O1表面上发生反射后的光线与O2的交点即为点C。因为，A->B->C这条光路符合光的传播性质，这条路径是所有经过O1上一点到C的路径中最短的一条，其它所有的B'都会使光程增加。事实上，光就有这种神奇的本领：不管之前有过多少反射点，有过多少折射点，这条光线今后传播到的每一个点都满足这种无比别扭的“以它为终点则前面的定点均已达到最优”的性质。对于光来说，这是顺理成章的事；但从我们的角度来看，还没到目的地便能确保路径最优是很不可思议的。我们会习惯性地认为，光从A点出发往B走之前必须得先知道它的终点是C，然后才会知道B可以使光程最短，因此它才会往B走。这是明显有悖于我们熟知的因果关系的。或许说，这个世界本没有什么因果关系，仅仅是因为人类的思维被禁锢在了因果链式思维中？

    接下来，我们举两个火星例子。两个都是经典的小学奥赛题。
  
    问题1：给定直线l同侧的两点A和B，在直线上找一点C使得折线ACB最短。
    问题2：角ABC内有一点P，请在AB上找一点M，BC上找一点N，使得三角形PMN的周长最短。
    类似的问题还有很多。很多这类几何极值问题都和Fermat原理有直接

    Cantor对集合的一些著名的研究让我们更加清楚地认识了无穷这玩意儿。Cantor发现，无穷集合之间也有大小关系，他把这种大小关系叫做集合的势(cardinality)。正整数和正偶数都有无穷多个，但到底谁要多一些呢？我们认为，正整数和正偶数一样多，因为我们可以在它们之间建立起一一对应的关系（乘2除2），因此有多少个正整数就有多少个正偶数，反过来有多少个正偶数我就能找出多少个正整数。于是我们说，正整数集和正偶数集是等势的。
    再来想一个问题，自然数和所有整数哪个多哪个少？答案还是一样多。重新排列一下所有整数，你会看到自然数和整数之间也有一一对应的关系，它们的个数一样多，两个集合也是等势的：

自然数：0,  1,  2,  3,  4,  5,  6,  7,  8, …
   整数：0, -1,  1, -2,  2, -3,  3, -4,  4, …

    Cantor还发现，有理数集与自然数集也是等势的，也就是说有理数和自然数一样多！这个证明方法可谓是数学史上真正的经典：把所有有理数写成最简分数的形式，根据分子和分母的值把它们排列成二维的阵列，然后从1/1出发沿对角线方向蛇形遍历所有的数。第i个遍历到的数与自然数i对应，正有理数集与正整数集也就有了一一对应的关系。注意这里仅仅是正有理数，不过没啥，用刚才证明整数集与自然数集等势的方法，我们也可以把正有理数扩展到全体有理数。
      

    事实上，对于任何一个集合S，如果你能找出一种方法把集合里的所有元素按顺序一个不漏地罗列出来，写成a1, a2, a3, a4, … 的形式，那么这个集合就是和自然数集等势的，因为序列的下标和自然数集就已经构成了一个一一对应的关系。我们把所有与自然数集等势的集合叫做可数集(countable set)，因为它们是可以数出来的。
    并不是所有集合都是可数的。Cantor证明了，实数区间[0,1]是不可数的集合，它的势比自然数集大。你找不出什么方法能把0到1之间的所有实数一个不漏地排列出来。这个证明方法很巧妙，假设你把实数区间[0,1]里的所有数按照某种顺序排列起来，那么我总能找到至少一个0到1之间的实数不在你的列表里。把你的列表上的数全写成0到1之间的小数：

a1 = 0.0147574628…
a2 = 0.3793817237…
a3 = 0.2323232323…
a4 = 0.0004838211…
a5 = 0.9489129145…
………

    那么我就构造这么一个小数，小数点后第一位不等于a1的第一位，小数点后第二位不等于a2的第二位，总之小数点后第i位不等于ai的第i位。这个数属于实数区间[0,1]，但它显然不在你的列表里。这样，我就证明了实数区间是不可数的。

    最近，Matthew H. Baker找到了证明实数区间是不可数集的一种新方法。这种方法同原来的方法完全不同。新的证明方法从一个博弈游戏出发，在两个不同的数学领域间建立起了联系，非常具有启发性。
    A和B两个人在实数区间[0,1]上玩一个游戏。首先，A在(0,1)之间选一个数a1，然后B在(a1,1)里选一个数b1；接着，A在(a1,b1)之间选一个数a2，然后B在(a2,b1)里选一个数b2……总之，以后A和B轮流取数，选的那个数必须位于前面两次选的数之间。可以看到，序列a1, a2, a3, …是一个单增的有界序列，因此游戏无限进行下去，数列{an}最终会收敛到某一个实数c。游戏进行前，A和B约定一个[0,1]的子集S，规定如果最后c∈S，则A胜，否则B胜。
    Baker发现，如果S集为可数集的话，B肯定有必胜策略。如果S集可数，那么B就可以把S集里的数排列成一个序列s1, s2, s3, … 。B的目标就是让序列{an}的极限不等于S集里的任一个数。考虑B的这样一个游戏策略：当B第i次选数时，如果选si合法，那么就选它（这样序列{an}就不能收敛到它了）；否则如果这一步选si不合法，那就随便选一个合法的数（此时序列{an}已经不可能收敛到si了）。这种策略就可以保证A选出的数列的极限不是S集里的任一个数。
    有趣的事情来了。假如A和B约定好的S集就是整个实数区间[0,1]，那么B显然不可能获胜；但如果[0,1]是可数集的话，B是有必胜策略的。于是我们就知道了，[0,1]是不可数集。

消息来源：http://blog.sciencenews.org/mathtrek/2008/01/small_infinity_big_infinity.html
查看更多：https://www.math.gatech.edu/~mbaker/pdf/realgame.pdf

    SETI@home可以在杂乱的射电数据中搜寻独特的讯号，你能在大街上的嘈杂声中清晰分辨出一个尖细的女声大叫“亚美蝶”。这些现象都表明，有时对集合里的所有元素进行整体考察可以很快找出我们所要找的个体。去年我们搞合唱比赛时，我又想到了一个绝佳的例子：你可以在合唱声中清楚地听到是否有人跑调。考虑这样一个问题，假如合唱团里有一个人唱歌始终走调，但我听不出来是谁走调，只能听出当前正在唱歌的人中是否有唱走调了的人。那么，我如何才能迅速地揪出那个唱走调的人？利用经典二分法，我们可以在log2(n)次合唱后找出唱走调了的人。每一次，我都把剩下的人平均分成两组，然后选其中一组来合唱：如果听不到走调的声音，这一组的人就全部过关；如果听到有人走调，那另一组里的人都可以被排除了。递归地对剩下的组进行同样的操作，log2(n)次操作后必定可以找出那个唱歌走调的人。
    现在的问题变得有些麻烦了。假如我们知道合唱队里有一个人唱歌爱跑调，但他不是总会跑调。具体地说，他只有1/2的概率唱错，但其余1/2的时间里他却唱得很准。现在，传统的二分法不再适用了，因为没有走调声已经不能起到排除的作用了。你能想出多少种可行的算法来找出那个人？下面提出一些可行的方法，你认为哪种方法更好？你能求出这些算法所需要的检测次数的期望值各是多少吗？

    1. 不断地随机生成一个大小为n/2的子集并对其进行检测，直到某次不能通过检测为止，然后递归地对其进行操作。
    2. 所选的子集大小为n/2是最优的吗？把上面这种方法的n/2改成n/a，常数a的最优值是多少？
    3. 检测次数的期望值还可以更小吗？我们想到，每次都重新生成一个新的集合其实并不科学，新集合本身是否包含老鼠屎也是得碰碰运气的。因此，对方法1的一个合理改进是：把集合平均划分为两个部分，交替对它们进行检测直到某次检测没通过为止，然后对该组递归操作下去。这种方法真的比前两种好吗？它所需要的期望次数是多少？
    4. 尝试对方法3进行改进。如果把集合平均划分成3份并循环进行检测，效果会不会更好一些？

    1. 选取的子集有1/2的概率覆盖了我们要找的那个人，子集里有他而他这次恰好又唱走调了则有1/4的概率。因此，不管规模有多大，平均需要4次才能把规模缩小一半。因此，检测次数的期望值为4*log2(n)。为了方便比较期望值的大小，后面的答案我们一律表示成一个常数乘以log2(n)的形式。
    2. 类似地，平均需要2a次检测才能把规模缩小到原来的1/a，因此总共花费的检测次数为2a*log2(n)/log2(a)。对函数求导，可得当a为e时函数值达到最小。此时的检测次数期望值为2e*log2(n)/log2(e)≈3.7683 * log2(n)。
    3. 这个就经典了。设方法3里把规模缩小一半所需要的检测的期望次数为m，下面我们来看m应该等于多少。把n个人平均分成两组，我们要找的老鼠屎有1/2的概率在第一组，有1/2的概率在第二组。因此，第一次就测出问题来有1/4的可能，第二次就测出问题也有1/4的可能。对于剩下的1/2种情况，局面变得又和最开始一样，只是平均需要的检测次数比原来多了2。根据期望值的定义，有m=(1/4)*1 + (1/4)*2 + (1/2)*(m+2)，解得m=3.5。总的检测次数就是3.5 * log2(n)，它比前面两种方法都要好。你可能不同意上面求m的方法。这没啥，如果你不断对m进行迭代，你会发现展开出来的式子就是最标准的期望值定义。
    4. 类似地，有m=(1/6)*1 + (1/6)*2 + (1/6)*3 + (1/2)*(m+3)，解得m=5。于是，把规模缩小到原来的1/3平均需要5次检测，总的检测次数为5*log2(n)/log2(3)≈3.1546 * log2(n)。

题目来源：IBM Ponder This Dec07
原文还从熵的角度探寻了问题的最优算法，感兴趣的读者可以去看一看

    在1717年，法国流行这样一个赌博游戏：连续抛掷一个骰子四次，赌是否会出现至少一个1点。经过试验，赌徒Chevalier de Méré发现至少出现一个1点比不出现的几率似乎要稍微大一些。他总是赌“会出现”，每次算下来他总是赢。在这个赌博游戏的一个“加强版”中，赌徒们需要猜测，连续抛掷两个骰子24次，是否会出现至少一对1点。Chevalier de Méré想，两个骰子同时掷出1点的几率显然是单个骰子掷出1点的几率的1/6，为了补偿几率的减小则必须要抛掷骰子24次。因此，两个赌博游戏换汤不换药，赌“出现”获胜的几率应该是一样的。但奇怪的是，他每次都赌会出现一对1点，结果几乎每次的最终结果都是输。他感到百思不得其解，于是向数学家Pascal寻求一个合理的解释。Pascal与大数学家Fermat用信件进行了交流，最终提出了概率问题的若干原理，创立了概率学。
    我们可以简单算一下，虽然直观感觉两个问题的概率应该相等，但实际上前者发生的概率大于0.5，后者发生的概率小于0.5，虽然两者相差并不多。

    问题1：连续抛掷一个骰子4次，至少出现一个1点的概率是多少？
    解答：在所有6^4种可能的情况中，一个1点都没有的情况有5^4种，因此至少出现一个1点的概率是(6^4-5^4)/6^4≈0.5177

    问题2：连续抛掷两个骰子24次，至少出现一对1点的概率是多少？
    解答：在所有36^24种可能的情况中，一对1点都没有的情况有35^24种，因此至少出现一对1点的概率是(36^24-35^24)/36^24≈0.4914

    谁能用一句话解释清楚，为什么赌徒Chevalier de Méré的直觉是错误的？不用Ctrl+A了，这次没有藏啥东西。

参考资料：http://www.cut-the-knot.org/Probability/ChevalierDeMere.shtml