Buffon投针实验:究竟为什么是pi?

    重要通告:最近多次发现我的tom邮箱发出的邮件被识别成了垃圾邮件,是什么原因我还不是很清楚。最近向我的tom邮箱发过邮件但迟迟没有收到回复的朋友麻烦检查一下垃圾邮件箱,或者重新给我发一次邮件,我换一个邮箱回复您。

    数学学习真正悲哀的就是,记住了某个神奇而伟大的定理,看懂了其最严密的推导过程,但却始终没能直观地去理解它。虽然严密的推导是必要的,直观理解往往是不准确的,但如果能悟出一个让定理一瞬间变得很显然的解释,这不但是一件很酷的事,而且对定理更透彻的理解和更熟练的运用也很有帮助。我惊奇地发现,国内的每一本高数课本上都严格地讲解了微积分基本定理的证明,但几乎没有任何一个课本上讲过积分等于函数下方的图形面积究竟是为什么。事实上,这几乎是显然的,但还是有不少人学完微积分后仍然没有意识到。每当谈到这个问题时,我更愿意首先提出一个非常有启发性的事实——圆的周长是2·pi·r,圆的面积就是pi·r^2,后者的导数正好就是前者。这个现象是很容易理解的,因为圆的半径每增加一点,面积增加的就是周长那么一圈,换句话说面积的变化就等于周长。类似地,如果你能找到一个函数g(x),它的导数正好就是f(x),那么当x每增加一点,g(x)就增加了一条小竖线段,显然g(x)就应当是f(x)下方的面积。看清了这一点之后,我们才能欣赏到微积分基本定理真正牛B的地方。原先大家都是用分割求极限的办法来求函数下方的面积,但Leibniz却把面积看作一个可变的整体,用一种办法“一下子”就把它求了出来。有趣的是,这种现在看来如此自然的神奇办法,一千多年来居然没有任何人想到。

Read more…

最近几天碰到的几个有趣的问题

最近几天见到了几道零散的、不成系统的趣题,在这里合成一篇文章,与大家分享。

1. 证明:对任意正整数n,n^2+n+1一定不是完全平方数。

2. 说一个实数是可表达的,当且仅当它能用有限长的语句明确地描述出来,如2147483648可以说成是“二的三十一次方”,√2即为“平方后等于二的正实数”,π即为“圆的周长和直径之比”。问题是,是否存在一个不可表达的实数?

3. 一个人有两个小孩儿,其中有一个生于星期二的男孩儿。问另一个是男孩儿的概率是多少?

4. 无需积分,计算

Read more…

趣题:随机选取两个无穷大的图,求两者相同的概率

    假设我们俩各自独立地随机选取一个有无穷多个顶点的图(两点之间1/2的概率有边1/2的概率没有边)。那么,我们俩选到相同的图的概率是多少?

    令人难以置信、但想通了之后又异常显然的是,两个图相同的概率为1。并且,我可以精确地告诉你,这个相同的图是什么样子的。考虑这样一个无穷大的图,我们用自然数1, 2, 3, …给所有顶点标号,然后如果y的二进制表达中的右起第x位为1,就在顶点x和顶点y之间连一条线。比如,顶点5就和顶点1、顶点3相连。我可以证明,我们俩都100%地会选取到上述这个图。

Read more…

趣题:均匀分布且和为常数的n个变量

    不知道大家有没有幻想过,数学中是否存在这样一个牛B的问题,发表出来后十几年硬是没有一个人解开;后来某人惊奇地发现,它有一个极其精妙的解答,整个解决过程只需要几句话就能说清楚,但它实在是太巧妙了,这么多年就没有任何人想到。最近我就遇到了这样的事情。3月份UyHiP的题目非常有趣,整个证明几句话就完了,但想到解法的却只有一人。
    题目描述也极其简单。对于哪些n,存在一种生成n个随机变量的算法,使得它们在0和1之间均匀分布,且它们的和是一个常数?更进一步,如果这n个变量中任意k个都相互独立,满足要求的k最大是多少(表示成关于n的函数)?

    当然,这道题目我也没想出来。答案公布前,我思考了很久,最后还是放弃了。显然n是偶数时这样的算法是存在的,例如当n=6时,只需要先独立地选取3个随机变量X_1, X_2, X_3,然后令X_4 = 1 – X_1,X_5 = 1 – X_2,X_6 = 1 – X_3即可。这可以保证6个变量之和总为3,且它们均匀地分布在[0,1]区间里。但是当n是奇数时,满足要求的算法就未必存在了。例如当n=3时,不妨让X_1和X_2随机取,X_3等于1.5 – X_1 – X_2。这种算法似乎很和谐,问题就出在X_3有可能不在0和1之间。那么,重复执行该操作直到返回一个落在[0,1]里的X_3呢?这样的话变量又不是均匀分布的了,这将让变量更容易取到中间去,因为X_1和X_2太小或太大往往算不出合法的X_3(下图是Mathematica模拟的结果)。我试图从“n个变量的和的期望值是n/2”出发,证明和为1.5的3个变量不可能均匀分布在0到1之间。不过,最终还是没有找到突破口。

Read more…

经典证明:几个利用概率法进行证明的例子

    概率论并不仅仅是用来算算概率的。有些时候,概率论远比我们想象中的更强大。

    考虑这样一个问题。考虑集合X上的一个集合族,集合族中的所有集合大小均为d。我们说这个集合族是可以二染色的,如果对X的元素进行适当的红蓝二着色之后,每个集合里面都包含了两种颜色的元素。例如,当d=3时,{1,2,3}, {1,2,4}, {1,3,4}, {2,3,5}就是可二染色的,把1、2染成红色,把3、4、5染成蓝色,则每个集合里都含有两种颜色。是否存在d=3的不可二染色集族呢?这样的集族当然是存在的,例如取集合{1,2,3,4,5}的全部C(5,3)个元素个数为3的子集,则无论如何染色,总会有一个集合里面的元素全是一种颜色。上述推理立即告诉我们,对于一个给定的d,一定存在一个集合个数为C(2d-1, d)的不可二染色集族。这个数目还能再少吗?我们想知道,不可二染色集族中的集合个数最少可以少到什么地步。一个极其简单的证明给出了一个下界:集族的大小一定大于2^(d-1)。当d=3时,你一辈子也不能构造一个不可二染色集族,里面只含4个集合。
    为了证明这一点,不妨对X中的所有元素进行随机着色,每个元素取成红色和蓝色的概率均等。那么,一个元素个数为d的集合中,所有元素均为一种颜色的概率就应该是1/2^(d-1)。如果集族内的集合个数只有不到2^(d-1)个,那么即使“集合中是否只有一种颜色”是互相独立的,这些事件的并(至少有一个集合内只有一种颜色)的概率也不超过2^(d-1) * 1/2^(d-1) = 1,何况这些事件还不是独立的,因此存在单色集合的概率必然小于1。这个概率值小于1说明什么?这说明,“至少有一个单色集合”并不是必然事件,一定有一种染色方案使得每个元素里都含两种颜色,换句话说该集族可以被二染色。

Read more…