专题:美妙的数学

专题:美妙的数学

一封名叫数学公式的情书

作者/ 结城浩

日本资深技术作家和程序员。二十年来笔耕不辍,在编程语言、设计模式、数学、密码技术等领域,编写著作三十余本。代表作有《数学女孩》系列、《程序员的数学》等。

作者主页:http://www.hyuki.com/

{%}

那是高一的春天。

开学典礼那天,春光明媚。

“美丽的樱花开了……大家在新学期新起点之际……在这有着悠久历史的校舍里……努力学习、努力锻炼……少年易老学难成……”

校长那冗长的致辞简直引人入睡,我借着扶正眼镜的机会强忍住了呵欠。

开学典礼结束后,我在回教室的途中悄悄地溜了出来,独自一人漫步在校内的樱花树林间。周围连个人影都没有。

我现在 15 岁。15 岁、16 岁、17 岁……毕业的时候我将 18 岁了。有一个 4 次方的数字和一个质数。

{%}

在校门口

我已经读高二了,但对我来说唯一变化的就是身上别着的年级牌子。和昨天一样的生活今天仍然在继续,直到今天早晨我还这么认为。

“这…… 这个,请您读读看!”

四月底的一个多云的早晨,我在校门口被一个女孩叫住了。

她两手捧着个白色的信封,将它送到我面前。就这样,我莫名其妙地收下了这封信。那个女孩子向我行了个礼,就飞奔着进了校园。

她比我矮很多。我从来都没有见过这个女孩子,我想她可能是前阵子刚入学的新生吧。我迅速将信塞入衣服口袋,便朝教室走去。

上次收到信还是在上小学的时候。那次是因为我感冒休假,一个女班干部将作业题和一封信一起交给了我。信上写着:“大家都等着你哦。愿你身体快点好起来,快点回到学校来噢。”与其说是信,更像是一张简单的便条。

正如过去米尔嘉对我所说的:“谁都不知道接下来会发生什么。”和昨天一样的生活今天不一定会继续。

上课时,衣服口袋里的那个信封一直挠得我心里发痒。

心算智力题

“给你做个心算小测验。1024 的约数有几个呀?”

午休的时候,我正准备拿出那个女孩的信,米尔嘉一边啃着奇巧威化巧克力,一边到我的座位边向我提问。因为中途不能换班级,所以到了高二,我和米尔嘉仍旧是同班同学。

“心算吗?”我边问边把信重新放回衣服口袋。

“在我数到 10 之前回答我。0, 1, 2, 3, ... ”

等等。1024 的约数……1024 是能被除尽的数吗?可以被 1 除吧,被 2 除也可以,但不能被 3 除。1024 不能被 3 除尽,但是可以被 4 除尽。啊,对了,1024 是 2 的 10 次方……我开始进行紧张的计算。

“... , 9, 10。时间到了,算好了吗?几个呀?”米尔嘉问。

“11 个。1024 的约数有 11 个。”我赶忙答道。

“完全正确。你是怎么计算的?”米尔嘉伸出舌头舔舔沾有巧克力的手指,等着我回答。

“将 1024 进行因数分解得到的是 2 的 10 次方。也就是说,将 1024 变成 10 个 2 相乘的形式。”我回答道。

{%}

我接着说:“1024 的约数能够被 1024 整除。也就是说,所有的约数必定是 2 的 n 次方。n 在 0 到 10 之间取值。所以,1024 的约数就是以下这 11 个。”

2^0,2^1,2^2,2^3,2^4,2^5,2^6,2^7,2^8,2^9,2^{10}

听了我的回答后,米尔嘉频频点头表示赞同:“对啊。那我就接着出下一题喽。把 1024 的所有约数相加,最后所得的和为多少呀?”

“米尔嘉,不好意思,我中午还有其他事情,我过会儿再回答你……”我边说边站起身。

米尔嘉突然被我打断问话,顿时露出了不高兴的神色。我也顾不上这些,匆匆离开了教室。

可是,打断别人问话很没礼貌吧。米尔嘉问我什么来着?求 1024 的所有约数之和是吧?我一边想着一边朝楼上爬。

虽说是午休时间,但外面的人还是很少。我猜想大概是因为天气不好的关系吧。

在信封里有一张白色的信纸,信是用钢笔写的,字迹清秀。

我是今年春天刚入学的泰朵拉。我和学长您是同一所初中毕业的,比您小一届。我想和学长探讨关于如何才能学好数学的问题,所以写了这封信。

虽然我对数学十分感兴趣,但是从初中开始我的数学成绩就不好。进入高中后,我听说高中数学是非常难学的,所以想向学长讨教一下该怎么克服这个薄弱科目。

在百忙之中打扰您,真是不好意思,不知道您是否愿意与我探讨一下这个问题呢?如果可以的话,今天放学后,我在阶梯教室等您。

泰朵拉

我将这封信读了 4 遍。

原来是这样,这个女孩子名叫泰朵拉呀。她和我在同一个初中,而且是比我小一届的学妹,我真的一点都不记得了。但是数学不好的同学确实很多,更不用说是刚入校的新生了。

暂且不说这些,这封信和小学时的那张便条也差不了多少。我完全会错意了。唉!算了,就这样吧。

放学后,只好去阶梯教室喽。

放学后

“1024 的所有约数之和算出来没有啊?”

一天的课程结束后,我正准备去阶梯教室,米尔嘉突然又开始对我发问了。

“是 2047。”我立刻回答。1024 的所有约数之和是 2047。

“对是对了,但那是因为你考虑的时间非常充分吧。”米尔嘉说。

“算是吧……再见。”我向她道别。

“你是去图书室吗?”顿时,她的眼神中掠过一丝光芒。

“不是,今天可能不去图书室了,有点急事。”我说。

“嗯,这样啊,那我给你布置家庭作业。”她说。

米尔嘉给我布置的家庭作业

有一个正整数 n,如何求出 n 的所有约数之和?请写出解题方法。

我听后问道:“这道题的意思是不是要用 n 来表示其所有约数之和?”

“不是,你只要告诉我求解的步骤就可以了。”她说。

阶梯教室

“啊,真对……对不起。特地叫您来一次……”

我一踏入阶梯教室,就看见一个紧张地等待着我出现的女孩子。她就是泰朵拉,怀里抱着笔记本和铅笔盒。

“学……学长,我非常想和您交流,可是我却不知道该怎么跟您说。听朋友说,在阶梯教室说话会比较方便,所以就……”

从主教学楼穿过中心花园,就是阶梯教室,物理课和化学课一般都在阶梯教室进行。教室内每排椅子的摆放呈阶梯状,最低处是讲台。这样做是为了让教室里坐着的所有学生都能看清讲台上老师所做的实验。

我和泰朵拉坐在教室最后一排的长椅上。我从衣服口袋里掏出今天早晨收到的信。

“我读了信哦。但不好意思的是,我不太记得你了。”我说。

她拼命地摆摆右手说:“那当然,我也认为您不会记得我。”

我接着问道:“对了,你是怎么知道我的呀?我想我中学时应该没那么受人瞩目吧。”我是一个不参加任何课外活动的男孩子,一放学就往图书室跑,不会引起别人注意吧。

“嗯,这是因为……不是啦,学长可是很有名的哦。我……我……”她一个劲地解释。

“算了,没关系。对了,你不是因为自己数学不好,想要和我讨论讨论吗?我可以问问你的详细情况吗?”我言归正传。

“好的。谢谢您。我上小学时,觉得数学问题啦计算啦都非常有意思,可是进了初中以后,无论是听老师讲课还是自己看书,都觉得自己越来越不能理解了。到了高中,老师说数学很重要,叮嘱我们一定要认真学习。我也很努力地在学,但是总不能完全理解,不知道学长是不是有办法帮帮我?”她说明了自己的学习情况。

“原来如此。”我又问,“顺便问一下,你有没有因为你所说的‘不能完全理解’而导致考试成绩不太好呢?”

“这个倒还不至于。”她答道。

泰朵拉用大拇指按着嘴唇,思考着。她留着一头短发,一双机灵的大眼睛,眼珠滴溜溜地转动着。这让我感觉她很像有活力的小动物,比如说小松鼠,或者小猫咪,她给我的感觉大概就是这样。

“像单元测验之类的考试,如果事先告诉我们考试范围的话,我还能凑合着考考,但像水平测验之类的不知道考试范围的考试,我曾得过很惨的分数。成绩的落差非常大。”她补充道。

我接着问:“那上课怎么样呢?都听得懂吗?”

她说:“说到上课嘛,我很想能够全部理解……”

“但感到听不懂,对吗?”我问。

“是啊。我觉得不是很懂。我能解题,但也只能解个大概。我上课能听懂,但也只是懂个大概。但是,事实上是没有真懂。”她说。

质数的定义

“我可以再问得具体点吗?你知道质数吗?”我问泰朵拉。

“嗯…… 我想我知道吧。”她说。

“你想你知道?那我问问你,你能说说质数的定义吗?请你回答‘质数是什么’这个问题。不要用计算公式来表示,用语言表达就可以了。”我紧追不放。

“问我质数是什么啊。嗯,就是类似 5 啦 7 啦之类的数字吧。”她回答道。

“嗯,5 和 7 都是质数。这是对的,但是 5 和 7 只能说是可以被称为质数的两个例子。‘举例说明’和‘下定义’是不同的。”我纠正了她的说法,之后再一次问道,“质数是什么呢?”

泰朵拉点点头说:“好吧。质数是……‘只能被 1 和其本身整除的数字’吧?数学老师说过必须要背出质数的定义,所以我还记得。”

我接着她的话说:“如果是这样的话,你一定也认为下面我说的这个定义是正确的吧。”

“正整数 p 只能被 1 和 p 整除时,我们把 p 叫作质数。”(?)

“是啊,我认为是对的。”她说。

“不对,这个定义是错误的。”我说道。

“啊?但是比如说 5 是质数,它不就只能被 1 和 5 整除嘛。”她不明白。

我解释道:“嗯,5 确实是质数。但是如果照这个定义来说的话,1 也变成质数了。为什么这么说呢,因为如果 p 是 1 的话,p 也只能被 1 和 p 整除啊。但是,1 不算在质数里。最小的质数应该是 2。把质数以从小到大的顺序排列的话,是从 2 开始的。”

2, 3, 5, 7, 11, 13, 17, 19, ...

我继续说道:“所以上面我说的定义是不对的。关于质数,正确的定义应该是下面这样,要排除个别情况。”

