首先呢，让我们来一个牛B函数大回顾。这下我不知道要赚多少的PV。你能否构造一个函数f(x)，使得：
它是一个阶梯状的连续函数？
它是除常函数之外的没有最小正周期的周期函数？
该函数只在一点连续？
该函数在[0,1]和(0,1)之间形成一一对应？
该函数某一点导数为正，但该点邻域不构成单增区间？
平面上任意小的圆内均包含函数上的点？
另外还有一些可能是众所周知（所以没在Blog里写过）的函数，比如处处连续但处处不可导的函数、在有理点处处不连续在无理点处处连续的函数等等。
好了，现在呢，又一个牛B东西出现了。你能不能想出这样一个函数f，它的定义域和值域都是R，并且对于任意小的区间l=(u,v)，这个函数都能把(u,v)满射到整个R上。换句话说，是否存在这样的函数f(x)，对于任意一个实数t以及任意一个区间(u,v)，总存在一个x满足u<x<v且f(x)=t。
这个月月初就开始看《从一到无穷大》，花了接近两个星期才看完。这确实是一本让人放不下手的好书。考虑到我的阅读速度，一个多星期一本书已经近乎神速了。在这本书里我经常会看到一些有趣的数学知识，前段时间我还写过书里提到的一个有趣的东西——环面上的染色问题反而比平面上的“四色问题”更加简单。这种例子并不罕见，很多时候一些扩展版的问题反而比原问题更加简单。在第八章，我看到了另一个好玩的东西：随机游走(random walk)问题。
随机游走问题是说，假如你每次随机选择一个方向迈出一个单位的长度，那么n次行动之后你离原点平均有多远（即离原点距离的期望值）。有趣的是，这个问题的二维情况反而比一维情况更加简单，关键就是一维情况下的绝对值符号无法打开来。先拿一维情况来说，多数人第一反应肯定是，平均距离应该是0，因为向左走和向右走的几率是一样的。确实，原点两边的情况是对称的，最终坐标的平均值应该是0才对；但我们这里考虑的是距离，它需要加上一个绝对值的符号，期望显然是一个比0大的数。如果我们做p次实验，那么我们要求的平均距离D就应该是
其中d的值随机取1或者-1。这里的绝对值符号是一个打不破的坚冰，它让处于不同绝对值符号内的d值无法互相抵消。但是，当同样的问题扩展到二维时，情况有了很大的改变。我们把每一步的路径投射到X轴和Y轴上，利用勾股定理我们可以求出离原点的距离的平方R^2的值：
一旦把平方展开后，有趣的事情出现了：这些X值和Y值都是有正有负均匀分布的，因此当实验次数p充分大时，除了那几个平方项以外，其它的都抵消了。最后呢，式子就变成了
于是呢，就有平均距离R=sqrt(n) （准确的说是均方根距离）。我们得出，在二维平面内随机选择方向走一个单位的长度，则n步之后离出发点的平均距离为根号n。这是一个很美妙的结论。
今天是10月25日。祝古汉MM生日快乐。
曾经有一段时间这个Blog的访问量和订阅量剧增，后来才知道因为这个Blog上的一道牛B题目被出成POJ的月赛题了。那道题目真的很好玩，题目和解答都很简单有趣。其实我挺喜欢这种“给出一个算法并证明该算法最优”类型的数学题目。这里再和大家分享一个类似的比较老的题目，有兴趣的话不妨先想想再看答案。
一次“交换”操作是指将数列中的两个数位置对换。我们假设，互不相交的若干个交换操作可以一次同时进行；换句话说，如果k个交换中任两个都不会对同一个数进行操作，那么这k个操作可以并行完成。例如，在数列
10, 6, 8, 5, 2, 3, 1, 4, 7, 9
中，我们可以同时交换第4个数和第6个数，第8个数和第9个数，以及第3个数和第7个数。经过这一次“并行交换”后，数列变为：
10, 6, 1, 3, 2, 5, 8, 7, 4, 9
任意给定一个长度为n的全排列，请问对该序列进行排序最坏情况下需要多少次并行交换？给出一种具体的算法，说明这个次数足够了；并且给出一种最坏情况，证明这个次数是必需的。
网友Mingliang Zhu在TopLanguage上发起提问。
设想这样一个计算机系统，它只支持以下几个操作：
1. 定义变量、给变量赋值；
2. 变量自身加一；
3. 令一段语句循环执行指定的次数。
这个系统只处理且只能处理0和正整数。系统不存在“溢出”的问题。
注意这个系统没有比较运算，事实上它甚至不存在Boolean值和判断语句。
循环语句也不是FOR i=a TO b DO的形式，只能是LOOP n的形式。
在这个系统上实现加法很容易，让a自增b次即可。现在的问题是，你能在这个系统上实现减法吗？
在去年10月份的数学文化节期间，我去听了好几次讲座，其中有一些讲的相当精彩。时间过得好快，转眼间又是一年了，如果不是Wind牛发短信问我去不去听讲座，我估计今年数学文化节过了都还想不起这档子事。于是和Wind牛跑去二教309，听了一场叫做《从数据中挖掘因果关系》的讲座。这个题目是很有趣的：数据本身并不说谎，难就难在我们如何从中挖掘出正确的信息。当我们讨论数据时，我们讲的最多的是数据的相关性，而我们希望得到的则是事件之间的因果联系；但事实往往是复杂的，统计数据有相关性并不意味着两个事件具有因果联系，而具有因果联系的两件事从统计数据上看有时也并不相关。
对于前者，最简单的例子就是公鸡打鸣与太阳升起：公鸡打鸣与太阳升起总是同时发生，但这并不表示把全世界所有的公鸡都杀光了后太阳就升不起来了。统计发现，手指头越黄的人，得肺癌的比例越大。但事实上，手指的颜色和得肺癌的几率之间显然没有直接的因果联系。那么为什么统计数据会显示出相关性呢？这是因为手指黄和肺癌都是由吸烟造成的，由此造成了这两者之间产生了虚假的相关性。我们还可以质疑：根据同样的道理，我们又如何能从统计数据中得出吸烟会致癌的结论呢？要想知道吸烟与癌症之间究竟是否有因果联系的话，方法很简单：找一群人随机分成两组，规定一组抽烟一组不抽烟，过它十几年再把这一拨人找回来，数一数看是不是抽烟的那一组人患肺癌的更多一些。这个实验方法本身是无可挑剔的，但它太不道德了，因此我们只能考虑用自然观察法：选择一些本来都不吸烟的健康人进行跟踪观察，然后呢，过段时间这一拨人里总会出现一些失意了堕落了犯上烟瘾的人，于是随着时间的流逝这帮人自然而然地分成了可供统计观察的两组人。注意，这里“是否吸烟”这一变量并不是随机化得来的，它并没有经过人为的干预，而是自然区分出来的。这是一个致命的缺陷！统计结果表明，犯上烟瘾的那些人得肺癌的几率远远高于其他人。这真的能够说明吸烟致癌吗？仔细想想你会发现这当然不能！原因恰似黄手指与肺癌一例：完全有可能是某个第三方变量同时对“爱吸烟”和“患肺癌”产生影响。1957年，Fisher提出了两个备选理论：癌症引起吸烟（烟瘾是癌症早期的一个症状），或者存在某种基因能够同时引起癌症和烟瘾。
有虚假的相关性数据，就有虚假的独立性数据。“健康工人效应”是一个特别有意思的理论。调查发现，在铀矿工作的工人居然与其它人的寿命一样长（有时甚至更长）。这表明在铀矿工作对身体无害么？当然不是！其实，是因为去铀矿工作的工人都是经过精心挑选的身强体壮的人，他们的寿命本来就该长一些，正是因为去了铀矿工作才把他们的寿命拉低到了平均水平。这一有趣的细节导致了数据的伪独立性。类似地，有数据表明打太极拳的人和不打太极拳的人平均寿命相同。事实上呢，太极拳确实可以强身健体、延长寿命，但打太极拳的人往往是体弱多病的人，这一事实也给统计数据带来了虚假的独立性。
你能想到的最大的数是多少？我电脑里A片的字节数？人体的细胞个数？整个地球的质量？宇宙间所有原子的个数？当然，在数学研究中，数学家们很可能会创造出一些比这些数都大的数。
1938年，数学家Edward Kasner的外甥发明了一个表示10^100的单词googol，这个数已经超过了宇宙中所有原子的个数。Pólya曾经猜想，小于等于n的正整数中，质因子个数为奇数的数不少于质因子个数为偶的数；1958年数学家C. B. Haselgrove首先给出了一个长达361位的反例。上个月，人们找到了一个新的Mersenne素数2^43112609-1，它一共有12978189位。1955年，数学家Stanley Skewes证明在不超过10^(10^(10^963))的范围内存在x满足π(x) > li(x)，其中π(x)表示不超过x的素数有多少个，而li(x)则是dt/ln(t)从0到x的定积分。
Matrix67 |
2008-10-30 23:16 | 
