看到新词就上一下Wikipedia确实是一个好习惯。前一篇日志的那个pdf里作者提到了Gedankenexperiment(Thought experiment)，上Wikipedia一查果然学到了牛B的新东西。好多物理定律其实完全是由思维实验推导出来的，难以置信仅仅是思考竟然就能得出物理世界遵从的各种法则。经典的物理思维实验有Newton大炮、Galileo斜塔实验、Schrödinger的猫猫、Maxwell的妖怪等等。还有，Turing机也是一个伟大的思维实验。

   
    数学上的不少悖论（特别是涉及到维度和无穷的悖论）都是相当有趣的思维实验。Gabriel喇叭是y=1/x在[1,+∞)上的图象沿x轴旋转一周所形成的旋转体。这个简单的三维图形有一个奇特的性质：它的表面积无穷大，却只有有限的体积。为了证实这一点，只需注意到：
   
    Gabriel喇叭会导出一个非常诡异的悖论：如果你想用涂料把Gabriel喇叭的表面刷一遍，你需要无穷多的涂料；然而把涂料倒进Gabriel喇叭填满整个内部空间，所需要的涂料反而是有限的。
    有网友一定会问，那有没有什么二维图形，面积有限大，周长却无限长呢？答案是肯定的，Koch雪花就是这样一个经典的例子。不过，通过分形构造出来的这类图形似乎并不存在涂料悖论，因为递归到一定深度时分形图形的尺度将小于表面涂料的厚度，因此表面大小不能永无止境地算下去，涂满表面所需的涂料不再是无穷多。当考虑到涂料厚度时，原先的悖论也可以解释清楚了：填充内部空间仅仅涂满了图形的内表面，一旦考虑到涂料的厚度，它和外表面的区别就出来了。

查看更多 »

如果一个矩形可以分割为若干个小矩形，每个小矩形都有至少一边为整数长，则原矩形同样有至少一个长度为整数的边。换句话说，用至少有一边的长度是整数的小矩形拼成一个大矩形，大矩形也有至少一条整数长的边。

    在这个命题的所有常见的证明方法中，我总觉得这个证明是最诡异的。真不知道第一个想出这个证明方法的人是怎么思考出来的。把矩形放在平面直角坐标系上，左下角对齐原点(0,0)。考虑函数e^(2 · pi · i · (x+y))在每个小矩形上的积分（展开并分离变量分别积分）：
    

    显然，这个式子等于0当且仅当(x1-x0)和(y1-y0)中至少一个是整数（也即至少有一边的长度是整数）。考虑函数在整个大矩形上的积分，它可以拆成各个小矩形上的积分的和，因此结果仍然是0。这说明，大矩形至少有一条整数长的边。

    Proofs from THE BOOK的第六章相当精彩，这一章循序渐进地介绍了多个无理性证明。先证明e是无理数，证明方法和高数课本上的基本相同；试图用类似的办法证明e^2也是无理数时，这一章的内容开始牛B了起来，一些巧妙的变换就让原来的办法继续适用于e^2的证明；加上一些更有趣的技巧，我们还能继续证明e^4也是无理数；当证明对除0外的所有有理数r，e^r都是无理数时，全章达到了高潮。
    这一章还提到了pi^2是无理数的证明方法。这个证明建立在Ivan Niven于1947年提出的“pi是无理数”的经典证明的基础上：仅仅是在原证明过程中加了一些微妙的变化就得到了pi^2也是无理数的结论。注意到，“pi^2是无理数”是一个比“pi是无理数”更强的结论。由于有理数的平方还是有理数，因此证到了pi^2是无理数也就说明了pi必然是无理数；但反过来却不行，因为无理数的平方不一定也是无理数，比如根号2的平方就不是无理数。

    证明过程用到了一个函数，其中n是一个任取的大于等于1的常数。可以想像，这个函数的分子部分展开后是一个关于x的整系数多项式，最低次数为n，最高次数为2n。我们将用到这个函数的两个性质：首先，当0<x<1时，显然有0 < f(x) < 1/n!；其次，函数f及其任意阶导数在x=0和x=1处都是整数。为了证明后一个结论，首先注意到当x=0时，不管是多少阶的导数，除了常数项以外其余项都是0；常数项只可能在n<=k<=2n时出现（k表示k阶导数），但此时它等于一个整系数乘以k!/n!，显然也是个整数。另外，由于f(x)=f(1-x)，根据复合函数的微分法我们立即得到对任意x都成立，当然也就有。