“正整数 p 只能被 1 和 p 整除时,我们把 p 叫作质数。但是质数不包括 1。”

“或者在句首加上条件进行定义。”我补充道。

比 1 大的整数 p 只能被 1 和 p 整除时,我们把 p 叫作质数。”

“或者将这个加上的条件写成算式也可以。”我又补充说。

“当整数 p > 1,并且只能被 1 和 p 整除时,我们把 p 叫作质数。”

“哦,对哦,1 不是质数……我想起来了,我确实学过。学长所说的定义我也完全理解了。但是……”这时,泰朵拉猛地抬起头说,“质数不包括 1 这一点我是明白了。但是,还是不能完全接受。为什么质数不包括 1 呢?为什么包括了 1 就不对了呢?我不是很明白质数不包含 1 的 rationale。”

“rationale 是什么意思啊?”我不解。

“rationale 就是正当的理由,可以用原理来说明的理论根据。”她答道。

啊,这孩子,这个女孩原来知道彻彻底底理解的重要性啊。

“学长?”她好像看出我走神了。

“啊,对不起,你问我质数为什么不能包含 1 对吧?很简单哦。那是因为质因数分解有唯一分解定理。”我回过神来。

“质因数分解的唯一分解定理是什么呀?”她问道。

“质因数分解的唯一分解定理就是说,将某个正整数 n 分解质因数时,其形式是唯一的。比如,将 24 进行质因数分解,其唯一形式是 2 × 2 × 2 × 3。不过,不用考虑这些质因数的顺序,不论是 2 × 2 × 3 × 2 还是 3 × 2 × 2 × 2,这些形式只是质因数的顺序不同而已,我们仍把它们看作是同一种质因数分解的形式。质因数分解的唯一分解定理对于数学而言是非常重要的,为了遵循这个定理,规定 1 不包含在质数范围内。”我向她解释。

“仅仅为了遵循质因数分解的唯一分解定理,就随随便便地这么规定吗?”她不能理解。

“是啊。不过你说随随便便规定有点言过其实了。数学家们是为了建立一个数学的世界而规定一些有用的数学概念,然后再给这些概念取名,也就是对其进行定义。如果能清晰地给这些概念做出规定的话,至少作为定义是合格的。所以,正如你所说的,质数包含 1 的定义也是有可能的。但是,定义是否可能与这个定义是否有用是有区别的。如果照你所说的,将 1 放到质数里,这样就不能运用质因数分解的唯一分解定理了。顺便问一下,你现在理解质因数分解的唯一分解定理了吗?”我说。

“嗯,我觉得我是理解了。”她回答。

“嗯,为什么你只是觉得自己理解了呢?自己是否已经真正理解必须靠自己来确定。”我特别强调了“自己”两个字。

“是否真正理解要靠自己来确定,此话怎讲?”她问道。

“比如说,可以举个恰当的例子来考查自己是不是真正理解了。‘举例是理解的试金石。’虽然举例并不是定义,但是举一个确切的例子是很好的练习。”我答道。

“如果 1 包含在质数里的话,质因数分解的唯一分解定理就不成立了。请举例说明。”

“这样啊。如果 1 包含在质数里的话,24 的分解质因数就变为这样了,会出现很多种形式……”她说。

\begin{aligned}2\times2\times2\times3&\\2\times2\times2\times2\times3&\\1\times1\times2\times2\times2\times3&\\\vdots&\end{aligned}

“嗯,是啊。这就是质因数分解的唯一分解定理不成立的例子。”

泰朵拉听了我的话后顿时放心了。

“只是,比起‘会出现很多种形式’这样的说法,‘会出现几种’或者‘会出现两种以上’的说法更好些。为什么这么说呢,那是因为……”我的话还没说完,就听泰朵拉紧跟着说:“那是因为后者表达更严谨吧?”

“正是如此。‘很多’这个表达方式不够严谨。到底大于几个才算是‘很多’呢?这种表达有歧义。”我说。

泰朵拉说:“学长,不知怎么的,我感觉我的脑子像被彻底打扫了一遍,重新装进了定义、举例、质数、分解质因数、唯一分解定理,等等。另外,还要注意语言表达的严谨性。对数学而言,如何应用语言来表达是非常重要的吧?”

“对,你真聪明。在对数学概念的表达上可要谨慎地使用语言。为了尽量不让人产生误解,就要使用严密的语言。对数学表达而言,最最严密的语言就是数学公式了。”我说。

“数学公式……”她不明白。

“说到数学语言,就不得不说数学公式。我想使用黑板,我们往下走走去讲台那里吧。”于是,我就顺着楼梯往下走,泰朵拉跟在我后面。才走了两三步,只听“咔”的一声,我顿时感到背部一阵剧烈疼痛。

“啊!”我不禁大叫。

“不,不好意思!”泰朵拉连忙道歉。

她不小心在阶梯处绊了一跤,正好撞在我身上。我们两个人差点一起滚下去,幸好我拼命地站稳了脚。真是太危险了!

绝对值的定义

“那么你知道绝对值吗?”我问。我们面朝着黑板,在讲台上并排站着。

“嗯,我想我知道吧。5 的绝对值就是 5,-5 的绝对值也是 5,就是只要把负数的负号去掉就可以了吧?”泰朵拉回答道。

“嗯……那么,用数学式子来表示 x 的绝对值的定义的话,这样写你是不是能接受呢?”我在黑板上写下数学式子。

x 的绝对值 |x| 的定义

{%}

“啊,这样说来,我对此还真有点疑问呢。x 的绝对值不是去掉负号就可以了吗?为什么会出现 -x 的情况呢?”她疑惑不解。

“‘去掉负号’这一说法就数学语言而言是比较暧昧不清的。虽然这种说法能够让人理解其意思,能够大致明白说的是什么。”我说。

“那么,把这个说法改成‘把负号变成正号’呢?”她紧追不舍。

“这样说也很暧昧不清啊。比如,-x 的绝对值是什么?”我在黑板上写道。

|-x|

“去掉负号,答案是 x 吧,也就是说,|-x| 等于 x。”她答道。

“错了。那如果 x 等于 -3,答案将如何呢?”我举出反例。

“啊? x 如果是 -3 的话……”泰朵拉也在黑板上写了起来。

{%}

“如果照你所说的 |-x| 就是 x 的话,x 是 -3 的时候,|-x| 必须是 -3 了。但是事实上,|-x| 却是 3。也就是说,|-x| 应该等于 -x。”听了我的解释,泰朵拉又看了看式子,开始陷入沉思。

“啊,我知道了。是啊,x 原本就是负数的时候,如果不再加上一个负号的话,这个数字就变不了正数。不知怎么的,我无意识中就把 x 当作是 3 啦、5 啦之类的正数了。”她恍然大悟。

“对啊,x 这个字母前面没有加什么符号,所以一般人们都不会想到 x 还可能是 -3 这样的情况,但这恰恰又是很重要的。用 x 来表示就是因为不用举出具体数字,就能定义 x 的绝对值。如果只是说‘去掉负号就是绝对值’,那就过于片面了。另外,我们还必须要注意不能忘了加上条件。说得难听点,就是要让人觉得是在故意刁难他们,必须进行严密的思考。当你逐渐习惯了严密的思考时,你就会觉得自己也习惯数学公式和数学了。”

我正说着,泰朵拉一屁股坐在最前排的一把椅子上,她默不作声地用手指不停地玩弄着笔记本的页角,像是在思考着什么。

于是,我就在一旁等她开口说话。

“我……我是不是浪费了初中的大好时光呀?”她终于开口了。

“此话怎讲?”我问。

“我也算是读上来了,但是,我却从没有仔细地看过教科书中出现的定义和数学公式——我一直就没有认真对待。”她长叹一口气,显出非常失望的样子。

“喂!”我有话要说。

“嗯,怎么了?”泰朵拉看看我。

“如果你这么想的话,从现在开始学会严密思考也不晚啊。过去的事就让它过去吧。你要面对现在,对于现在认识到的事情,只要在今后好好注意就可以了。”我说。

泰朵拉像是舒了口气,睁大眼睛,立刻站起身来,“是……是啊。已经过去了的事情再怎么后悔也没有用了,要在今后好好注意。对,确实是这样,学长。”

“嗯…… 对了,今天就大致说到这里吧。天也快黑了,以后再继续聊吧。”我说。

“继续聊?”她问。

“嗯,我放学后一般都在图书室,泰朵拉,如果你还有什么要问我的话,再叫我好了。”我答道。

她听后顿时两眼放光,很开心地笑了笑,说:“好,一定!”

回家路上

走到教室门口时,泰朵拉抬头看看天空,叫道:“啊呀呀……下雨了!”天空乌云密布,飘起了蒙蒙细雨。

“你没带伞吗?”我问。

“早上赶着出门,忘记带了。真是白看天气预报了!——但没关系。反正是小雨,我快跑就行了。”她说。

“但跑到地铁站还是会被淋湿哦,反正我们是一个方向,一起走吧。我的伞也比较大。”我邀请道。

“那不好意思喽。谢谢您。”她同意了。

和女孩子同撑一把伞还是我有生以来第一次。春雨细细的,柔柔的,我们慢慢走着。刚开始时我还有点儿不自在,连走路都显得笨拙了,但随着我渐渐地跟上她的步伐,心情也平静了下来。这条路很安静。道路原本的嘈杂声可能都被雨水吸收了。

今天能和泰朵拉进行那么长时间的对话,我真的很高兴。像她这样的学妹真是可爱啊,心中有什么想法都表露在脸上,让人一看就知道她是不是真懂。

“学长,您为什么能立刻知道呢?”泰朵拉突然问我。

我回过神来:“知道什么呀?”

“没有,嗯……今天您和我说话时,为什么我不知道的地方立刻就被学长您发现了呢?我想不太明白。”她说。

啊,吓了我一跳。我还当她有心灵感应,知道我在想什么呢。

我定了定神:“今天所说的质数、绝对值的问题其实也是我以前所疑惑的。学习数学时,一有不懂的地方就很烦恼,会连续思考几天,看书,有时会突然间恍然大悟,‘啊,原来是这么回事啊。’那时就会特别开心。随着这种开心的体验越来越多,我就渐渐喜欢上了数学,数学也就越来越好了。——啊,这里要拐弯了。”

“拐角就是‘The Bend in the Road’吧?从这里走也能到车站吗?”她问。

“是啊,在这里拐弯,一直穿过住宅区到车站的话,要比别的路线快得多呢。”我说。

“会很快到车站吗?”她又问。

