进位制与数学游戏

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

曾经在我的那些数学玩具们——二进制篇中提到过这个问题,看过那篇文章后,答案应该是不言而喻的,1, 2, 4, 8, 16, 32……

如果把题目换成:现有一架天平,若干个砝码,每个砝码应该分别多重才能称出1至1000克整数克的物品?

答案如果是不假思索的1, 2, 4, 8, 16, 32……自然是可以的,那我也不用废话写这篇文章了。实际上1000个苹果需要装在10个箱子里,用天平称1至1000克的物品却不需要10个砝码,只用7个就够了。

差别在于:装苹果的盒子只以能是选择拿或者不拿,而天平则可以不放砝码,或者把砝码放在左边,或者放在右边。所以,我只用两个砝码:1克和3克,就可以称出1至4克的任意整数克。

因此,解装苹果的问题需要用到二进制,解天平砝码的问题则需要用到三进制。二进制有0或1,真或假,开或关的两种状态。三进制则就有三种状态,0、1、2或-1、0、1(平衡三进制)。

在生活中,也有不少东西具有三种状态。对于天平称东西的问题(尤其是那些在XX个小球中找出X个不同的智力题)或者一些带有约束条件的过河问题,都可以用三进制来建模和解决。

进位制是一个很有意思的话题,以学习十进制和二进制的思维方式,我们就很容易的类推出各种进制的表现型式和性质,甚至于还可以捣鼓出“负2进制”之类的东东。感兴趣的TX可以考虑拜读Donald E. Knuth的神书TAOCP的第二卷。

好吧,其实这篇文章算是看了《进位制与数学游戏》一书的一小点收获了,在这本书中,作者不厌其烦的为一个相同的数学模型创造出了无数的问题和实例,所以在看完整本书后,能发现的收获也就只有那么一小点。

最后联想到了一个以前学编译原理时老师讲过的题,当时在课堂上我还真是没能自己做出来:

构造一个DFA,用于识别字母表∑={0,1}上可以被3整除的二进制数。

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

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亿年。

又撞墙了

原先就知道老老实实呆在家里是没事的,如果牵着狗狗出去逛逛,一不留神就会撞到墙上,撞得头破血流,撞得狗狗找不着北。今天发现,原来不牵着它,让狗狗自己走在回家的路上,也会撞上墙。

故事是这样的:以前总是让狗狗带着找路,后来发现狗狗身上背的小邮筒挺好使的,就把自己的邮件让狗狗帮忙收发。再后来又发现,狗狗还能帮忙把分布在各家门前的信箱的信件全部拿回来,而且还能把类别分的清清楚楚的,贴上不同的标签。更重要的是,它还会帮忙把那些信箱里的没有用的垃圾清理干净,把那些广告啥的扔到它的垃圾筒里,而且准确率极高。于是就把自己的N个信箱的全部信件都交给狗狗管理了。它也非常的尽责,总是很及时的跑遍所有的地方把邮件取回来,理整好再交给我。

可是这几天,好像狗狗一直偷懒没有去取信。正想责备它,却看到了它头上的鼓鼓的包,问问它怎么回事,回答说:拿263号信箱的时候不知怎么的信箱门就突然关上了。一直重试,于是撞的满头包。于是,我气乎乎的想去找邮局算帐。可是我自己去信箱拿信试试,发现一切都是那么的正常,所以,似乎邮局也没错……难道邮局不允许狗狗代为取信了?应该不会啊,我跟狗狗取信的方法是一样的啊,都是走的国际标准一千九百三十九号指定的流程啊。

顾不上处理狗狗遭遇,先自己处理一下那一堆狗狗没拿回来的信件吧。垃圾还真是多……一封封慢慢看吧……突然看到一个精致的信封,似乎很有吸引力,打开一看,唉……精美的信纸上还是印上了些非常不“和谐”的内容,似乎跟什么轮子有点关系,只好随手把它扔进垃圾箱。忽然间,对狗狗头上的包有所感悟,原来,那堵无形的墙,不只在出门的时候撞得上,回家路上,要是遇到什么不“和谐”的东西,它一样会撞得你晕晕的。

唉,从今往后就得留神着狗狗头上包了,如果撞了,就得自己去把那些会招来墙的信件处理掉了。麻烦啊……

这几天去看英文百科全书不会撞墙了,去找找各个博客的家也不会撞了,甚至一个被墙围起来的博客小区也可以进去了。可是那个出色的照片博物馆的照片陈列广场却被墙圈起来了。

没办法,期待有一天,我们真正的可以跨越“长城”,走向世界!

向各位用RSS阅读器阅读的朋友表示抱歉,不小心又把文章的uuid搞乱了,导致一篇老文章又跳到前面来了……有时间必须得再改进一下目前Blog和RSS生成的流程了。