我的那些数学玩具们——默比乌斯带

Möbius Strip,我不太喜欢“默比乌斯带”这个翻译,因为在我认识它时,我看到的说法都是“莫比乌斯圈”或“梅比乌斯圈”,不过其实早在1993年,全国科学技术名词审定委员会就规定了这个词的正规翻译是“默比乌斯带”,所以……

一、魔术

魔术师拿起一条纸带,把它粘成一个环,从中间撕开,这个纸环变成了一个更大的纸环。再撕一下,哈哈,大纸环变成了两个套在一起的纸环。

很简单,显然是在粘纸环时做了一点点手脚,把纸带扭曲了一下,把它粘成了一个默比乌斯带。默比乌斯带一个最明显的特性就是它只有一个面,而且从中间撕开的时候会变成一个大圈圈,估计这一点大家都知道了吧。

这个“一个面”的特性有一个很好的用处,就是在做传动皮带的时候,如果把皮带做成默比乌斯带,就是让皮带得到更充分的利用。如果用在磁带上,也许就可以更有效的利用带基,也可能免去翻面的麻烦。多废话罗嗦一句,不要误解这一点,现在的录音磁带的翻面只是用磁带的两个不同磁道,可不是用了正反面啊。

二、四维空间的臆想

小时候总是喜欢胡思乱想,四维空间这个似乎很神奇的名词也不断的被误解和歪曲。但小孩子总是对这种乱想乐此不彼,所以乱想也就放在这里做为“玩具”吧。

一般人是不能想象四维空间的,因为我们所能认识到的世界是三维的,我们只能理解小于等于三维的东西。零维是点,一维是线,二维是面。任何一维,只要在不属于它的维度上运动起来就让维度升高了一级。把高维的东西放到低维空间去就更简单了,投射即可。所以如果我们能帮助二维世界的生物理解三维,我们也许就可以理解四维了。

默比乌斯带就是帮助二维空间理解三维的一个好工具。默比乌斯带本身是二维的,它就是一个面,唯一的问题在于它被在高维的空间中扭曲了一下。

把一匹三维的马投影到二维空间,如果从正侧面投影的话,可能有两种结果,一种是马头朝左,一种是马头朝右,这两种二维马是无法相互转换的,除非把它拿到三维空间来翻个面,再放回二维空间去。有了默比乌斯带,情况就不一样了,一匹马只要沿着默比乌斯带走一圈,再把自己从倒立姿势变换正立,它就成功的把自己变成了另一个朝向的马。

小时候我一度没有理解这个故事,我剪了一匹纸马,扶着它在默比乌斯带上走,发现走回原地时,它还是没有发生变化。错就错在我在用三维的眼光去看二维的事物,我的纸马不是在默比乌斯带这个二维面上走,而是在它的外面走,所以走回原地时,实际上已经走了两圈了。用纸做的默比乌斯带是有厚度的,是三维的,而真正意义上的默比乌斯带是一个曲面,没有厚度,马是嵌在这个面里面走,而不是在它外面。

理解了这个,我们就可以继续臆想四维空间了,如果在四维空间在帮助三维空间做一个扭曲,以后生产手套的厂家就高兴了,他们的生产不用区分左右手了,只要生产一种,然后拿一半去扭曲的空间转一圈,回来翻个面,另一种手套就做好了。

三、变色(变数字)的六边形