“是啊。早上走这条路线的话,也比较快哦。”我说。

哎呀,泰朵拉一下子放慢了脚步。是不是我走得太快了呢?要和上她的脚步还真难。

到车站了。

“那就这样了,我还要顺便去一下书店,再见。对了,我把伞借给你吧。”我说。

“啊,在这里就告别吗?嗯……那个……”她支支吾吾。

“嗯?怎么了?”我说。

“没……没什么。把伞借给我吧,我明天还您。今天真是谢谢您了。”泰朵拉把双手摆在腿前,深深地朝我鞠了一躬。

自己家

夜晚。

我一个人在房间里回想着今天和泰朵拉之间的对话。她是那么地坦率,而且求知欲强,今后一定会有发展空间的。我想如果她也能渐渐体会到数学的乐趣就好了。

和泰朵拉说话的时候,我有种教她学习数学的感觉。这种感觉与我和米尔嘉说话时的感觉完全不同。米尔嘉始终在牵着我的鼻子走。确切地说是她在教我。

想到米尔嘉,我突然想起了她给我留的“家庭作业”。竟然有同班同学给我布置家庭作业的。

米尔嘉给我布置的家庭作业

有一个正整数 n,如何求出 n 的所有约数之和?请写出解题方法

这个问题只要求出 n 的所有约数就能得出答案了。先求出 n 的所有约数,然后把它们相加求出“约数之和”。但是,这种求解方式也太复杂了吧,我再想想还有没有其他什么简便的方法。嗯,试试把整数 n 进行质因数分解。

我想到了午休时的题目:1024 是 2 的 10 次方。如果把此题用字母来表示的话,比如说将 n 变成质数的乘方形式,如下所示。

n = pm p 为质数,m 为正整数

n = 1024 时,上式就变为 p = 2,m = 10 的特殊形式。如果像列举 1024 的约数那样考虑的话,n 的约数就如下所示。

1,p,p^2,p^3,\cdots,p^m

所以当 n = pm 时,n 的所有约数之和应该按以下方法求解。

n 的所有约数和 1+p+p^2+p^3+\cdots+p^m

综上所述,当 npm 这一形式时,我们能够求出关于整数 n 的所有约数之和。

 

我们还可以将正整数 n 进行质因数分解。假设 p, q, r, ... 为质数,a, b, c, ... 为正整数。

n=p^a\times q^b\times r^c\times\cdots\times

啊,等一下。如果用字母的话,则不能表示其一般形式。如果在指数的地方有 a, b, c, ... ,再加上 p, q, r, ... 之类的字母,数学公式就变得混乱不堪。

如果能写成 2^3\times3^1\times7^4\times\cdots\times13^3 这样的形式就好了,也就是质数正整数的积的形式。

好,就这样写。用 p_0,p_1,p_2,\cdots,p_m 来表示质数,然后用 a_0,a_1,a_2,\cdots,a_m 来表示指数,在字母右下角标上下标 0, 1, 2, ... , m,虽然该公式有点杂乱,但这是一般形式。这里 m + 1 表示“将 n 分解质因数后质因数的个数”。我们再重新算一遍。

 

将正整数 n 进行质因数分解,一般都可以写成以下形式。假设 p_0,p_1,p_2,\cdots,p_m 为质数,a_0,a_1,a_2,\cdots,a_m 为正整数,则有

n=p^{a_0}_0\times p^{a_1}_1\times p^{a_2}_2\times\cdots\times p^{a_m}_m

n 的结构如果是这样的话,那么 n 的约数就可以表现为以下形式。

p^{b_0}_0\times p^{b_1}_1\times p^{b_2}_2\times\cdots\times p^{b_m}_m

此时,b_0,b_1,b_2,\cdots,b_m 就是以下整数。

{%}

嗯,如果仔细写出来的话,看起来真复杂啊。也就是说,如果质因数不变,指数从 0, 1, 2, ... 开始变化,就能形成不同的约数。说起来是很简单,但是变形成一般形式后,式子就比较多了。这种情况很常见。

不过变形后就很简单了。要求约数的和,只要把所有约数都加起来就可以了。

{%}

啊……不对不对,如果这样的话就不是“所有约数之和”了。这只是在约数中,以质因数的乘方形式组成的约数的和。事实上,约数的形式应该是下面这样。

p^{b_0}_0\times p^{b_1}_1\times p^{b_2}_2\times\cdots\times p^{b_m}_m

是否有必要将所有质因数乘方形式的所有组合都挑选出来,相乘后解得约数之和呢?用语言来描述反而复杂,还是用式子来表示吧。

{%}

我就米尔嘉布置的作业所做的解答

将正整数 n 进行质因数分解,如下所示。

n=p^{a_0}_0\times p^{a_1}_1\times p^{a_2}_2\times\cdots\times p^{a_m}_m

这里假设 p_0,p_1,p_2,\cdots,p_m 为质数,a_0,a_1,a_2,\cdots,a_m 为正整数,这时,n 的“所有约数之和”可以用以下式子来表示。

{%}

式子不能写得比这个更简洁了。——嗯,这样大概就对了。

米尔嘉的解答

“你回答得对!虽然式子写得比较杂乱。”第二天,米尔嘉碰见我时很坦率地告诉我。

“还有没有更简便的形式呀?”我问道。

“有啊。”米尔嘉不假思索地答道,“首先,相加的部分可以写成以下形式,只是要加上 1 - x 不等于 0 这个条件……”米尔嘉边说边在我的笔记本上写了起来。

1+x+x^2+x^3+\cdots+x^n=\frac{1-x^{n+1}}{1-x}

“啊,这样啊。”我说。这不就是等比数列的求和公式吗?

{%}

“用了这个公式的话,你写的乘方和就全变成了分数形式。接下来,乘积的部分就用 \prod 来表示。”米尔嘉说。

\prod 这个字母就是 π 的大写字母啊!”我说道。

“嗯,是啊。但是这个和圆周率一点关系都没有。\prod^{\text{Product}} 就是 \sum^{\text{Sum}} 的乘法运算。乘积(Product)的英语首字母 P 在希腊语中就是用 \prod 来表示的,正如 \sum 那样,也是用希腊语 \sum 来表示和(Sum)的英语首字母 S。\prod 的定义式是这样的。”米尔嘉说。

\prod^m_{k=0}f(k)=f(0)\times f(1)\times f(2)\times f(3)\times\cdots\times f(m)  定义式

“如果使用 \prod 的话,那么乘积部分就能用简单的方式表达出来。”她说。

米尔嘉的解答

将比 1 大的整数 n 进行以下形式的质因数分解。

n=\prod^m_{k=0}p^{a_k}_k

假设 pk 为互不相同的质数,ak 为正整数。

那么,此时 n 的“所有约数之和”就可以用以下公式来求解。

{%}

“原来如此。虽然式子变短了,但是文字却增多了。对了,米尔嘉,今天你去图书室吗?”我问。

“不去。今天我要去盈盈那里练琴,听说她创作了新曲子。”她说。

本文节选自《数学女孩》

 

{%}

《数学女孩》以小说的形式展开,重点描述一群年轻人探寻数学中的美。内容由浅入深,数学讲解部分十分精妙,被称为“绝赞的初等数学科普书”。内容涉及数列和数学模型、斐波那契数列、卷积、调和数、泰勒展开、巴塞尔问题、分拆数等,非常适合对数学感兴趣的初高中生以及成人阅读。

被遗忘的女性

{%}

作者/ William Dunham

世界知名的数学史专家,现为美国穆伦堡学院教授。他笔耕不辍,著述颇丰,较有影响的著作还有Journey Through Genius: The Great Theorems of MathematicsThe Calculus Gallery: Masterpieces from Newton to Lebesgue(《微积分的历程:从牛顿到勒贝格》,中文版已由人民邮电出版社出版)。Dunham教授分别于1992年、1997年、2006年获得美国数学协会颁发的George Polya奖、Trevor Evans奖和Lester R. Ford奖。

如果读者有心记录,一定会发现数学世界里的男性明显多于女性。这种不平衡反映了数学科学中男性的历史优势。但是,这是否就意味着女性对数学学科的过去没有贡献,现今没有贡献,将来也不会有所贡献呢?

上面各问题的答案分别是“不”“当然不”“请严肃点”。数学史中女性的出现可以追溯到古典时代,而今天女性比以往任何时候都活跃。女性的生存要面对男数学家几乎无法想象的障碍,其中不仅因为她们缺少鼓励, 而且还有对女性加入的强烈阻碍。

首先, 我们承认, 在历史上最有影响的数学家的短短清单中,阿基米德、牛顿、欧拉、高斯等清一色都是男性。1900年之前数学界的女性人数非常少, 只有可数的几个人。其中经常提到的就是亚历山大的希帕蒂娅, 她大约生活在公元400年。夏特莱侯爵夫人(1706—1749)和玛丽亚·阿涅西(1718—1799)活跃在18世纪,索菲·热尔曼(1776—1831)、玛丽·萨默维尔(1780—1872)以及爱达·洛夫莱斯(1815—1852)工作在19世纪初。20世纪初,索菲亚·柯瓦列夫斯卡娅(在文学作品中也被称为索尼娅·柯瓦列夫斯基)跻身于这一清单之中。

这些女性当中,希帕蒂娅是一位颇有影响的几何学家、教师和作家;夏特莱侯爵夫人因为把牛顿翻译给法国人而知名,萨默维尔因为把拉普拉斯翻译给英国人而知名。1748年,阿涅西出版了数学教科书, 为此她得到了应有的认可。洛夫莱斯在查尔斯·巴贝奇制造他的第一台“分析机”时与他一起工作。

热尔曼和柯瓦列夫斯卡娅是这个清单中最多才多艺的数学家。前者对纯数学和应用数学都有研究。我们在第F章提到过她对费马大定理的研究,1816年因为她对弹力的数学分析工作而获得法国科学院的大奖。而柯瓦列夫斯卡娅取得了博士学位, 并在大学担任职务,取得了她那个时代女性的开创性成就。在这一过程中,她赢得了各个方面曾经对她怀疑的男性同事的尊重。

所以, 在20世纪之前女数学家肯定是存在的。令我们惊讶的不是人数很少,而是还真的是有。因为女性不仅需要克服对数学充满渴望的人要面对的通常意义下的种种障碍,即 高级数学的确相当困难,而且还必须克服各种各样的文化层面所带来的障碍。我们讨论一下挡住她们道路的三个最严重的障碍。