查看更多 »

来源：http://abstrusegoose.com/26

    又回来更新啦！虽然还有两门课没考，但今天已经轻松了不少。梦魇般的现代文学史总算是结束了。抱了两天两夜的佛脚，结果考试时一看卷子，仍然没一道会的题目。不定项选择多选少选均不得分，都是些文学常识题，给四篇我从没见过的小说名字问哪些是第一人称叙事，或者给四个人名字问哪些是笔名之类的。天哪……以后的古代文学史咋办啊。
    先强烈推荐一本好书。前几天在TopLanguage看到有牛人推荐Proofs from THE BOOK这本书，当即决定买了下来。这几天复习累了我都在看这本书，真的是很好很强大，里面汇集了很多著名问题的经典证明，包括很多我一直想找但没找到的证明。好了不多废话了，下面进入正题。

    很早以前，我们曾经研究过质数，证明了质数有无穷多个。后来，我们又学到了另外两种证明质数无穷多的方法。这两种方法的基本思路相同：寻找一个无穷大的集合，里面的数两两互质。只用有限个质数明显不能得到无穷多个两两互质的数，于是我们立即可知质数必然有无穷多个。今天，我们将证明两个比质数无穷多更强的定理。这两个证明都出自Proofs from THE BOOK的第一章。

    定义函数π(x)为“小于等于x的质数有多少个”。无妨规定x为一个正整数。我们将用初等微积分方法证明当x趋于无穷时π(x)也趋于无穷并给出π(x)的一个下界。我们将说明，对于所有x，π(x)>=log(x)-1，即x以内的质数至少有log(x)-1个。
    为了说明这一点，让我们考虑所有不超过x的质数的倒数的等比级数(1 + 1/p + 1/p^2 + ..)的乘积，即。
    回忆等比级数的公式，则我们有：

    第二行的一些变换非常巧妙。第二行中间的不等号是一个关键，用到了一个基本事实：第k个质数显然比k大。最后的连乘中前一项的分子和后一项的分母正好抵消，最后消完了就只剩了一个π(x)+1。
    另一方面，想像一下把(1+1/2+1/4+...)(1+1/3+1/9+...)(1+1/5+1/25+...)...展开的样子，很显然展开后的每一项都是一个所有质因子都不大于x的数的倒数，即Σ(1/m)，其中m取所有仅含1..x范围内的质因子的数。显然，原本就比x小的数，其质因子当然不可能超过x，这就是说从1到x的所有正整数都是属于m的。利用一些微积分的基本知识，我们可以立即得出Σ(1/m) >= 1+1/2+1/3+...+1/x >= log(x)。地球人都知道，log(x)是没有上界的，于是质数的个数也没有上界。
    这里还有一个类似的问题，大家可以对照着看看。