聊了很多,今天真正的玩具才刚刚登场。这个玩具我从小学做到研究生毕业,每次都还能引吸一些人来研究。不过后果常常是把我做好的玩具搞坏了 :-(

这个玩具很简单,就是把一个默比乌斯带压压扁。

说得容易做的不容易,因为这个“压压扁”要压得恰当好处才行,所以还是按图做比较好。

三种变换制作图纸

三种变换制作图纸

剪一条2-4厘米宽的纸带,画上10个正三角型,如图在两面分别写上数字(或相同数字涂上相同的颜色)和标记,然后沿红线和蓝线折起来,红线表示陷下去,蓝线表示鼓起来。比如在上面的图中,折好后2和*、2和2都是面靠面,1和3是背靠背。然后,把打*号的面粘起来,需要把纸带交叉一下才能让*号和*号粘起来,不好描述,自己体会一下吧,反正粘好以后就是个压扁的默比乌斯带。

这时正面是一圈一致向内的1,反面是东倒西歪的3,而2就不见了。我们的目标就是要把1、2、3分别变出来,而且最好要求是一致向内。

怎么变呢?我实在是不太会描述,有兴趣的朋友不妨自己试一试。我把我的描述写在这篇文篇的回复中,想看的人看看吧。

三种变换很单调,这个玩具还可以很轻松的扩展成六种、九种、十二种或更多的变换。做法不难,首先算一下要画多少个三角型,公式显然是3*N+1个,因为N种变化需要6*N个三角面,纸是双面的,所以只要3N个,加上的一个多了两个面是用来粘贴的。先把这条纸带“拧麻花”,六种变化的拧一次,九种的拧两次,以此类推,就可以得到一条看上去只10个三角面的纸带,于是就可以按三种变换时的做法把它折成最终的玩具了。还是以六种变化的为例画个图吧:

“拧麻花”示意图

“拧麻花”示意图

所谓“拧麻花”就是沿红线折叠啦,折完以后纸带就成为跟前面一样看起来是10个三角形的样子了,不过在具体做最后一步时可能需要发挥一下主观能动性,思考一下怎么叠才是合理的,这个只能意会不能言传了。纸带上标的数字我也不知道要怎么标了,我自己都是做好以后再一边玩一边标上去的。

成品的六种变换的玩具

成品的六种变换的玩具

下面是一些经验之谈:用的纸要尽量薄但有韧性,纸带宽度和正三角形的60度角一定要精确。与其画N个三角形出来不如只画一个,然后把剩下的直接折出来,又快又精确。6种变换的是最有性价比的,因为纸是有厚度的,变换越多折得次数越多,很厚的时候就不好折了。要知道“一张无论多大的纸都最多可以对折7次”左右。

有关这个玩具的数学原理?抱歉,我真不知道。迄今为止我只在两本杂志上看到过这个玩具,一本只讲了最简单的3种变换的,另一本介绍了推广到N种颜色的,在网上我还没有看到过任何相关的介绍。如果你知道有相关资料或原理介绍,希望能让我知道一下。

什么时候玩具会搞坏?当你发现一个面上出现不同的数字(颜色)的时候。为什么会坏?折来折去其实都是在做变换,从拓扑学看,虽然对于这个封闭的曲面来说怎么折它在拓扑上都是等价的,但表现出来可能会是不同的形状,如果正好扭到了一个不正确的状态,玩具就坏了。虽然理论上一定可以再把它折回到正常状态,在实践中,还是把它剪开再重新折好贴起来才更有性价比。

我的那些数学玩具们——二进制篇

作为所谓技术青年,我向来认为自己爱好理科,但从高中开始,我的理科成绩就一直是烂得可以,很奇怪。不过大学毕业的那段时间里,我无意中领会到我的兴趣爱好的培养都跟一本从小看到大的科普书有关,该书的统一书号是13031-841,嗯,1978年的中国书上还都没有ISBN的。今天不讲这个书,以后有机会再讲。今天讲玩具。因为最近很偶然的发现自己从小就对很多数学玩具有很深的兴趣,这些玩具对我的成长和学习也起到过不少的作用。

二进制在我玩过的数学玩具中占有很重要的一席之地,今天先聊聊这个。二进制中经常遇到2^N或2^N-1这样的值,所以这里说的就是广义上跟二进制相关的东西,包括几何级数。

一、猜年龄(属相、数字、etc)

魔术师拿出一把卡片,上面写有乱七八糟的数字,请观众找出包含自己年龄数字的那些卡片,然后魔术师就可以猜出观众的年龄。

这个魔术的演化版本实是在数不胜数,各种各样的道具也是层出不穷。我自己的做过的就不下十种,所谓的魔法卡片、魔法书什么的,各式各样但都万变不离其综。

这个游戏的原理现在来看实在是不值得一提。上网搜了一下,发现不知道这个游戏原理的人原来还不在少数……所以还是简述一下原理:

给卡片编上号,比如四张卡片,编号4,3,2,1。然后把数字转换成二进制,对于数字13=1101B,就在二进制位为1(即编号4,3,1)的卡片上写出上这个数字13。这样如果有人抽出了4,3,1这三张卡片,你马上可以知道他想的数字是2^3+2^2+2^0=13。……好像讲得太技术了,估计明白的人本来就明白,不明白的看了也没明白,算了,就这样吧……

这个魔术原理太简单,所以还是要多用一些障眼法来实现比较好的效果,猜属相就是一个比较好的演化版本,这里就送大家一套猜属相的卡片吧:

猜属相卡片

猜属相卡片

ABCD四卡分别编号8421,找出哪几张就把对应编号相加,得出结果后减2,然后从依次排列的十二生肖中找到这个编号对应的动物即可。我的属相在ABD卡上出现,所以编号是8+4+1-2=11,所以属Dog。

有这些玩具的基础,若干年后看到两个所谓的面试智题力,就可以轻松的微微一笑,太简单了。

– 你让工人为你工作7天,给工人的回报是一根金条。金条平分成相连的7段,你必须在每天结束时给他们一段金条,如果只许你两次把金条弄断,你如何给你的工人付费?

– 现有1000个苹果,10个盒子,问各个盒子内应该分别放入多少个苹果,才能使得用户要买任意1至1000之间的一个苹果数,都可以给他(卖的时候是整个盒子卖,不能拆盒子的包装)。

二、九连环

其实九连环这个东西我一直没有玩过,只是从那经典的《十万个为什么》数学卷上了解到这个伟大的古老的中国玩具。

九连环

九连环

不过在我觉得“爸爸是万能的”的年纪,我让爸爸给我做过一些类似的玩具,其中一个宝塔环就是九连环有点相似,找不到完全一样的图片了,找到个类似的,爸爸做的比这个漂亮而且精致 :-)