第一是,数学对女性的普遍的负面看法,这一看法在男性和女性身上都已根深蒂固。其核心就是相信女性不具备做纯数学的能力。这样的信仰已经深深印入很多人的大脑之中,其中不乏非常有影响力的人物。据说伊曼纽尔·康德就曾经发表评论说,女性“担心对几何动她们美丽的脑袋时”会长出胡须,这是出自一位如此重要的哲学家之口的最令人气馁的评论。1遗憾的是, 这样的看法在过去绝不是个案。在那个时代,很多希望学习三角学或者微积分的高中女孩子都被指导老师、家长或朋友劝说去从事家政学或者英语这些更适合女性思维方式的学科。不管你相信与否, 这样的状况一直在持续。

1Nadya Aisenberg and Mona Harrington,Women of Academe: Outsiders in the Sacred Grove, U.of Massachusetts Press, Amherst, MA, 1988, p. 9.

证明女性不能从事数学研究的诸多证据之一是从事这一研究的女性很少。换句话说, 数学中女性的缺乏被用来证明她们没有从事这门学科的能力。当然这些说辞的理由是荒谬的。这就与把第二世界大战之前美国职业棒球大联盟中缺少非洲裔美国人归结为他们没有玩这种游戏的素质是一样的。正如杰基·罗宾森、亨利·阿伦和其他很多人已经充分证明的那样,职业棒球大联盟缺少黑人球员不能证明他们缺乏能力,而只能说是缺少机会。

上面提到的具体人物充分说明女性也能研究数学。我们可以用近来非常活跃的女性数学家来证明这一点, 有格雷丝·奇泽姆·扬,20世纪初她在高等积分理论的改进中起到非常重要的作用, 有朱莉娅·罗宾森, 她是希尔伯特第十问题的解决者, 还有埃米·诺特,她是20世纪最有成就的代数学家之一。女性不能研究数学的观点是没有根据的。

但是, 还有一个与此相随的观点就是女性就不应该研究数学。往好处说, 那是在浪费时间;往坏处说, 那是有害的。正如小孩子不应该走近高速公路一样, 所以女性不应该走近数学。

我们以弗洛伦斯·南丁格尔为例,后来她在医学艺术领域赢得了声望。在她年轻的时候,她表现出对数学的极大热情, 因而对此感到奇怪的母亲问到,“数学对结了婚的女人有什么用?”2人类事业中没有什么比数学更有用的了。但是南丁格尔却被告知它是无用的。因为已经赋予了19世纪女性可接受的传统角色,无论如何数学都被看成是毫无用处的了。

