鸽笼原理英文是Pigeonhole Principle。但是它有很多中文名字，比如鸽巢原理，抽屉原理，鞋盒原理等等。它指的是如下一个定理：
如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或更多的物体。
我们来证明一下(这不是显然么！)。用反证法。假设每个盒子中都至多有一个物体，那么物体的总数至多是n。这与共有n+1个物体矛盾。所以定理成立。
别看这个定理很简单，用它却可以巧妙的解决很多问题，一个简单的例子就是13个人中至少有两个人的生日在同一个月份里。下面我们来考虑一些更具挑战性的例子：
1 证明给定m个整数a1,a2,…,am，存在整数k和l，0<=k<l<=m，使得a(k+!)+a(k+2)+…+a(l)能够被m整除。
证明：对于m个和 a1 , a1+a2 , a1+a2+a3 , … , a1+a2+…+am 。如果这些和当中的任意一个可以被m整除，问题便得证了。假设这m个和都不整除m，那么它们除以m的余数可能是1,2,…,m-1。由于存在m个数，而余数只有m-1种，所以必然有两个和除以m有相同的余数(鸽笼原理)。因此存在整数k和l，0<=k<l<=m，使得a1+a2+…+ak=bm+r , a1+a2+…+al=cm+r，两式相减，得到a(k+!)+a(k+2)+…+a(l)=(c-b)m，从而命题得证。
2 距离全国大学生数学建模竞赛还有11周时间。我决定每天至少做一道建模题，但为了不让自己陷入题海战略，给自己一些总结和思考的时间，我还是决定每周不能做题超过12道。证明存在连续的若干天，期间我恰好做了21道题。 Read the rest of this entry »

还记得我写过的那篇用概率计算π的文章么？今天又学到了点东西(From Prof.Xiang)。原来用概率模拟来计算一些问题，这种方法是有名字的。名字就是本文标题。以下内容摘自百度百科：

——————————————————————————————————————————–

蒙特卡罗(Monte Carlo)方法，或称计算机随机模拟方法，是一种基于”随机数”的计算方法。这一方法源于美国在第一次世界大战进研制原子弹的”曼哈顿计划”。该计划的主持人之一、数学家冯?诺伊曼用驰名世界的赌城-摩纳哥的Monte Carlo-来命名这种方法，为它蒙上了一层神秘色彩。

Monte Carlo方法的基本思想很早以前就被人们所发现和利用。早在17世纪，人们就知道用事件发生的”频率”来决定事件的”概率”。19世纪人们用投针试验的方法来决定圆周率π。本世纪40年代电子计算机的出现，特别是近年来高速电子计算机的出现，使得用数学方法在计算机上大量、快速地模拟这样的试验成为可能。

考虑平面上的一个边长为1的正方形及其内部的一个形状不规则的”图形”，如何求出这个”图形”的面积呢？Monte Carlo方法是这样一种”随机化”的方法：向该正方形”随机地”投掷N个点落于”图形”内，则该”图形”的面积近似为M/N。

可用民意测验来作一个不严格的比喻。民意测验的人不是征询每一个登记选民的意见，而是通过对选民进行小规模的抽样调查来确定可能的优胜者。其基本思想是一样的。

科技计算中的问题比这要复杂得多。比如金融衍生产品（期权、期货、掉期等）的定价及交易风险估算，问题的维数（即变量的个数）可能高达数百甚至数千。对这类问题，难度随维数的增加呈指数增长，这就是所谓的”维数的灾难”(Course Dimensionality)，传统的数值方法难以对付（即使使用速度最快的计算机）。Monte Carlo方法能很好地用来对付维数的灾难，因为该方法的计算复杂性不再依赖于维数。以前那些本来是无法计算的问题现在也能够计算量。为提高方法的效率，科学家们提出了许多所谓的”方差缩减”技巧。

另一类形式与Monte Carlo方法相似，但理论基础不同的方法-”拟蒙特卡罗方法”(Quasi-Monte Carlo方法)-近年来也获得迅速发展。我国数学家华罗庚、王元提出的”华-王”方法即是其中的一例。这种方法的基本思想是”用确定性的超均匀分布序列(数学上称为Low Discrepancy Sequences)代替Monte Carlo方法中的随机数序列。对某些问题该方法的实际速度一般可比Monte Carlo方法提高数百倍，并可计算精确度。

——————————————————————————————————————————–

下面我来举几个具体例子：
1 还是求π
这次的方法要简单一点，不用绕那么多弯子。在[0,1]×[0,1]中任取点，该点可能落在单位圆内的概率为圆的面积比上整个矩形的面积。我们知道这个比值是π/4。那么，只要这个概率求出来了，再乘以4就是π。在用计算机模拟的时候，限制条件用x^2+y^2<1。这里究竟要不要取等号是没有关系的。因为面是由无数条线组成。一条线的包括与否不会影响到整体效果。
我用matlab模拟，做了一百万次(即共取1000000个点)，结果为3.1403。

2 求定积分
比如y=x^2(对x)从0积到1。结果就是下图红色部分的面积：

注意到函数在(1,1)点的取值为1，所以整个红色区域在一个面积为1的正方形里面。所以所求区域的面积即为 在正方形区域内任取点，点落在所求区域的概率。这个限制条件是y<x^2。
我用matlab模拟，做了一百万次(即共取1000000个点)，结果为0.3328。
再比如求重积分