宝塔环

宝塔环

在解宝塔环的时候,从上到下N个环中,如果要摆脱第N个环的束缚,就需要先把N个环套上,再解开所有N-1个。所以每解一层所需要状态变化都是上一层的2倍减1次。解开N个环需要经历的总的状态数是2^(N+1)-1。

而九连环里的二进制就更是复杂多了,九连环中的每个环都有上下两种状态,如果把这两种状态用0/1来表示的话,这个状态序列就会形成一种循环二进制编码(格雷码)的序列。所以解决九连环问题所需要的状态变化数就是格雷码111111111所对应的十进制数341。

九连环和宝塔环的状态序列的变化特征是每次状态变化都只会改变一个二进制位,在数字电路中这样的变化会比较平稳,而太多位的变化可能会带来很大的尖峰电流脉冲,所以用格雷码可以减少电路出错的可能性。

三、棋盘摆米和汉诺塔

印度古老传说中的国际象棋棋盘摆米的故事算不上是一个玩具,不过几何级数的神奇力量我也确实是实实在在的在数米粒的过程中体会到的。

要算是玩具的话,还是汉诺塔这个折磨过所有初学编程者的东东更好玩一些。小时候的我实在是没有那么强的动手能力去做三根细针和大小不一的圆盘,不过撕点大大小小的纸片,并在上面标注一下数字表示大小还是我可以做到的,于是这个玩具就被我这样粗制滥造出来了。

不知道是不是对二进制天生的敏感,相比上面那个宝塔连环,这个玩具似乎并没有为难到我,基本上这个玩具只陪伴了我不到一个小时的时间,我就发现,它跟棋盘摆米原来是一样的无聊……不过话说回来,刚开始的几分钟还是挺有意思的,所以还是拿这个简陋的玩具在朋友之间炫耀了一把。

高中的时候准备NOI竞赛的时候,汉诺塔做为学习递归的必修课倒是小小折磨了我一把,我那时对形参和实参实在是有点理解不了(我是BASIC出身,半路浅尝C,再半路学Pascal)。不过这段经历让我在大一C语言期末考试前颇是得意了一把,做为一道必考的题目,考试前一天我至少给不同的人讲了十遍汉诺塔的原理,我记得我那天嗓子有点哑……

对于汉诺塔的递归程序,不知道有没有人尝试过去画它的(传统的)流程图,一定会失败的,传统的流程图完全没有办法去表达递归的思路。不过有一种图示可以比较好的画出递归的过程,这种流程图是我在我这辈子看的第一本英文技术书上看到的:Data Structure & Program Design in C,看这本书的是时候,我还正深受一些劣质中文Visual C++书之害,从此以后,看优秀的英文技术书就成为我坚定的信念。

递归算法图示

递归算法图示

与其跟学不会的递归纠缠不清,倒不如找找有没有非递归的汉诺塔解法。可惜虽然算法书上告诉大家:所有的尾递归都可以转化成迭代算法,结果却常常是搞成一个比递归还复杂的非递归实现。

《十万个为什么》第二套的数学卷2上讲过一种直观的非递归汉诺塔解法,很简单:

1. 把最小的圆盘向右移动到下一个位置,如果已经到最右边,就回到左边第一个位置