2Cecil Woodham Smith, Florence Nightingale: 1820{1910, McGraw-Hill, New York, 1951, p. 27.

于是, 女性还被告知研究数学将损坏她的社交魅力。更有甚者,据说有什么医学证据显示,思虑过多的女性将会经历从生殖器官到大脑的血液转移过程,并伴随着非常可怕的后果。令我们好奇的是男性似乎不用担心类似的血液流。

这一类观点迅速变成行动, 或者更精确地说是, 无行动。热尔曼不得不用一个男性化的笔名发表她的数学论文;柯瓦列夫斯卡娅尽管怀有不可质疑的能力,但是最初学术位置还是拒绝她。甚至是伟大的埃米·诺特,她在德国哥廷根大学谋求低等职位时也遭到了冷遇。她的诽谤者不赞同或者担心一旦女人走入这一大门,将带来无法阻止的倒退。为此,戴维·希尔伯特用下面一段巧妙的讽刺对此做了回应:“我不明白这位候选人的性别为什么成了反对她就职的证据。毕竟, 我们这里是大学, 而不是洗浴场所。”3最终诺特得到了工作,而且这个数学团体(哥廷根大学)还活得相当得好。

3Auguste Dick, Emmy Noether, trans. H. I. Blocher Birkhäuser, Boston, 1981, p. 125.

第二个障碍是正规教育的拒绝。数学这门学科需要训练,高强度的训练。为了到达前沿, 你必须从基础开始进发,对于数学这样既古老又复杂的学科, 这需要花费几年的努力。在过去,很少有女性甚至开始这样艰辛的路程。因此,想在高级数学中取得成功几乎是不可能的。

男性又是如何学习这门学科的呢?他们通常接受家庭教师的辅导,或者一对一的授课。我们已经看到莱布尼茨去请教克里斯蒂安·惠更斯, 而欧拉与约翰·伯努利一起研究学习。这是培养把火炬传向未来的大师的过程。几乎没有女性有这样的机会。

而男性经过适当的训练之后迈入大学,在那里他们的才干和能力将会得到进一步的培养。高斯就读于Helmstadt大学, 旺策尔就读于法国巴黎综合理工学院,罗素就读于剑桥大学。

再对比一下, 热尔曼是一位非常有前途的人,却因为她的性别关系甚至被拒绝进入大学讲演礼堂。她只能在教室门口听课, 或者向有同情心的男同学借笔记来抄,就这样她秘密地跟上进度。用高斯的话说,她所取得的成功证明了她是一位“最具有勇气”4的女性。

4Fauvel and Gray, History of Mathematics, p. 497.

因此, 太多的女性根本没有实际接触过高级数学的世界。值得一提的是上面提到的很多女性家庭都比较富裕,而且拥有相应阶层的优势。热尔曼可以随意使用她父亲的图书馆。萨默维尔偷听他哥哥的家教课程。这些富裕家庭的女儿们显然有权选择不去顺应那些更合适宜的方法。正如迈克尔·迪肯对贫穷女性的数学前途评论到,“贫穷和女人气这一对无能的双胞胎太沉重了。”5

5Michael A. B. Deakin, “Women in Mathematics: Fact versus Fabulation,”Australian Mathematical Society Gazette, Vol. 19, No. 5, 1992, p. 112.

把这种情况与大致同一时期的女性作家比较一下很有趣。读和写是贵夫人训练的一部分, 尽管这只被看成是必要的社交技巧,而不是通向艺术生涯的手段。但是, 很多女性还是具备写作条件。如果她有充足的时间, 充足的训练和能力,她也许会利用这些条件去进行诗或文学的创作。其中简·奥斯丁就是一个例子,她的作品是她对周围人的生活的仔细观察,并通过她非凡的才能加以提炼而成的。奥斯丁会读、会写,她是一位艺术家。她创作的著作使她置身于英国文学伟人之列。

很多女孩还是学习了一些初级的计算, 这倒是实事。但是与文学不同,这种学习到此为止。高级数学的进步需要对几何、积分和微分方程等学科的了解,每一门学问都是以前者为基础的。 如果没有相应的训练,几乎没人能够掌握它们。 当女性的这种训练需求遭到拒绝时,与此同时她们也就被拒绝了接受数学工具。通向她们的科学未来的大门被砰的一声关上了。我们将永远无法知道数学界的简·奥斯丁了,因为缺少必要的正规教育而被数学抛弃了。

这一切都已经成为过去。现在情况如何呢?表面上的障碍已经消失,各大学也不再强制执行诸如热尔曼遭遇到的对女性的禁令。正相反,从美国各大学数学学科登记入学的数据来看, 我们有理由乐观。在1990年到1991年的这一学年,美国研究机构授予了14 661个数学本科毕业生。其中女生有6917人,占47%。这几乎接近一半的比率对于一个世纪前男性占主导的数学领域是不可想象的。

但当我们再看一看高级学位时,数据就令人很失望。就在同一学年,女性只占数学硕士学位的2/5,而且只占数学博士学 位的1/10。6 这种状况表明,尽管从数据上看进入本科教育的女性人数增长迅猛,但是她们很少可能继续她们的训练, 进入研究生层次,而从这里开始将产生出明天的研究型数学家和大学教授,所以这种状态仍然是男女不平衡。

6“Earned Degrees Conferred by U.S. Instiutions,”Chronicle of Higher Education, June 2, 1993, p. A-25.

为什么女性不能继续进入研究生院呢?从历史上看,很多女性立志当一名大学预科层次的老师,因此没有获得研究型学位的需要。在某种情况下,因为身处如上描述的各种观念之下,较低的自我评价的确对更高层次的成功产生了悲观的负面影响。其重要问题是勇气和寻找能鼓舞士气并帮助扫除学习高级数学之路上的各种障碍的良师益友。男性有太多同行和榜样;而女性在激烈的学术领域中总是感觉很孤单。她们的正规教育之路在很多方面不同于她们的男性同伴。

甚至当女性战胜了各种负面的看法, 获得了坚实的教育,还仍然存在很多障碍:女性缺少除了日常生活需求之外,全力从事她们工作的支持。

数学研究需要不受各方面干扰的大块时间。研究型数学家花很长时间坐在那里思考。在过去如此, 今天也是如此,这样大块的时间不是所有人都拥有的。正如上面提到的那样,最简单的方法就是非常富有。据传说阿基米德有部分锡拉库扎王族的血统。洛必达(1661—1704)侯爵非常富有,雇用约翰·伯努利在新兴微积分领域指导他, 随后而闻名欧洲。而我们上面所说的各位女性中, 夏特莱侯爵夫人是一位女侯爵,而洛夫莱斯则是一位女伯爵, 阿涅西是富人家的孩子。这些人当中没有人靠洗衣度日。

另一个方面的支持是欧洲的学术团体, 这是那个时代的研究中心。来自柏林、巴黎、圣彼德堡的赞助养活了无数的学者。在柏林和圣彼德堡取得职位的欧拉就是一位利用这样的机会取得成功的数学家。

或者你有一份要求不高的工作, 允许你在闲置的时间进行研究和沉思。我们已经提到过的莱布尼茨就是在巴黎的外交工作期间,寻找时间学习了数学并最终创造了微积分。地方法官费马似乎从来没有尽力做法院的工作, 而是做数学研究。

总之, 对于有潜力的数学家, 有钱是无害的, 成为学术团体的成员,或者只有部分时间被雇用, 都是无害的。当然,今天对数学家的主要赞助是研究型大学,这些机构提供办公室、图书室、旅行费用、想法相似的同事以及适度的教学任务。作为回报,希望数学家对这门学科的前沿做出深层次的思考。

对照一下女性的历史角色:在丈夫或兄弟在外面工作的时候待在家里、抚养孩子、做饭、缝缝补补和照料家务杂事。即使她们有这方面的训练,一个女人从哪里得到时间去思考微分方程或者是射影几何呢?对她们的期望是完全不同的。

事实上, 女性甚至很少有她们自己的空间。正如弗吉尼亚·伍尔夫在这一类话题的短文中提醒我们的那样,女性很少有独处、思考、写作(或进行数学研究)的空间。伍尔夫讲述了莎士比亚富有想象力的妹妹朱迪思的一个故事,她完全有她的哥哥一样的才能, 在威廉全身心投入他的作家生涯的时候,她的生活就是负责家庭的日常需要。据伍尔夫说, 莎士比亚的妹妹

和他一样, 敢做敢为, 富于想象力, 热切希望了解这个世界。但是她没有被送去学校。她没有机会学习语法和逻辑,只能读一点贺拉斯和维吉尔的东西。她偶尔拿起书……看几页。然后, 她的父母就会走进来告诉她去补补长袜或者留心做饭,而不是沉迷书本和纸墨。7

7Virginia Woolf, A Room of One's Own, Harvest/HBJ Books, New York, 1989, p. 47.

兄妹俩, 一个是支持的提供者, 而另一位却是接受者。这种差别也太大了。

再说一下莱昂哈德·欧拉, 13个孩子的父亲。必须有人来抚养他们,替他们换尿布, 清洗他们的衣服。但是这个人不是莱昂哈德。再看一下锡里尼哇沙·拉玛奴金(1887—1920),他是20世纪初一位非常有才华的数学家。但在日常生活中,他却显得像一个孩子那样无助, 他的妻子照顾他需要的每一件事情。再看保罗·厄多斯, 这个人我们在第A章遇到过,在他21时才学习如何往面包上涂黄油。显然, 在他进行数学发现的初期,他得到了来自母亲的不同寻常的支持。

如果交换一下, 情况又如何呢?欧拉夫人、拉玛奴金夫人和厄多斯夫人如果在数学上取得了成功,她们的另一半会满足她们的日常生活需要吗?如果这些女性已经成名,那么她们可以投入大块的时间去研究数学吗?没有人会知道答案。但是,如果女性能够得到与这些男人相同的支持,那么她们会有更多人出现在数学编年史中。这是毫无疑问的。

在索菲亚·柯瓦列夫斯卡娅这位“20世纪前最伟大的女数学家”8的生活之中,上面提到的所有障碍,如数学教育方面的负面观念和困难以及缺少系统的支持,都出现过。

8Gillispie, Dictionary of Scientific Biography, essay on Sonya Kovalevsky, p. 477.

1850年初柯瓦列夫斯卡娅出生在莫斯科, 在一个比较富裕的书香之家长大,她是一名英语家庭教师, 并有机会学习数学。有一个很有趣的故事,说她卧室的墙上贴满了她父亲的微积分课程的旧讲义笔记。这位年轻的姑娘被这些奇怪的公式深深吸引了,它们就像朋友一样静静地围绕在她的身边。她发誓有一天一定要知道其中的秘密。

当然, 这需要训练。一开始, 她学习了算术。她被允许参加她堂兄的家教课程, 基本上是为了骗他更加努力学习。就这样她获得了代数知识(即便他还不会)。接下来,柯瓦列夫斯卡娅从住在附近的物理学家那里借来一本他写的书看。在读这本书时, 她遇到了三角学的困难, 这是一门她几乎一无所知的学科。不愿意放弃但又找不到适当的指导,柯瓦列夫斯卡娅就从零开始做起了研究。当她的物理学家邻居意识到她在做什么的时候, 他惊奇地观察到,“她已经第二次创造了整个三角学这门学科。”9

9Koblitz, Convergence of Lives, p. 49.

这样的成就显示了超凡的数学创造力。在她17岁的时候,她和她的家庭来到圣彼德堡, 在那里柯瓦列夫斯卡娅说服了反对她的父亲,接受了微积分的家教课程。尽管她是一位女性,但是凭借如此的才能她本应该立即进入大学。遗憾的是,对于一位19世纪的俄罗斯女性来说,她没有这样的选择权。

以现代的观点看, 她对这些令人失望的事情的反映有些极端。在她18岁的时候, 在她的安排下,与一位准备前往德国的年轻学者进行了权宜结婚,她希望通过这样的婚姻得到进一步接受高等教育的机会。这个男人是弗拉基米尔·柯瓦列夫斯基,一位自愿参与这次“虚构婚姻”的古生物学者, 因为这对女性解放有利。他们两个人动身去了海德堡大学, 表面上维系着这样的婚姻,事实上各自从事着自己感兴趣的研究。

柯瓦列夫斯卡娅在海德堡一如既往表现得非常出色,所以1871年她瞄准了更高的目标:柏林大学,以及它令人尊敬的高级数学教授卡尔·维尔斯特拉斯(1815—1897)。下定了决心的柯瓦列夫斯卡娅安排了一次与这位世界著名学者的见面,恳求他的指导。维尔斯特拉斯给她提出了一些非常有挑战性的问题就把她打发走了,目的在于他不希望再见到她。

但是, 他还是再一次见到了她。一周后,柯瓦列夫斯卡娅手里拿着答案回来了。用维尔斯特拉斯的评价说,她的工作展示了“对维度的直觉天分……甚至在过去的学生或者层次更高的学生当中都是很少见的。”10她使当时世界最具影响力的数学家之一的这位怀疑论者加入到她的羡慕者行列中。

10Ibid., pp. 99-100.

由此,年老的维尔斯特拉斯和年轻的柯瓦列夫斯卡娅开始了一段长期的合作。她的精力和洞察力赢得了他真诚的尊敬,而且他还安排她与欧洲很多数学团体接触。在他的指导下,柯瓦列夫斯卡娅开始研究偏微分方程、阿贝尔积分以及土星环的动力学。由于这些成果, 1874年她获得了哥廷根大学数学博士学位。她是第一位获得现代大学博士学位的女性。

贯穿她的一生, 柯瓦列夫斯卡娅不仅对数学感兴趣,而且对社会和政治公平等议题也感兴趣。作为一名自由主义事业的支持者,她支持女权和波兰人的自由。当时她给一家激进报纸写文章。在她丈夫的帮助下, 1871年公社期间她秘密进入巴黎,当时这座城市被俾斯麦的军队包围。在这次冒险中,她的确被德国士兵击中了。到了巴黎, 她病倒了, 并受了伤,还与被包围的这座城市的激进派领导人取得了联系。这就是一个渴望实现她的社会信念的人物。

另外, 除了是科学家和革命者外, 她还是一位作家。柯瓦列夫斯卡娅写小说、诗歌、戏剧以及《童年的回忆》,这是一本自传式的童年记录。她是在俄罗斯渡过的青春,因此她见到过杜斯妥也夫斯基,在后来的生活中又认识了屠格涅夫、契科夫和乔治·爱略特。这位有社会责任感的数学家进入了著名的艺术圈子里。

总之, 索菲亚·柯瓦列夫斯卡娅拥有各种惊人的才能。聪明、果断、伶牙俐齿, 因此她被同时代人描绘成为“简直是光彩夺目。”11这里给出的一幅画像展示了她超凡脱俗的人格魅力,人们写了很多关于她的畅销书或电视连续剧。

11Ibid., p. 136.

如同所有连续剧一样, 她的故事以喜剧开场却以悲剧收场。尽管她的婚姻背景很特殊, 但是她与丈夫发展成真正的爱情,这一对夫妇于1878年有了一个女儿。但是五年后,一次失败的生意使他失去了大量金钱之后,沮丧的弗拉基米尔·柯瓦列夫斯基摄取氯仿自杀了。索菲亚成了寡妇和单身母亲。

幸运的是她还是世界一流的数学家。在维尔斯特拉斯的另一名弟子米特格-雷弗勒的热情帮助下,她被指定到瑞典的斯德哥尔摩大学任教。1889年她成为这一职位的终身教授, 这在数学界对女性来说也是第一次。

{%}

苏维埃邮票上的索菲亚·柯瓦列夫斯卡娅

在斯德哥尔摩的那段日子也并非没有困难。对女性固有的偏见又阻碍着她对进步事业公开而坚定的支持。那些保守的学者们因为对她的数学无可挑剔,转而指责她与一位著名的德国社会主义者接触。而维尔斯特拉斯和米特格-雷弗勒委婉建议柯瓦列夫斯卡娅应该采取更谨慎的政治态度。但是她没有这样做。

在数学这一边, 她被指名担任《数学学报》杂志的编辑,这是担任这一职位的第一位女性。她与埃尔米特和切比雪夫(我们在前一章遇到过他)等数学家联系,并成为俄罗斯数学团体和西欧数学团体的重要纽带。1888年柯瓦列夫斯卡娅获得法国科学院的鲍廷奖,获奖理由是她的论文《刚体绕固定点的旋转问题》,由此国际名声、报纸文章以及贺信迎面扑来。这样的喝彩声足以使她获得俄罗斯的皇家科学院的会员资格(作为一名女性,在她的祖国, 这样一个学术职位还不足以养活她)。

因此, 1891年充满希望的未来似乎就摆在这位著名人物的前面, 但是没有想到的是灾难突然降临。在去法国的途中, 柯瓦列夫斯卡娅咳嗽, 好像就是普通的感冒。但是, 当她返回到斯德哥尔摩时,在那样阴雨和寒冷的气候条件下, 她的身体状况变得更糟。返回家里,她变得太虚弱以至于无法工作。一次昏迷过后, 1891年2月10日,柯瓦列夫斯卡娅去世, 年仅41岁。

一如既往, 当这样一位天才永远地去了的时候,她给世人留下了惊叹、无尽的怀疑和没有实现的梦想。整个欧洲传来了它们的赞美之声, 随之而来的悲伤也是真诚的。我们无法知道柯瓦列夫斯卡娅还会为数学做出什么样的贡献,我们也无法知道这样的贡献会使这门学科中女性的地位提高多少。

柯瓦列夫斯卡娅这样的天才是罕见的, 但是自她去世后, 在本世纪, 数学领域中女性已经越来越普遍。同时, 随之出现了一个麻烦的问题:我们是否因排斥女性,把她们当作另类而有罪恶感呢?随着女性开始进入医学或法律等专业领域,很少有人谈及“女医生”或“女律师”。我们并不是说数学职业应该分成两组:数学家和女数学家。这当然不是我们的意图, 而且它也不是真实的现状。但是, 有这样的危险。

这是朱莉娅·罗宾森的观点。随着她声望的增大,当她进入美国科学院并获得麦克阿瑟奖的时候,罗宾森被认为是男性领地上获胜的女性。在一篇非常重要的短文中,她写道:“所有这些关心都是令人愉快的, 但也令人感到困惑。我就是一名数学家。我更希望仅仅因为我证明了一些定理或者解决了一些问题而被记住,而不是因为是第一位这样、那样的女性。”12对此的适当回应是:“阿门!”

12Albers et al.,More Mathematical People, p. 280.

尽管需要进一步根除女性所面对的不平等,我们有理由对实现罗宾森的愿望充满信心。随着很多偏见和障碍的消失,数学注册的女性人数已经开始增加。即使这个问题没有得到完全解决, 也不可否认进步的事实。我们希望, 在不远的将来,提出“女性在哪里?”这样的问题会被认为是完全没有必要的。

本文节选自《数学那些事儿》

 

{%}

《数学那些事儿》是一本短文集,每篇短文论述一个特定的数学主题,介绍了数学世界的伟大定理、难题、争论以及诸多不解之谜。在清晰和机智的描述中,作者带领你跨越五千年的历史,探索不同的主题,从最早的算术文献到近代的无穷级数难题以及无理数的怪异特征。

书中还介绍了许多数学大师的生活轶事,例如浮夸不逊的伯特兰•罗素、聪明好斗的伯努利兄弟以及天才索菲亚•柯瓦列夫斯卡娅等,数学家栩栩如生的形象跃然于纸上。

递归——“用自己定义自己”的奇妙逻辑

{%}

作者之一/ Ronald L. Graham(葛立恒)

著名数学家,美国加州大学圣迭戈分校计算机与信息科学专业教席(Jacobs Endowed Chair),AT&T实验室研究中心荣誉首席科学家,美国数学学会前任主席。Graham于1999年成为美国计算机学会会士,2003年获得美国数学学会的斯蒂尔终身成就奖,2012年成为美国数学学会会士。他还曾获得美国数学学会颁发的Lester R. Ford奖和Carl Allendoerfer奖以及其他众多奖项。

我们首先探讨一个称为河内塔的精巧智力题,让大家对递归有一个初步的印象。

河内塔

河内塔(The Tower of Hanoi)是由法国数学家爱德华·卢卡斯于1883年发明的:给定一个由8个圆盘组成的塔,这些圆盘按照大小递减的方式套在三根桩柱中的一根上。

{%}

我们的目的是要将整个塔移动到另一根桩柱上,每次只能移动一个圆盘,且较大的圆盘在移动过程中不能放置在较小的圆盘上面。

卢卡斯给这个玩具赋予了一个罗曼蒂克的传说,说的是一个大得多的婆罗贺摩塔(Tower of Brahma),它由64个纯金的圆盘堆放在三座钻石做成的方尖塔上。他说,上帝一开始把这些金圆盘放到了第一座方尖塔上,并命令一组牧师按照上面的规则把它们移动到第三座方尖塔上。据说牧师们夜以继日地工作,当他们完成任务时,那座塔就将坍塌,世界也将毁灭。

这个智力题有解,只是并非显而易见,不过只要稍加思考(或者此前看见过这个问题)就能使我们确信的确如此。现在问题来了:我们能做到的最好的解法是什么?也就是说,要完成这项任务移动多少次才是必须且足够的?

解决这样问题的最好方法是对它稍加推广。婆罗贺摩塔有64个圆盘,河内塔有8个圆盘,让我们来考虑一下,如果有 n 个圆盘将会怎样?

这样推广的一个好处是,我们可以大大简化问题。事实上,先研究小的情形是大有裨益的。移动只有一两个圆盘的塔十分容易,之后再通过少量的尝试就能看出如何移动有3个圆盘的塔。

求解问题的下一步是引入适当的记号:命名并求解。我们称 Tn 是根据卢卡斯的规则将 n 个圆盘从一根桩柱移动到另一根桩柱所需要的最少移动次数。那么,T1 显然是1,而 T2 =3 。

考虑所有情形中最小的情形还可以轻松得到另一条信息,即显然有 T0 =0,因为一个有 n=0 个圆盘的塔根本无需做任何挪动!聪明的数学家们不会羞于考虑小问题,因为当极端情形(即便它们是平凡的情形)弄得明明白白时,一般的形式就容易理解了。

现在让我们改变一下视角,来考虑大的情形:怎样才能移动一个大的塔呢?移动3个圆盘的试验表明,获胜的思路是将上面两个圆盘移动到中间的桩柱上,然后移动第三个圆盘,接着再把其余两个放到它上面。这就为移动 n 个圆盘提供了一条线索:首先把 n-1 个小的圆盘移动到一个不同的桩柱上(需要 Tn-1 次移动),然后移动最大的圆盘(需要一次移动),最后再把那 n-1 个小的圆盘移回到最大圆盘的上面(这需要另外的 Tn-1 次移动)。这样,至多需要 2Tn-1+1次移动就能移动 nn>0 )个圆盘了:

