H.W.Richmond在1921年的第10期The Mathematical Gazette里提出了这样一个问题：
任意写下一个数，再在它下面写下它的2倍、3倍、4倍、……、9倍。把这些数按位对齐，每一列里恰好有9个数字（前面几行中的首位为空时该位置视作0）。证明，每一列中至少有一个数字0或者数字9。
设我们最初写下的数为S，则这9个数分别为S, 2S, 3S, …, 9S。假如某一列里任一个数字都不等于0或者9，这也就是说该列的所有9个数字都只能取1到8里的数，于是由鸽笼原理，必定存在两个数aS和bS，该位上的数字是相同的。不妨设a>b，于是，在aS-bS中，该位置上的数字必然只能是0或者9（这取决于它前面是否有借位），而aS-bS=(a-b)S显然也在这9行数里面。
题目来源：http://www.cut-the-knot.org/Curriculum/Arithmetic/ZerosAndNines.shtml
今天在回访网站流量来源时看到了一个很牛B的东西，和大家分享一下。
给定一个顶点数为100000的图G，问是否存在Hamilton回路。现在，A宣称自己已经找到了一个Hamilton回路，但B不信，要A证明给他看。你能否想出一个办法使得，A可以让B相信自己有了正确的答案，但B依然不知道答案是什么。这种方法既科学又有趣，整个过程不需要第三者参与，仅仅靠AB两人之间的交流即可。这种方法可以让B有充分的理由相信A找到了Hamilton回路，但能保证B仍然得不到任何与正确答案有关的线索。
首先，A生成一个100000的全排列P，然后用这个排列P把原图G的顶点标号打乱（对标号进行置换），这样就得到了一个同构的图G'。然后A把图G'告诉给B。注意，目前判断两个图是否同构还没有有效的P算法，因此除非A把排列P也告诉了B，否则B不知道G'和G是不是真的同构。接下来B从下面这两个问题中随机抽一个问题让A作答：叫A证明G与G'同构（即叫A给出排列P，确保他没有作假），或者叫A指出G'中的一条Hamilton回路。反复进行“构造G'—抽问”的过程，每次A答对后B都会更加确信A确实找到了原图G的Hamilton回路，来个十几二十次后A作假的嫌疑基本上可以被排除了。这是因为，如果A不知道原图G中的Hamilton回路，这两个问题他是不可能同时答对的，既然B是抽查的，A不可能每次总能答对。同时，除非B同时知道了两个问题的答案，否则B永远不知道原图G的Hamilton回路是什么。仅仅知道G'的Hamilton回路是没有用的，因为此时B连G和G'是否同构都不知道，更别提找出它们之间的对应关系了。
来源：http://www.zju88.cn/cgi-bin/bbstcon?board=Algorithm&file=M.1200769543
据说，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原创
做人要厚道，转贴请注明出处
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