2. 把除最小圆盘所在位置的另外两个位置上的圆盘中较小的一个移动到大的上面(只可能有一种移法)

3. 重复1/2,直到所有盘子从一个柱子移到另一个柱子

不过不管怎么实现,完成神话中的64片金片的汉诺塔,需要步数总是二进制中64个1,正好相当于64位电脑的字长,对应的值就是2^64-1=18446744073709551615,如果一秒钟移一片,需要差不多5800亿年。

模仿与创新

看到Torrent Droid这个可以用手机拍摄DVD条码然后自动下载电影的程序,再次想起了手机上的条码应用。找了个条码识别库,很快做出个可以在WM上运行的拍条码去豆瓣找书的程序,兴奋没超过十分钟:与其费劲的启动程序、拍照、识别,还不如自己打开浏览器输一下条码好了,才13个数字。

这是几个小时前我在饭否上说的一句话。

手机拍摄条形码,然后识别,然后做点这样那样的事,这样的应用已经看到过两个了。最早是在Android上实现的拍条码查商品价格和评价的CompareEverywhere,然后就是今天的Torrent Droid,拍DVD条码可以自动让电脑帮忙下载相应的电影。

我做的应用:扫描书的条码,识别后从豆瓣上找到对应的书,调用浏览器打开豆瓣对应的资源页面,上面可以看到对书的介绍和评论。

这两个Android的应用和我今天做的扫条码查豆瓣,哪些是创新,哪些是模仿?

在我看来,两个Android的应用都是创新,而我的做的是模仿,而且还是比较拙劣的模仿--这也正是为什么我自己都对自己做的东西都只有十分钟的新鲜劲儿。

CompareEverywhere,作为第一个(也许)用手机拍摄条码识别做事的软件,它的创新性不容置疑。

Torrent Droid,它把手机拍条码的创意用到了一个全新领域,所以也是一种创新。

扫条码搜豆瓣,似乎也是把相同的创意用到了一个新的领,但其实这只是模仿,而且是模仿到了前两个应用中最炫目的一点,却没模仿到最重要的一点。

最重要的一点就是:创造价值。

CompareEverwhere和Torrent Droid,它们都只是把扫描条码作为整个产品中的一个普通的环节,而产品的核心价值是在把条码实别成数字以后事情,是把这串数字的搜索结果进行整合、分析、信息再加工的过程。也就是说,即便没条码扫描,这两个应用依然有它们的价值,它们可以节省很多本来要由人来完成的很烦琐的过程。

而豆瓣找书则不同,程序只是把识别出来条码数字做为URL的一部分去打开页面,并没有对数据进行分析和再加工,相比用户自己去输入这个URL而言,基本上没有创造出额外的价值来。(更不要说豆瓣的网页其实是非常不适合在手机上浏览的)

做产品,很多时候要为它做一些炫目的东西,因为这些东西也许会给你创造一个机会。但最终用户花钱是不是花在花架子上的,任何时候还是不能忘记产品的本质、产品的真正价值所在。

做产品是这样,做人也许也差不多。

折腾WD My Book World Edition

在同事鼓动下,跟他一起买了一个WD My Book World Edition II。这是一个小型的家用NAS (Network-attached Storage, 网络存储设备),它采用ARM 926系列的芯片,具备32M内存、千兆网卡,使用改造过的GNU/Linux系统。说白了,就是一个没有输入输出设备、很弱的、不太贵的、很省电的小电脑。由于采用的是GNU/Linux系统,而且WD开放了相关的源代码,所以,这个东东具有相当的可折腾性。

WD My Book World Edition II

WD My Book World Edition II

盒子买回来了就是一个空盒子,于是自己买了一块640G的硬盘装上。这个盒子直接采用主硬盘来存放它的操作系统,而不是采用Flash ROM,所以可以随便搞,不用担心会把系统刷死。

商家提供了一张系统恢复光盘,可以把WD官方的系统和网友改造过软件包一次性恢复到硬盘上,很方便,不对于追求完美而且又有点自虐倾向的我来说,这个系统太不好,原因在于它集成的东西太多了,包括Web管理界面在内的很多东西对于我来说都不实用,却要占用很多的宝贵的系统资源。而且它的专有系统也导致了可以再装的软件比较有限,而且很多时候需要自己编译,麻烦。

在论坛上看到有人找到了方法把EABI版的Debian跑在了盒子上,这显然是个利好消息。于是我就开始折腾……