Tn ≤ 2Tn-1+1,n>0

这个公式用的是符号“ ≤ ”,而不是“ = ”,因为我们的构造仅仅证明了2Tn-1+1 次移动就足够了,而没有证明 2Tn-1+1次移动是必需的。智者或许能想到一条捷径。

还有更好的方法吗?实际上没有。我们迟早必须移动最大的那个圆盘。当我们这样做的时候,那 n-1 个小的圆盘必须已经在某根桩柱上,而这至少需要 Tn-1 次移动才能把它们放置到那儿。如果我们不太精明,则移动最大的圆盘可能会多于一次。但是在最后一次移动最大的那个圆盘之后,我们必须把那 n-1 个小的圆盘(它们必须仍然在同一根桩柱上)移回到最大圆盘的上面,这也需要 Tn-1 次移动.从而

Tn ≥ 2Tn-1+1,n>0

把这两个不等式与 n=0 时的平凡解结合在一起就得到

T0=0;

Tn=2Tn-1+1,n>0. ——式1

(注意,这些公式与已知的值 T1=1 以及 T2=3 相一致。关于小的情形的经验不仅能帮助我们发现一般的公式,而且还提供了一种便利的核查方法,看看我们是否犯下愚蠢的错误。在以后各章涉及更为复杂的操作策略时,这样的核查尤为重要.)

像式1 这样的一组等式称为递归式(recurrence,也称为递归关系或者递推关系)。它给出一个边界值,以及一个用前面的值给出一般值的方程。有时我们也把单独的一般性方程称为递归式,尽管从技术上来说它还需要一个边界值来补足。

我们可以用递归式对任何 n 计算 Tn 。然而,当 n 很大时,并没有人真愿意用递归式进行计算,因为太耗时了。递归式只给出了间接、局部的信息。得出递归式的解我们会很愉悦.这就是说,对于 Tn ,我们希望给出一个既漂亮又简洁的“封闭形式”,它使我们可以对其进行快捷计算,即便对很大的 n 亦然。有了一个封闭形式,我们才能真正理解 Tn 究竟是什么。

求解递归式

那么怎样来求解一个递归式呢?一种方法是猜出正确的解,然后证明我们的猜想是正确的。猜测解的最好方法是(再次)研究小的情形。我们就这样连续计算T3=2x3+1=7 ,T4=2x7+1=15 ,T5=2x15+1=31 ,T6=2x31+1=63。啊哈!这看起来肯定像是有

Tn=2n-1,n ≥ 0. ——式2

至少这对 n ≤ 6 是成立的。

数学归纳法(mathematical induction)是证明某个命题对所有满足 nn0 的整数 n 都成立的一般方法。首先我们在 n 取最小值 n0 时证明该命题,这一步骤称为基础(basis);然后对 n > n0,假设该命题对 n0n-1 之间(包含它们在内)的所有值都已经被证明,再证明该命题对 n 成立,这一步骤称为归纳(induction)。这样一种证明方法仅用有限步就得到无限多个结果。

递归式可以用数学归纳法完美地确立起来。例如在我们的情形中,式2 很容易由式1 推出:其基础是显然的,因为 T0=20-1=0。而如果我们假设当 nn-1 取代时式2 成立,则对 n>0 用归纳法就得出

Tn=2Tn-1+1=2(2n-1-1)+1=2n-1

从而式2 对 n 也成立.好的!我们对 Tn 的探求就此成功结束。

牧师的任务自然还没有完成,他们仍在负责任地移动圆盘,而且还会继续一段时间,因为对 n=64 有 264-1 次移动(大约 1.8x1019次)。即便是按照每微秒移动一次这个不可能实现的速度,也需要5000多个世纪来移动婆罗贺摩塔.而卢卡斯的智力问题更切合实际,它需要 28-1=255 次移动,快手大概四分钟就能完成。

河内塔的递归式是在各种应用中出现的诸多问题的一个典范。在寻求像 Tn 这样有意义的量封闭形式表达式时,我们经过了如下三个阶段。

(1) 研究小的情形。这有助于我们洞察该问题,而且对第二和第三阶段有所帮助。

(2) 对有意义的量求出数学表达式并给出证明。对河内塔,这就是递归式1 ,它允许我们对任何 n 计算 Tn(假设我们有这样的意向)。

(3) 对数学表达式求出封闭形式并予以证明。对河内塔,这就是递归解2 。

第三阶段是需要反复集中探讨的。实际上,我们将频繁跳过第一和第二阶段,因为我们以给定一个数学表达式作为出发点。即便如此,我们仍然会深入到各个子问题中,寻求它们的解将会贯穿所有这三个阶段。

我们对于河内塔的分析引导出了正确的答案,然而它要求“归纳的跳跃”,依赖于我们对答案的幸运猜测。例如,我们将会看到,在递归式1 中方程的两边加上1可以使其变得更简单

T0+1=1;

Tn+1=2Tn-1+2,n>0.

现在如果令 Un=Tn+1 ,那么就有

U0=1;

Un=2Un-1n>0.

不必是天才,也能发现这个递归式的解正是 Un=2n,从而有Tn=2n-1。

河内塔程序

前面所示的“解出 n 层河内塔”的步骤,已经相当于程序的伪代码了。因此,这里我们用 C 语言编写河内塔解法的程序也就相当简单了。

河内塔解法的程序

#include <stdio.h>
#include <stdlib.h>

void hanoi(int n, char x, char y, char z);