，其中D={(x,y)|x^2+y^2<=1}

函数z=sin(x+y)/(x+y)的图像大致如下：

这个积分代表函数曲面与平面z=0和柱面x^2+y^2=1所围成的体积。所以我们要求的概率就是： Read the rest of this entry »

五个商人，带着一个宠物猴，一起买了一堆西瓜。但是暮色已晚，他们决定第二天把西瓜平均分成五份，每人一份。夜里，一个商人先醒了，他看了看地上的西瓜，想：我先给它分好吧。于是把西瓜平均分成五份，但不巧剩了一个。于是给猴吃了。他自己拿走了五份中的一份，又去zZZ…了。过一会又一个商人醒了，他一看：咦？地上怎么是四堆西瓜？于是他把这四堆西瓜放到一起，又平均分成了五份。不巧，又剩了一个。于是给猴吃了。他自己拿走了五份中的一份，又去zZZ…了。过会，第三个商人又醒了，于是重复了第二个商人的行为，恰好还是剩一个。又给猴吃了……就这样，5个商人都这样做了一次。第二天早晨，他们一起把地上的四堆西瓜又重新分成了5份。恰好还是剩一个，又给猴吃了(看来此猴已经快撑死了-_-!)，每个人拿走一份。问：最开始这堆西瓜最少有多少个？
解：首先，我们假设这堆西瓜有a0个。那么，第一个人拿走一堆后这堆西瓜剩下a1=(a0-1)*(4/5)个(注意猴子吃了一个)。第二个 Read the rest of this entry »

一个集合{1,2}可以看作是无序对，因为{1,2}={2,1}。有时候我们需要另外一个东西<1,2>，使得<1,2>≠<2,1>，这个东西就叫做有序对。更一般的说，有序对就是指这样一个集合，如果<x,y>=<u,v>，那么x=u && y=v。如果用集合定义有序对使它满足以上的性质呢？我们来尝试一下：
如果定义<x,y>={x,y}，这显然不行。如果定义<x,y>={x,{y}}呢？由于<{Ø},{Ø}>=<{{Ø}},Ø>，这样定义也不行。
第一个成功的定义的是1914年Norbert Wiener给出的。它定义：<x,y>={{{x},Ø},{{y}}}。这个看起来很繁琐。一个形式上比较简单，也是目前共用的定义是Kuratowski在1921年给出的：<x,y>={{x},{x,y}}。下面我们来证明这个定义的合理性，也即：<x,y>=<u,v> iff x=u && y=v
证明：充分性显然。下证必要性。假设<x,y>=<u,v>，那么{{x},{x,y}}={{u},{u,v}}。由此我们可以得出{x}∈{{u},{u,v}}和{x,y}∈{{u},{u,v}}。从第一个关系得到{x}={u}或者{x}={u,v}。类似得，从第二个关系我们可以得知{x,y}={u}或者{x,y}={u,v}。首先假设{x}={u,v}成立，那么x=u=y=v，结论成立。再假设{x}={u}。如果第二个关系中{x,y}={u}，又回到了x=u=y=v的情况。如果第二个关系中{x,y}={u,v}，那么由{x}={u}可知,{y}={v}。因为所有的情况我们都考虑了，所以结论成立。
当得到了有序对的严格定义后，有些读者也许会很自然的想到，能不能把它一般化，如此定义n个元素的有序组，即<x1,x2,…,xn>={{x1},{x1,x2},…,{x1,x2,…,xn}}。 Read the rest of this entry »

在图书馆里面看到了一本很有意思的书《数学的奥妙》，作者是伊库纳契夫【俄】。它是一本数学科普书，里面有很多趣味的数序题和游戏。给大家推荐一下。我把其中的一些有意思的题写在这里（其实是前几页的，因为我还没看完）：
[1]分子比分母小的分数，能和分子比分母大的分数相等么？
[2]每天中午，轮船由法国的哈弗尔港启航，经由大西洋驶往纽约。同一时刻，同一家公司的轮船从纽约出发驶向哈弗尔港。两艘船的航行日期都需要7日。请问：从哈弗尔经纽约的轮船在抵达纽约时，共和几艘同一家公司反方向的轮船相会？
[3]有位农妇提一篮苹果到市场去卖，第一个客人买走全部苹果的一半加上1/2个，第二个客人买走剩下苹果的一半再加上1/2个，第三个客人再买走剩下的一半又1/2个……第六个客人也买了剩下苹果的一半加1/2个，这时农妇的苹果刚好卖完，而这6个客人所买的苹果都不曾切为两半，请问农妇带了多少苹果到市场去卖？
[4]某一个整数的个位数是2，把2移至最前方，数字立即变为原来的两倍，求原数。
[5]有3个骑士各带着一名随从在河边会合，想渡河到对岸。碰巧发现一艘可以容纳2人的小船。因为随从们都表示不愿意和自己主人以外的骑士在一起，而且无论如何威胁利诱，都没有任何效果，那三个胆怯的随从始终坚持他们的意见。但最后6个人还是凭那艘只能容纳2人的小船平安无事过了河，请问他们是如何做到的呢？ Read the rest of this entry »