查看更多 »

    我们平时习惯说“微积分”。有趣的是，积分的出现远远早于微分。积分思想的早期萌芽甚至可以追溯到古希腊时代，Democritus曾运用这种思想解决了很多复杂的问题。他的“数学原子论”观点强调几何体是由一个一个面重叠而成，而面则是由线组成。他把圆锥看作一个个不可再分的薄片，从而成功地得到了圆锥体体积公式：圆锥的体积等于等底等高的圆柱体体积的1/3。事实上，仅仅凭借经验加实验，这个公式也很容易被发现，因此我们这里不再仔细追究公式的推导过程。但古希腊人对球体积的研究却迟迟没有进展。此时，一代神牛Archimedes出现了。Archimedes用了一种出人意料的神奇方法找到了球的体积公式，整个推导过程令人称叹不已，拍案叫绝。
    我们从圆的方程开始说起。首先观察方程(x-a)^2 + y^2 = a^2，这是一个中心在(a,0)，半径为a的圆，它在y轴右边与y轴相切。整理一下这个式子，我们有x^2 + y^2 = 2ax。在这个式子中，x可以从0取到2a，每一个x的值就对应着一个y值，它表示圆上对应位置的半弦长。注意到这个式子的特殊性：如果等式两边同时乘以π，牛B东西就来了：πx^2 + πy^2 = 2aπx，左边出现了两个与圆面积相关的项。这使我们有了一种让等式两边再乘以一个2a的冲动，因为这样的话等式右边也出现了一个与2a相关的圆面积：2a(πx^2 + πy^2) = x π(2a)^2。现在的问题是，等式左边多出来的一个2a和等式右边的那个x该咋办？不用担心，我们不是有杠杆原理这种牛B东西么，这两个东西可以当力臂长啊。于是，一个现在看上去并不算太突兀的力学模型出现了：

      
    找一根不计重量的金属杆，水平放置这根金属杆并以O为支点。金属杆右边串一个半径和高都是2a的圆柱体，圆柱体的左端点与支点O重合。把一个半径为a的球和一个底面半径和高都是2a的圆锥用绳子串起来，悬挂在左边距支点2a处。再次回到我们刚才的等式2a(πx^2 + πy^2) = x π(2a)^2。发现了吗，每取一个x，式子中的三个圆面积公式正好对应着这三个几何体相应位置上的横截面积。右边的圆柱横截面积始终为π(2a)^2，它离原点的距离为x；左边那个圆锥的横截面积为πx^2，它与圆锥顶端的距离为x；圆锥上方的那个球里同样存在一个对应的截面，这个截面离球的顶端距离也是x，而它的面积则正好是πy^2（回忆之前提到的半弦长）。乘上它们各自的力臂，我们就得到了上面的式子，而这个式子左右两边是相等的。于是我们知道了，对于任何一个x，三个立体图形对应位置上的“切片”都能够使杠杆平衡。我们有理由相信，如果每一个切片都可以使杠杆平衡的话，取遍所有的切片后，整个系统也应该是平衡的。尽管这存在一个严密性的问题，但毫无疑问这种假设是非常合理的，并且这种想法很大程度上促成了后来微积分的产生。无论如何，Archimedes利用这种方法得到了正确的答案：假设球的体积是V，则由杠杆原理得2a*(V + π(2a)^2*2a/3) = a π(2a)^2*2a （右边那个圆柱体的重心在图形的正中间，它到支点的距离为a，这即是臂长）。解得，V=(4/3)πa^3。

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

    《数学与猜想》里引用了一段欧拉的这篇经典的研究报告，写的非常精彩。你可以从中看到一个数学家是如何进行发现、归纳、猜想和论证的。你可以看到两个完全不同的数学模型里出现了惊人的巧合，通过挖掘它们之间的内在联系，最终完成了伟大的统一。
    没扫描仪，拿相机拍的，效果非常不好，见谅了！
    另外，拜托大家不要盗链下面的图片。

  
  
  
  
  

    Quake III公开源码后，有人在game/code/q_math.c里发现了这样一段代码。它的作用是将一个数开平方并取倒，经测试这段代码比(float)(1.0/sqrt(x))快4倍：
float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // what the fuck?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}

    code/common/cm_trace.c中也出现了这样一段解释sqrt(x)的函数，与上面的代码唯一不同的就是这个函数返回的是number*y：
/*
================
SquareRootFloat
================
*/
float SquareRootFloat(float number) {
    long i;
    float x, y;
    const float f = 1.5F;

    x = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;
    i  = 0x5f3759df - ( i >> 1 );
    y  = * ( float * ) &i;
    y  = y * ( f - ( x * y * y ) );
    y  = y * ( f - ( x * y * y ) );
    return number * y;
}

    这样的代码速度肯定飞快，我就不用多说了；但算法的原理是什么呢？其实说穿了也不是很神，程序首先猜测了一个接近1/sqrt(number)的值，然后两次使用牛顿迭代法进行迭代。根号a的倒数实际上就是方程1/x^2 - a = 0的一个正实根，它的导数是-2/x^3。运用牛顿迭代公式x' = x - f(x)/f'(x)，式子化简为x' = x * (1.5 - 0.5a * x^2)。迭代几次后，x的值将趋于1/sqrt(a)。
    但这段代码真正牛B的是那个神秘的0x5f3759df，因为0x5f3759df - (i >> 1)出人意料地接近根号y的倒数。人们都不知道这个神秘的常数是怎么来的，只能把它当作神来膜拜。这个富有传奇色彩的常数到底咋回事，很少有人说得清楚。这篇论文比较科学地解释了这个常数。