void hanoi(int n, char x, char y, char z)
{
    if (n ==0) {
        /* 什么也不做 */
    } else {
        hanoi(n-1, x, z, y);
        printf("%c->%c, ", x, y);
        hanoi(n-1, z, y, x);
    }
}
int main(void)
{
    hanoi(6, 'A’, 'B', 'C');
    return EXIT_SUCCESS;
}


该程序会输出“ 6 层河内塔”的解决步骤,具体如下。

A->C, A->B, C->B, A->C, B->A, B->C, A->C, A->B,
C->B, C->A, B->A, C->B, A->C, A->B, C->B, A->C,
B->A, B->C, A->C, B->A, C->B, C->A, B->A, B->C,
A->C, A->B, C->B, A->C, B->A, B->C, A->C, A->B,
C->B, C->A, B->A, C->B, A->C, A->B, C->B, C->A,
B->A, B->C, A->C, B->A, C->B, C->A, B->A, C->B,
A->C, A->B, C->B, A->C, B->A, B->C, A->C, A->B,
C->B, C->A, B->A, C->B, A->C, A->B, C->B,

数一下,确实是 63 次。

扩展递归思维

假设现在碰到了一个难题。我们十分清楚“简单问题易解,复杂问题难解”的道理。所以这时,我们要联想到河内塔,进行如下思考。

“能将复杂问题转换为较为简单的同类问题吗?”

这就是递归的思维方式。

对于河内塔来说,就是将 n 层河内塔转换为 n-1 层河内塔的问题,即在问题中找出递归结构。虽然暂未解决给定的问题,但是要找出同类的简单问题,并将它当做“已知条件”来运用。

如果找到了这种递归结构,接下来就根据递归结构建立递推公式。

找出递归结构并建立递推公式,是相当重要的一环。如果能够总结出解析式自然最为便捷,不过若找不到解析式,只建立递推公式也是非常有用的。因为它是得出具体数字的线索,同时也能帮我们把握问题的本质。

切比萨

我们的第二个范例有更多的几何特色:用一把比萨刀直直地切 n 刀,可以得到多少块比萨饼?或者说得更有学术味儿点:平面上 n 条直线所界定的区域的最大个数 Ln 是多少?这个问题于1826年被一位瑞士数学家斯坦纳首先解决。

我们再次从研究小的情形开始,记住,首先研究所有情形中之最小者。没有直线的平面有1个区域,有一条直线的平面有2个区域,有两条直线的平面有4个区域(每条直线都在两个方向无限延伸):

{%}

我们一定会想到有 Ln=2n,当然!增加一条新的直线直接使区域的个数加倍。遗憾的是,这是错误的。如果第 n 条直线能把每个已有区域分为两个,那么就能加倍。它肯定能把一个已有区域至多分成两个,这是因为每一个已有区域都是凸的(一条直线可以把一个凸区域分成至多两个新区域,这些新的区域也将是凸的)。但是当增加第三条直线(图中的那条粗线)时,我们很快就会发现,不论怎样放置前面两条直线,它只能至多分裂3个已有的区域:

{%}

从而 L3=4+3=7 是我们能做到的最好结果。

略加思考之后,我们给出适当的推广。第 nn>0 )条直线使得区域的个数增加 K 个,当且仅当它对 K 个已有区域进行了分裂;而它对 K 个已有区域进行分裂,当且仅当它在 K-1 个不同的地方与前面那些直线相交。两条直线至多相交于一点,因而这条新的直线与那 n-1 条已有直线至多相交于 n-1 个不同的点,故必定有 Kn .我们就证明了上界

LnLn-1+n, n>0

此外,用归纳法容易证明这个公式中的等号可以达到。我们径直这样来放置第 n 条直线,使得它不与其他直线中的任何一条平行(从而它与它们全都相交),且它不经过任何已经存在的交点(从而它与它们全都在不同的点相交)。于是该递归式即为

L0=1;

Ln=Ln-1+n, n>0

核查一下就发现,已知的L1L2L3的值在这里完全正确,所以我们接受这一结果。

现在需要一个封闭形式的解.我们可以再次来玩猜测游戏,但是1,2,4,7,11,16,…看起来并不熟悉,故而我们另辟蹊径。我们常常可以通过将它从头到尾一直“展开”或者“解开”来弄清楚递归式,如下

{%}

换句话说,Ln 比前 n 个正整数的和 Sn大1。

Sn 不时地冒出来,故而值得对较小的值做出一张表.这样,我们下次看到它们时,或许会更容易辨认出这些数:

{%}

这些值也称三角形数,因为 Sn 是一个有 n 行的三角形阵列中保龄球瓶的个数。例如,通常的四行阵列有 S4=10个瓶子。

为计算Sn,我们可以利用据说是高斯在1786年就想出来的一个技巧,那时他只有9岁(阿基米德也曾在他关于螺旋线的经典著作的命题10和命题11中用到过):

{%}

只要把 Sn 和 它反向书写相加,就能使得右边 n 列的每一列中的诸数之和都等于 n=1 。简化即嘚

Sn=n(n+1) / 2, n≥0

好的,我们就有解答

Ln=n(n+1)/2 + 1, n ≥ 0.——式3

作为专家,我们或许很满意于这个推导,并认为它是一个证明,尽管在做展开和合并时我们付出了一点点努力,但是学数学的学生应该能够适应更严格的标准,故而最好用归纳法构造出一个严格的证明。归纳法的关键步骤是

{%}

现在对于封闭形式3 就不再有疑问了。

我们谈到了“封闭形式”而没有具体说明它的含义。通常,它的含义是极其明晰的。像式1 这样的递归式不是封闭形式的,它们用其自身来表示一个量;但是像式2 和式3 这样的解是封闭形式的。像 1+2+...+n 这样的和不是封闭形式——它们用“…”企图蒙混过关,然而像 n(n+1)/2 这样的表达式则是封闭形式的。我们可以给出一个粗略的定义:如果可以利用至多固定次数(其次数与 n 无关)的“人人熟知的”标准运算来计算量 f(n) 的表达式,那么这个表达式是封闭形式的。例如, 2n-1 和 n(n+1)/2 都是封闭形式,因为它们仅仅显式地包含了加法、减法、乘法、除法和幂指运算。

简单封闭形式的总数是有限的,且存在没有简单封闭形式的递归式。当这样的递归式显现出重要性时(由于它们反复出现),我们就把新的运算添加到整套运算之中,这可以大大扩展用“简单的”封闭形式求解的问题的范围。例如,前 n 个整数的乘积 n! 已经被证明是如此重要,故而现在我们都把它视为一种基本运算.于是公式 n! 就是封闭形式,尽管与它等价的 1×2×...×n 并非是封闭形式。

阶乘

如下,我们递归地定义阶乘。这可称为阶乘的递推公式。这样的定义既能明晰 0! 的值,又能省略上面式子中的“…”部分。

n! = 1 (n=0时)

n! = n×(n-1)! (n=1,2,3...)

之所以将它称作递归定义是因为“它使用了阶乘(n-1)! 来定义阶乘n!”。你能发现定义中出现的递归结构吗?

该式虽然使用阶乘自身来进行定义,但却不会循环无解。对于 0 以上的任一整数,n! 的定义都很明确,因为使用了比 n! 低一层的(n-1)! 来定义n!

例如,从阶乘的递归定义出发来看一下 3!。通过定义可知

3! = 3×2!

再根据递归定义展开右边的 2! 可得

2! = 2×1!

继续根据递归定义展开1! 可得

1! = 1×0!

最后根据“ n =0 时”的定义可得

0! = 1

至此,大家理解为什么将 0! 定义为 1 了吧。若 0! 不是 1,就无法顺利进行上述递归定义。

平面上直线变折线

现在,我们简要谈谈平面上直线问题的一个变形:假设我们用折线代替直线,每一条折线包含一个“锯齿”。平面上由 n 条这样折线所界定的区域的最大个数 Zn 是多少?我们或许期待 Zn 大约是 Ln 的两倍,或者也可能是它的三倍。我们看到

{%}

从这些小的情形出发并稍加思考,我们意识到,除了这“两条”直线不经过它们的交点延伸出去而使得区域相融合之外,一条折线与两条直线相似:

{%}

区域2、3和4对于两条直线来说它们是不同的区域,但在一条折线的情形下是单独的一个区域,于是我们失掉了两个区域。然而,如果放置得当——锯齿点必须放在它与其他直线的交点“之外”——那就是我们失去的全部,也就是说,对每条折线我们仅仅损失两个区域。从而

Zn=L2n-2n=2n(2n+1)/2 +1-2n=2n2-n+1, n ≥ 0. ——式4

比较封闭形式3 和 4 ,我们发现对于大的 n

Ln ~ 1/2 n2,

Zn ~ 2 n2;

所以用折线所能得到的区域是用直线所能得到的区域的大约四倍。(当 n 很大时,我们用“ ~ ” 来分析整数函数的近似性状。)

本文参考图书《具体数学》《程序员的数学》

 

{%}

《具体数学》由当今顶级数学家和计算机科学家合著的经典著作,自1990年出版以来经久不衰,并被世界多所知名大学采纳为教材,是当代计算机科学方面的一部重要著作。

书中讲解了许多计算机科学中用到的数学知识及技巧,教你如何把一个实际问题一步步演化为数学模型,然后通过计算机解决它,特别着墨于算法分析方面。其主要内容涉及和式、整值函数、数论、二项式系数、特殊的数、生成函数、离散概率、渐近式等,都是编程所必备的知识。另外,本书包括了六大类500 多道习题,并给出了所有习题的解答,有助读者加深书中内容的理解。

{%}

《程序员的数学》向程序员介绍了编程中常用的数学知识,借以培养初级程序员的数学思维。读者无需精通编程,也无需精通数学,只需具备四则运算和乘方等基础知识,就可以阅读本书。

书中讲解了二进制计数法、逻辑、余数、排列组合、递归、指数爆炸、不可解问题等许多与编程密切相关的数学方法,分析了哥尼斯堡七桥问题、高斯求和方法、河内塔、斐波那契数列等经典问题和算法。引导读者深入理解编程中的数学方法和思路。

既适合程序设计人员,也适合数学爱好者阅读。

编程也无法解决的问题

作者/ 顾森

网名Matrix67,北京大学中文系应用语言学专业学生,数学爱好者。

2005年开办数学博客,至今已积累上千篇文章,已有上万人订阅。长期为各类科普杂志供稿,从事中学数学教育工作多年。

{%}

程序员可以利用计算机解决很多问题。按照指定的语法规则编写代码,把想法“告诉”计算机;再在编译器中编译代码,生成一个个各有所能的程序。你可以随心所欲地制作各种搞怪的小程序:寻找并输出2010年到2020年中所有“黑色星期五”的日子,读取用户输入的手机号码并输出它是不是质数,读取用户输入的一篇文章并输出出现频率最高的四字词……这听上去似乎是一件相当有乐趣的事情。不过,无论计算机如何发展,都存在本质上无法解决的问题,程序员也有自己无法解决的苦恼。