省略具体过程N万字,总之经过三周多时间的折腾,终于成功的把Debian 5 (Lenny) GNU/Linux装在了盒子上,目前运行一切正常,盒子可以提供以下的功能:

PPPoE拨号上网、防火墙和路由,FTP/CIFS(Windows共享)/NFS数据访问,脱机BT/eMule/HTTP/FTP下载。

其它的功能,比如HTTP Server,比如Subversion,显然也是可以很容易实现的,简单apt-get安装一下即可。如果有PSP的话,还可以给它装上nethostfs。

盒子整体性能欠佳,FTP最快访问速度也就在9MB/s左右,平均CIFS的访问速度只有6M/s左右,如果打开NAT做路由会降到4M/s左右。eMule和BT的下载速度倒还都比较理想,2M的ADSL基本上可以达到线速。aMule消耗内存较严重,如果换用mldonkey会好一些,速度也比较快,但mldonkey不支持eMule混淆协议,不是很完美 :-P

还有几个小问题没有搞定:

1. 使用IDE硬盘:试了两种IDE->SATA转接卡,其中JM20330芯片的可以成功的转接一块4G(汗!)的硬盘,但320G那块还是不成功。看来只能用USB了。

2. 内存扩容:可以用64M的内存颗粒去替换板子上32M颗粒,10块钱的成本,性价比很好,就是这是个要求很高的技术活,不敢乱搞,以免因小失大。

折腾过程中总结了一些东西,发在论坛上了,这里就不罗嗦了,索引一下:

折腾盒子时还收获一个副产品,可能不少朋友不知道,在这里分享一下:

电信的一些ADSL套餐是可以支持多终端同时拨号上网的,也就是说,把ADSL Modem接在交换机上,然后同一个交换机上的多台电脑可以同时分别拨号上网,这对于路由器性能不佳(比如常常被BT下载轰到断流/常常DNS解析故障)或者需要多个IP的人,还是很有价值的。收费的问题,南京电信e8套餐是按从第一台终端连上到最后一台终端断线时长计算,不会重复计费。但具体的情况视套餐不同可能不同,最好与电信客服确认一下。

GMobileSync

Google前天发布了Google Sync,用于手机等移动设备与Google Calendar或Contacts进行同步。试用了一下,还是比较好用的,性能很不错。

可是这一利好消息却让另一件本来有点得意洋洋的事变得有点郁闷,唉,生不逢时啊。故事是这样的:

最近事情比较多,所以打算用Google Calendar来合理安排日程,于是希望找一个同步Google Calendar与Windows Mobile Pocket Outlook的软件。找了一圈,免费的软件和服务还真是不多,不过在CodePlex上有叫个GMobileSync的小软件倒是比较符合我的需求。下载试用一下,天哪,把我的日历搞得一团糟,该添的被删了、删了的又被加上了、所有的日程还都给我加上了几个小时的偏移量、农历日历被同步成每天一次的全天事件%!@#$

看在它是GPL的份上,自己来修改一下吧,下载了一份代码,虽然写得一团糟,但看起来并不太难,三下五除二把BUG修复,加上一些自己要用的功能。

有收获更要有奉献,申请成为这个项目的开发人员吧,看上去这个项目已经沉睡很久了,如果真的已经死掉了,就我自己在Google Code上另起个炉灶好了。不过在我即将动手之际,项目的负责人同意我成为GMobileSync的开发人员了。于是很积极的把修复的Bug和新加的功能提交,然后跟项目负责人商量产品版本发布计划,发完邮件等回复……

然后故事就讲完了,Google发布了Google Sync。

好吧,为了让我的劳动没有白费,在得到上级领导同意新版本发布前先出个Private Build吧。有兴趣的朋友可以下载试用,下载地址:

http://www.freemindworld.com/GMobileSync/GMobileSync_1.3.7_rc.cab

为了尽可能适用多用机器,这个cab是在Windows Mobile 5 Smartphone SDK下编译打包的,所以可以适用所有Windows Mobile 5/6的Smartphone或PocketPC用户。

至少,它比Google Sync多一个功能:支持一个帐户下多个日历。Google Sync只能同步用户的主日历。

敝帚自珍,近期还会继续维护GMobileSync项目。下一步计划完善多日历和多帐号(包括Google Apps)支持,这个可以看成是GMobileSync的核心竞争力。同时还要解决目前性能差、流量大的问题。GMobileSync用的是Google Data API实现的,而Google Sync是用了ActiveSync或OpenSync协议,显然后者会更适合这个任务,也许可以学习过来用用。