不可解问题

不可解问题是比我们想象中更难的概念,必须谨慎处理。

所谓不可解问题,并非“花大量时间求解的问题”,也不是“本来就无解的问题”,更不是“目前谁都不知道解法的未解决的问题”。

不可解问题是“原则上不能用程序来解决的问题”。也可以说是“不包含在‘程序可解决问题的集合’中的问题”。没人能写出解决不可解问题的程序。它就是如此不可思议!

那么不可解问题,即“不能写成程序的函数”存在吗?这指的不是目前尚不明确是否能写,而是指肯定有还是肯定没有“不能写成程序”的函数。

停机问题

最奇怪的幻想总是来自于最奇怪的需求。程序员一定有过这样的经历:看到自己编写的程序运行了半天都还没有任何结果,于是开始纠结,到底是再等一会儿呢,还是强行终止程序,检查一下程序代码有没有写错。犹豫了半天决定杀掉进程,之后又检查了半天竟然发现程序没有写错。于是开始后悔,早知道程序没有死循环的话,刚才就多等一会儿了。此时,你会突然开始幻想,有没有什么编译器能够事先告诉你你的程序是否会无限运行下去?

注意,这里有一个假设:我们手里的计算机是一台理想的计算机。它拥有无穷无尽的内存,不会溢出,不会越界,可以存储任意大的、任意精确的数字。此时,“无限运行下去”就不仅仅是指“令 a=1 并不断把 a 替换为 a2 直到a>100”这样的“死循环”了,状态永不重复的程序也有可能永远停不下来。比方说,“令 a=100 并不断把 a 替换为a+1 直到 a<10 ”,这段程序虽然不会重复之前的状态,但也不会停下来。

在这样的假设下,编程判断一段代码是否会无限执行下去将会相当地困难。但我们仍然不排除会有某个天才程序员想出了超级复杂的算法,耗时五年为他心爱的编译器写出了这样一个强大的插件。为什么不可能呢?这个东西看上去似乎比时光旅行机更现实一些。或许我们会在某个科幻电影中看到,一个程序员在漆黑的屏幕上输入几个数,敲了一下回车,然后屏幕上立即用高亮加粗字体显示:“警告:该输入数据会导致程序无限运行下去,确定执行?(Y/N)”如果有一天,这一切真的成为了现实,那么你能利用这个玩意儿来做些什么实用的、有价值的事情?如果我说你能靠这玩意儿发大财的话,你相信吗?

永远不要说什么“看看当年我参加计算机竞赛时第二题的第四个数据点是不是真的因为死循环才超时的”、“看看上个星期做完项目跟客户演示时为什么半天没有输出”之类的话。对于个别程序和数据的组合,有时是可以判断能否结束运行的。但却做不到给定任意程序和数据,都可以判断能否结束运行。根本写不出这种具有普遍性的程序。

万能证明法

如果可以编写出判断停机问题的程序,我一定会用点儿别人想不到的雕虫小技干出一番惊天动地的大事。

我上来就先写一个哥德巴赫猜想(任一大于3的偶数都可以写成两个质数之和)的验证程序。我写一个程序,让它从小到大枚举所有的偶数,看是不是有两个质数加起来等于它。如果找到了,继续枚举下一个偶数,否则输出这个反例并结束程序。然后编译该程序。这个编译器不是可以预先判断我这个程序能否终止吗?如果编译器说我这个程序会无限执行下去的话,我岂不是相当于证实了哥德巴赫猜想吗?

GoldChecker (n)
{
    while (n > 0) {
       < 判断n 是否能写成两个质数之和 >
       if( <不能写成两个质数之和 >) {
          < 输出n 后结束程序>
       }
       n = n + 2 ;
    }
 }

写出上面的GoldChecker本身并不难。

现在调用HaltChecker(GoldChecker, 4),结果会怎么样呢?如果结果为true,那就意味着“将4 输入GoldChecker,在有限时间内程序会结束运行”,即存在不能写成两个质数之和的n。这就否定了哥德巴赫猜想。而如果结果为false,那就表明“将4 输入GoldChecker,在有限时间内程序不会结束运行”,由此可得哥德巴赫猜想是正确的。

不管怎样,我都将成为解决哥德巴赫猜想的第一人,在数学史上留下自己的名字。接下来呢?把刚才的程序代码改成孪生素数搜索器,再用编译器检验一下,看看是不是真的有无穷多个孪生素数。梅森素数是否有无穷多个,这也是数论中长期以来悬而未决的难题。不过现在看来,我也能不费吹灰之力就把它解决了。还记得我们在讲“最折磨人的数学未解之谜”时提到的问题吗?写一个“证明程序”也只是几分钟的事情,而且还能拿走埃尔德什提供的500美元奖金呢。数学上的未解之谜多着呢,我永远不愁没事做。1984年,马丁•拉巴尔(Martin LaBar)询问是否能用9个不同的平方数构成一个 3x3 的幻方,这个问题的奖金目前已经累积到了100美元加100欧元再加一瓶香槟。网上搜索“数学未解难题”,看看哪些问题是离散的,其中又有哪些问题是有悬赏的,写几个程序就可以把它们统统解决……

还是从幻想中清醒过来吧,判断一个程序能否无限运行下去的程序是否真的存在我们还不知道呢。不过仔细回想一下上面的讨论,你会意识到这种程序的存在该是多么不可思议。即使这样的程序真的存在,实现它的难度也绝对不亚于解决上述任何一个数学猜想,不然的话大家都转而向这个神奇的“万能证明方法”进攻了。

停机问题的证明——反证法

而事实上,计算机科学家们已经从理论上证明了,这种程序是永远不可能实现的。在计算机理论中,该结论可以叙述为:停机问题是一个不可解的问题。停机问题不可解的证明并不复杂,并且非常有趣。用反证法,假设我们有一个满足要求的程序P(a,b),它可以预先判断出运行代码 a 并读入数据 b 之后程序是否会终止。那么,我们可以编写这样一个程序Q,它首先读取输入数据并把它记做m ,然后调用P(m,n)并根据其返回的结果执行不同的任务:如果P(m,n )返回的结果是“不会终止”,立即退出程序;否则,任意执行一个死循环任务,比如“令 a=1 并不断把 a 替换为 a2 直到a>100”。现在,运行程序Q,然后把程序Q本身的代码作为输入数据传进去,于是程序Q调用P(m,n )时,实际上问的是“运行程序Q并输入Q的代码后会发生什么”,也就是询问它自身的命运。但根据程序Q的规则,如果P(m,n )认为该程序不会终止,Q就会立即退出;如果认为P(m,n )该程序总有终止的一刻,程序Q反而陷入循环。于是,P(m,n)并没有成功预测此时Q的命运,这说明停机问题是永远无法解决的。

我们刚才那些美好的梦想被这一个简短的证明撕成了碎片。

永远不要小瞧人类的想象力。对“万能证明方法”的进攻并没有就此结束。虽然判断一段代码运行后是否会终止的程序是不存在的,但这个“万能证明方法”的思路是非常值得借鉴的。下面,我给你一个绝对存在的东西,它同样可以用于我们的“程序证明”。它就是指定的编程语言中任意一段代码运行后最终会停止下来的概率。假如说这种编程语言有种字符 p(包括代码结束的标识符共种 p+1 ),长度为 n 的代码中 T(n) 有个不会无限运行下去,那么我们定义这个概率就是 {%} 。考虑两种极端的情况:如果所有代码都永不终止,那么这个概率值为 0;如果所有代码运行后最终都能停下来(包括语法错误根本不能编译的情况),那么概率为 {%},其中 pn-1 是除去那个结束符号后所有可能的 n-1 位代码的数量。利用等比数列求和公式容易得出这个值等于1。当然,在实际情况下,这个概率值是一个介于0和1之间的确定的数。

有了这个概率之后,我们就无敌了!我们可以故技重施,写一个哥德巴赫猜想验证程序。假如这个程序的长度为L。注意到 {%} ,当 K 足够大时必然有某个时刻 {%} 比小 {%} 。我们再用一个程序来生成所有可能的长度不超过的代码。然后便是壮观的一幕:让所有这 {%} 个程序同时运行!这里面,有些程序的代码语法有错,根本就不能通过编译;有些程序运行后屏幕一闪就退出来了;有些程序可能得等个好几天才能退出;当然也有将要无限运行下去的程序。不过可以肯定的是,受到上面那个概率值的限制,最终停止下来的程序是有一个上限的。随着越来越多的程序停止下来,总有某个时刻会达到这样一种状态:终止的程序所占的比例与我们那个概率值的误差不到 {%} (因为我们没有考虑的那些代码即使全部都会终止也只占 {%} 的分量,而值的选择保证了这个分量不足 {%} ),此时只要再有一个长度不超过L的程序终止,实际比例(将增加至少 {%} )就超过那个概率了。这时,我们就可以肯定,到时候还没有停止的程序必然将无限运行下去。如果届时我们的哥德巴赫猜想还没找出反例,这就意味着这个程序永远找不出反例了,哥德巴赫猜想也就得到了证实。

或许,这个工程确实有点庞大,需要耗费大量的时间和金钱。不过,为了证明那么多悬而未解的数学之谜,投入再多的时间和资金也值得啊!我们还可以采取分布式计算的办法,邀请全球的计算机一起来参与计算!那么,为什么不这样做呢?真实的情况到底如何呢?

这或许会有些不合常理:我们上面提到的那个概率值是一个“不可计算数”(uncomputable number)。它是一个可以严格定义出来并且也确实存在的数,但我们永远无法计算出它的值(即不存在某种算法能够给出小数点后任意多位的数字)。这个概率值是有名字的,它叫做蔡廷常数,是以数学家和计算机科学家格里高里•蔡廷(Gregory Chaitin)的名字命名的。可以证明,蔡廷常数确实是不可计算的。不妨反过来想,假如我们有一个能够给出蔡廷常数小数点后任意多位的值的算法,那么我们就能用上面那种“等足够多的程序终止”的方法判断出一个代码长为的程序是否会无限运行下去,这相当于有了一个解决停机问题的算法。但我们前面已经证明了,停机问题是不可解的,因此可以肯定地说,算出蔡廷常数一定是不可能的。

本文节选自《思考的乐趣》

 

{%}

《思考的乐趣》基本不涉及高深的数学理论,但是内容新颖、时尚,既有与现实生活联系紧密的应用型话题,又有打通几何、代数联系的富有启发性的讨论,还间或介绍了一些著名数学难题的最新研究进展,信息十分丰富。