在几百年前的日本，人们定期用猪牛等牲口祭祀天神，以表达对上天恩赐的感谢。但这种祭祀方式花费很大，于是日本人想到在木板上刻画牲口的图案，然后挂在寺庙里祭祀上天。有一天，一位日本武士开始设想：除了猪牛羊马以外，我们还可以在木板上画点其它东西。他开始画一些原创的、美观的、有新意的图案献给天神。他用数学来祭祀，向上天表示自己的聪明才智。

    人们陆续在日本的寺院里发现了数百个这样的木板，上面写有各种几何问题和定理。后人把这些刻有数学问题的木板叫做Sangaku。木板上的文字大都是古代汉字，这些文字多是对图案的描述，不过现在已经很难理解了。一位叫做Hidetoshi Fukagawa的日本数学教师一直致力于搜寻、翻译和研究Sangaku。最近，Fukagawa和Princeton大学的Tony Rothman合作完成了一本叫做Sacred Mathematics的书，书里详细介绍了Sangaku的完整历史，还有不少的Sangaku照片第一次走出了日本。
查看更多 »

    Benjamin Franklin是一个与Leonardo da Vinci同样神秘的人，他是一个伟大的物理学家、发明家、文学家、实业家、政治家、思想家、社会活动家。他一生中留下了许多的迷，电影National Treasure里提到的绝大多数关于Benjamin Franklin的事情都是真的。刚出版的一本名为Benjamin Franklin's Numbers: An Unsung Mathematical Odyssey的书中提到，人们还长期忽视了Benjamin Franklin的一些数学成就。Franklin曾计算过战争的经济开销，曾做过人口数预计，这都是没有先例的。其中，最有趣的数学创造还是要数Franklin的“另类幻方”。
    一个3x3的幻方是这样的一个九宫格，格子里写有1到9这9个数字，每一行、每一列和两条对角线上的三个数加起来都是一个相同的数。当然，更大一些的幻方也是存在的，例如你可以用前16个正整数排列成4x4的幻方。Franklin发明了一些另类的幻方，它的要求更加严格，但看上去似乎更有意思一些。Franklin在一封信中写道：“我不满足于这些普通的幻方，这都是很普遍、很简单的东西了。我给我自己强加了一些任务，然后成功地创造出了一些具有其它各种性质的幻方，它们看上去更加神奇。”Franklin创造了下面这个8x8的幻方，每种颜色的数字加起来都等于260，不同寻常的是，你有至少六种方法去解读它。
  

    更牛B的是Franklin的16x16幻方，他称它为“史上最神奇的幻方”。在这个幻方中，每一行、每一列和每一个“/\”形区域内的数字和都是2056。更不可思议的是，每一个4x4的子正方形内的数字之和也是2056 ！
  

    Franklin仍不感到满足。Franklin想，既然有“幻方”，为什么没有“幻圆”？于是Franklin构造出了下面这个图形。这个图形里，每一条半径、每一个同心圆和图中画出的每一个偏心圆内的数字加起来都是360。
  

    你可以从下面这个图中看出上图的偏心圆是怎么画出来的。
  

阅读更多：http://blog.sciencenews.org/mathtrek/2008/01/benjamin_franklin_plays_sudoku.html

    在1717年，法国流行这样一个赌博游戏：连续抛掷一个骰子四次，赌是否会出现至少一个1点。经过试验，赌徒Chevalier de Méré发现至少出现一个1点比不出现的几率似乎要稍微大一些。他总是赌“会出现”，每次算下来他总是赢。在这个赌博游戏的一个“加强版”中，赌徒们需要猜测，连续抛掷两个骰子24次，是否会出现至少一对1点。Chevalier de Méré想，两个骰子同时掷出1点的几率显然是单个骰子掷出1点的几率的1/6，为了补偿几率的减小则必须要抛掷骰子24次。因此，两个赌博游戏换汤不换药，赌“出现”获胜的几率应该是一样的。但奇怪的是，他每次都赌会出现一对1点，结果几乎每次的最终结果都是输。他感到百思不得其解，于是向数学家Pascal寻求一个合理的解释。Pascal与大数学家Fermat用信件进行了交流，最终提出了概率问题的若干原理，创立了概率学。
    我们可以简单算一下，虽然直观感觉两个问题的概率应该相等，但实际上前者发生的概率大于0.5，后者发生的概率小于0.5，虽然两者相差并不多。

    问题1：连续抛掷一个骰子4次，至少出现一个1点的概率是多少？
    解答：在所有6^4种可能的情况中，一个1点都没有的情况有5^4种，因此至少出现一个1点的概率是(6^4-5^4)/6^4≈0.5177

    问题2：连续抛掷两个骰子24次，至少出现一对1点的概率是多少？
    解答：在所有36^24种可能的情况中，一对1点都没有的情况有35^24种，因此至少出现一对1点的概率是(36^24-35^24)/36^24≈0.4914

    谁能用一句话解释清楚，为什么赌徒Chevalier de Méré的直觉是错误的？不用Ctrl+A了，这次没有藏啥东西。

参考资料：http://www.cut-the-knot.org/Probability/ChevalierDeMere.shtml

    在各种文明的算术发展过程中，乘法运算的产生是很重要的一步。一个文明可以比较顺利地发展出计数方法和加减法运算，但要想创造一套简单可行的乘法运算方法却不那么容易。我们目前使用的乘法竖式计算看似简便，实际上这需要我们事先掌握九九乘法口诀表；考虑到这一点，这种竖式计算并不是完美的。我们即将看到，在数学的发展过程中，不同的文明创造出了哪些不同的乘法运算方法，其中有的运算法甚至可以完全抛弃乘法表。
    古巴比伦数学使用60进制，考古发现的一块古巴比伦泥板证实了这一点。这块泥板上有一个正方形，对角线上有四个数字1, 24, 51, 10。最初发现这块泥板时人们并不知道这是什么意思，后来某牛人惊讶地发现，如果把这些数字当作60进制的三位小数的话，得到的正好是单位正方形对角线长度的近似值：1 + 24/60 + 51/60^2 + 10/60^3 = 1.41421296296...  这说明古巴比伦已经掌握了勾股定理。60进制的使用为古巴比伦数学的乘法运算发展带来了很大的障碍，因为如果你要背59-59乘法口诀表的话，至少也得背1000多项，等你把它背完了后我期末论文估计都已经全写完了。另一项考古发现告诉了我们古巴比伦数学的乘法运算如何避免使用乘法表。考古学家们发现一些泥板上刻有60以内的平方表，利用公式ab = [(a+b)^2 - a^2 - b^2]/2 可以迅速查表得到ab的值。另一个公式则是ab = [(a+b)^2 - (a-b)^2]/4，这说明两个数相乘只需取它们的和平方与差平方的差，再两次取半即可。平方数的频繁使用很可能加速了古巴比伦人发现勾股定理的过程。
    古巴比伦数学把除以一个数看作是乘以它的倒数，利用倒数表可以很方便的实现这种算法。倒数表开头的一部分是这个样子：

2      0; 30
3      0; 20
4      0; 15
5      0; 12
6      0; 10
8      0; 7, 30
9      0; 6, 40
10     0; 6
12     0; 5
15     0; 4
16     0; 3, 45
18     0; 3, 20
20     0; 3
....    ....

    
    古巴比伦人很早就发现，1/7是一个无限小数，怎么除也除不完。古巴比伦的倒数表里所有的数都是精确的小数，它们（在60进制中）都是有限小数。碰到无限小数时，他们会用取近似值的方法来解决。例如，古巴比伦人会通过1/13 = 1*(1/13) = 7*(1/91) ≈ 7*(1/90) = 7*(40/3600) = (7*40)/3600 来计算1/13的值。那个40就是查倒数表查出来的。


    古埃及数学使用了完全不同的乘法运算法。它们的乘法运算不需要借助任何辅助用表。古埃及人注意到，任何一个数都可以表示为若干个不同的2的幂的和。因此，你需要做的仅仅是不断将1和乘数进行翻倍。看看古埃及人如何计算46乘以22：

  46 x 22 = 1012
   1   22
   2   44     44
   4   88   + 88
   8  176  + 176
  16  352
  32  704  + 704
          -------
            1012

    上面的演算中，左列是1不断翻倍的结果，右边是22不断翻倍的结果。选出左列的2, 4, 8, 32，它们的和正好就是被乘数46；那么把右列对应的数加起来就是乘法运算的最终结果。至于如何选出2, 4, 8, 32这四个数，一个简单的方法就是，不断选出左列里小于被乘数的数中最大的一个，然后当前被乘数减去它。比如，32是最大的数，用46-32后剩14；8是小于14的最大数，14-8后剩6；然后最大的小于6的数是4，6减去4后剩2，这样下来2+4+8+32正好就是被乘数46了。这其实就是二进制的经典应用，2, 4, 8, 32正好与46的二进制中的数字1一一对应。你可以在这里看到一些相关的东西。
    无独有偶，据说俄国农村曾产生过这样一种乘法算术法：将被乘数逐次减半，同时乘数依次加倍，那么找出所有左边的数是奇数的行，其右列的数的和就是答案。例如，下面的例子中，23, 11, 5和1都是奇数，于是右边对应的44, 88, 176和704的和就是乘法运算的结果。这个做法与古埃及的算术法完全一样，但看起来似乎更神奇一些。

  46 x 22 = 1012
  46   22
  23   44     44
  11   88   + 88
   5  176  + 176
   2  352
   1  704  + 704
          -------
            1012

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

    69年7月31日，三家报社各自收到了连环杀手Zodiac写的一封密文的三分之一。Zodiac要求这三家报社把密文发表在报纸上，否则他将在这周末再次杀人。Vallejo Times-Herald得到的是整个密文的头三分之一(图1)，另外两家报社则是San Francisco Chronicle和San Francisco Examiner。这个密文共有408个符号，以后大家都习惯称它为408-密文(408-cipher)。408-密文是Zodiac的第一封密信，是Zodiac事件中极其重要的一环，David Fincher的电影Zodiac就完整地记述了这一事件。
    一个星期后，一位教师和他的妻子破解了这篇密文。他们发现，这篇密文用的是最简单的字母替换法，所不同的是一个字母可能对应多个符号。通常这种一对多的替换加密叫做同音替换法(Homophonic Substitution Cipher)。同音替换密码可以很好地防止字频破解法，因为你可以让常用的字母对应更多的符号，保证每个符号出现的次数大致相等。破解同音密码的常见方法是利用“字母Q后面一定是U”这一类的英文特性，因此你可以特别注意一个符号后面总是跟着那几个符号的情况（Q是不常用的字母，一般只对应一个符号）。但这篇密文太短，可以获取的信息有限，因此可能的破解方法只有一个：不断尝试，不断猜测，不断改进。不管怎样，那位教师和他的妻子解开了Zodiac的密码：

I LIKE KILLING PEOPLE BECAUSE IT IS SO MUCH FUN

IT IS MORE FUN THAN KILLING WILD GAME IN THE FORREST BECAUSE MAN IS THE MOST DANGEROUE ANIMAL OF ALL TO KILL SOMETHING GIVES ME THE MOST THRILLING EXPERENCE

IT IS EVEN BETTER THAN GETTING YOUR ROCKS OFF WITH A GIRL

THE BEST PART IS THAE WHEN I DIE I WILL BE REBORN IN PARADICE AND ALL THE I HAVE KILLED WILL BECOME MY SLAVES

I WILL NOT GIVE YOU MY NAME BECAUSE YOU WILL TRY TO SLOI DOWN or STOP MY COLLECTING OF SLAVES FOR MY AFTERLIFE EBEORIETEMETHHPITI

    最后这个EBEORIETEMETHHPITI是什么意思现在还没搞清楚。

    11月8日，Zodiac又寄出了一篇密文。这篇密文有340个字符，被称作340-密文。与408-密文不同的是，虽然大家都相信340-密文同样使用的是同音替换加密，但直到现在340-密文也没有解开。
    时至今日，David Fincher电影Zodiac又掀起了一次破解未解之谜的热潮，很多人都开始尝试破解340-密文并在网络上分享他们的新发现。最近，网络上出现了一个专门用于破解340-密文的网页。这个网页假设340-密文和408-密文一样也是用的同音替换法，你可以方便地对符号进行替换，同时程序可以告诉你替换后可以得到哪些单词。你也可以随机建立替换表，或者查看一些有趣的替换结果。目前最好的替换表可以产生halloween, killing, you, next, die, zodiac等单词。看过很多侦探小说和电影？对密码破译很有兴趣？340-密文是货真价实的“侦探小说式”密码，有兴趣的话不妨试一试。

    图灵机是1936年Alan Turing提出的一个计算机模型。这种计算机由一个一维数组（或者叫磁带）构成，还有一个可以左右移动的指针。磁带上每个格子里都有一种颜色（共可从m种颜色中选择），指针本身则可以是n种状态中的一种。给定一个m*n的表格，你就定义了一个图灵机。这个表格告诉机器，如果当前指针的状态是x，它所指的格子的颜色是y，那么下一步机器应该把这个格子染成什么颜色，然后指针应该左移一位还是右移一位，指针的新状态又是什么。有了一个图灵机后，我们便可以把它当做一个计算机进行数据处理了。我们可以给这个图灵机编写一个初始状态（也就相当于现在所说的程序和数据），让它按照这个表格不断执行下去，对数据进行处理并“输出”适当的结果来。
    能够模拟其它所有图灵机的图灵机叫做“通用图灵机”(UTM, Universal Turing Machine)。不是所有的图灵机都是通用的：很多图灵机只能完成一些特定的运算，而只有通用图灵机才能完成更一般的操作，是一台“通用的”机器。这些通用图灵机就像现代计算机一样，可以用来编程执行各种各样的操作，能实现现代计算机的各种功能。我们经常说一种程序语言是图灵完全的(Turing Complete)，指的就是这种语言等价于通用图灵机，能够执行任何一种复杂的数学运算。
    50年代起，科学家们疯狂地寻找通用图灵机，所需要的颜色数和状态数越来越小。最好的结果是1967年由Marvin Minsky得到的，他发现了一个7,4通用图灵机，即一个只需要7种状态，4种颜色的通用图灵机。人们开始好奇，最简单的通用图灵机是什么样子的。2002年，Stephen Wolfram（没错，就是MathWorld的那个Wolfram）做出了一个重大的突破：他发现了一个2,5通用图灵机，并且给出了一个很可能是通用图灵机的2,3图灵机。很早以前人们就证明了，不存在2,2的通用图灵机；因此如果Wolfram提出的2,3图灵机是通用图灵机的话，它就是最小的通用图灵机了。但Wolfram始终不能证明这个2,3图灵机是通用的，于是在今年三月份用25000美元悬赏征解。
    昨天，英国伯明翰大学的一名20岁在校大学生Alex Smith提交了一篇55页的论文，证明了Wolfram的2,3图灵机与另一个已知的通用机器等价，从而证明了2,3图灵机是最简单的通用图灵机，证实了这个很早就已经提出的猜想，解决了长期以来计算机科学界的一大疑问。这是一个意义非常重大的突破，无疑是信息学界中的一件激动人心的大事。

做人要厚道 转贴请注明出处
新闻来源：来源1 来源2

    人有十个手指，用手指的伸屈来计数非常方便。但一旦对象的数目超过10个了，手指头就不够用了。当然，有人会想到还有脚趾头。搬弄脚趾头是不现实的，数手指头只需要站着比划一下就可以了，数脚趾头还需要坐下来慢慢研究。一种好的方法是每次数完了十个指头后在什么地方做一个标记，比如在地上放一个木棒。人们可以把这根木棒想像成一个“大指头”，它相当于十个指头。这样，我有37个MM就被表示成了地上3个木棒加上我7个手指头。哈哈，你的MM数只有两根木棒加4个手指头，于是我的MM比你的多。久而久之，人们就只接受0到9这十个数字了，再大的数就用几个数字合起来表示。这种“满十进一”的数字系统就叫做十进位制。
    如果人只有八个手指头又会怎样呢？那我们现在很可能正在使用八进制，数学发展起来后我们最终只接受八个数字，而大于8的数字就用更高一级的计量单位表示。代表这八个数字的很可能是些星际之门里的怪符号，这里为了便于叙述，我们仍然使用阿拉伯数字的0到7来表示。于是，人类数数的方式将变为：0,1,2,3,4,5,6,7,10,11,12,13,14,15,16,17,20,...。这里，数字8被记作10，数字64则用100代替。在这个数学世界里，6+5=13，因为6+1得到的数已经是一位数中最大的了，再加的话只能“进一位”了。“满八进一”将成为数学运算的基本法则。
    如果人有12根手指，12进制将成为更难想像的事。在12进制中，人类会把10和11直接想成是一个“数字”。研究的进位制大于10时，大于9的数字我们习惯上用大写字母ABC来表示。这样，自然数序列里将多出两个符号A和B来，数数的方式变为...,8,9,A,B,10,11,12,...。

    我们自然会想，人类生活中究竟有没有其它的进位制呢？当然有。比如，时间和角度就是60进位制，60秒=1分。还有更怪的，计算机的储存容量单位是1024进制的，1MB=1024KB。当然，这也是有原因的。我们在研究几何时常常需要用到1/2，1/3，1/4或者1/6，我们希望这些分数在角度进制下恰好都是整数以便于运算。于是，角度的进位制就变成了60。为什么时间也是60进位制呢？因为时间和角度密切相关，你看看你的手表就知道了（别告诉我你的手表是数字型的）。为什么钟和手表又要用圆形表盘的方式来表示时间呢？其实人自古以来计算时间都是用的圆形盘面，因为地球绕太阳旋转和地球的自转使得时间具有了周期性。
    计算机使用二进制，因为计算机元件只有两种状态（开和关，或者说通电和断点），因此计算机只认0和1两个数字。1024是2的幂，又比较接近1000符合人的习惯，因此把1024当成了计算机容量的进位制。

    前段时间有人在OIBH上问，为什么纸币的面值都是1*10^n、2*10^n、5*10^n呢。有人回答说这样的货币系统可以使得某种贪心方法正确。确实有这个结论，这样的货币系统使得解决“凑钱和找零时最少使用多少张纸币”这一问题的贪心算法（不断拿最大面额的纸币）是正确。但用这一点来解释我们的问题显然是可笑的，人们首先考虑的并不是如何方便地使用最少纸币，而是如何方便地得到总面额。一个只有1元纸币和7元纸币的货币系统同样满足贪心性质，但显然傻子才会设计出这种别扭的货币系统来。因此，我的回答是“纸币的面值取10的约数，这样的话凑钱和找零最方便”。但是，有人会问，要是我们使用的进位制不是10怎么办？换句话说，如果我们使用的是23进位制，除1和本身外没有其它约数的话，又该怎样设置货币系统呢。答案非常出人意料，如果我们使用的是23进位制的话，我们很可能根本发展不出数学这门学科来。10=1+2+3+4，是前四个正整数的和；10又是2和5的积；这样的进位制非常适合数学的发展。同样地，6=1+2+3，6=2*3，因此可能正在使用六进制的昆虫们很容易发展出数学来（六足动物的数学非常强，不是有人发现了蜜蜂蜂巢的六边形样式设计是最科学的么）。大家看过《计算机中的上帝》(Calculating God)吗？那里面构造了这样一种生物：他有23根手指。这种别扭的数字最多只能让人联想到乔丹和染色体，除此之外没有任何特性。这给这种生物的数学发展带来不可逾越的困难。而事实上，这种生物恰好又没有发展数学的必要性。他就好像人类一样，对较小的物体个数具有直接感知的能力。人类可以直接感知的物体数量一般不超过6。也就是说，如果你眼前有3个，或者5个东西，你不需要数，看一眼就知道有多少个；但当你眼前出现的物体数目达到7个或者8个时，你就必须要数一数才知道个数了。而我们所说的生物面对的物体数目多达46个时仍然可以一眼分辨出多少来，数目超过46后就统称为“很多”了。直接感知数目达到50甚至60多的生物个体就扮演着该种族中的僧侣角色。46这个数字对于种族的生存已经完全足够了，他们在组建部落时总会保证部落的个体数不超过这个数字。因此，这种生物不需要数数的能力，他们也就无须发展数学了。他们不知道30加30等于多少，从某种意义上说他们甚至不知道一加一等于几，因为他们头脑中根本没有数字这个概念。作为一种补偿，他们对事物的感知能力相当敏锐。他们甚至直接凭直觉感知到了相对论，因为他们的思维不受演绎逻辑的束缚。

    下文将介绍两套进制转换的方法，然后介绍这两套方法在小数转换上的应用。更多的进位制相关应用你可以在文后的习题部分中体会到。

    在讲进位制时，大多数教材会教大家二进制和十进制如何互换。今天我就偏不这样讲，我要和那些教材讲得一样了我还不如不写今天这些东西。二进制虽然常用，但比较特殊，很可能会了二进制但仍然不会其它进制；我们今天当一回蜜蜂，看看六进制和十进制怎么互相转换。学会这个后，任意进制间的转换你就应该都会了。
    说起进位制时往往要回到最根本的一些计数方法上。这篇日志是我第237篇日志。数字“237”表示两个百，加上三个十，加上七个单位一。我们把它们分别叫百位、十位和个位，同一个数字在不同数位上表示的实际数量不同。用一个式子表示上面的意思就是，237=2*100+3*10+7。这就是进位制的实际意义。
    现在，假如我是一只勤劳的蜜蜂。我写237篇日志是肯定不可能的了，因为我的数学世界里根本没有7这个数字。那就说我写了235篇日志吧。结合前面所说的东西，“十位”上的数表示有多少个6，“百位”上的数表示有多少个36（后面提到的十位、百位打引号表明这不是十进制中的“十”和“百”）。于是，六进制下的235就应该等于2*6^2+3*6+5。这个算式你用什么进制算出答案就相当于把六进制中的235转换为了什么进制。不过你要把这个式子当成别的进制算是不大可能的，算之前你估计得重新背一遍乘法口诀表（注意我为什么不说是“九九”乘法口诀表）。这就是我们为什么一般只研究十进制与其它进制互换的原因。我们用熟悉的十进制进行计算，得出2*6^2+3*6+5=72+18+5=95。这是按定义进行进制转换的方法。六进制的235等于十进制的95，我们记作(235)6=(95)10。那个6和10是下标，应该像H2O的2一样小小地写在下面。我就懒得排版了，反正转贴个几次就成Plain Text了。
    下面的任务是，考虑怎么把(95)10变回(235)6。使用六进制计算13*10+5可以得到235（十位上的9相当于六进制中的13），但我们说过六进制计算很麻烦。下面我们给出一种把十进制转换为六进制的方法，仔细思考你会发现这种方法显然是正确的。我们把所有6的幂从小到大写出来：1,6,36,216,...。216远远超过95了，因此95的六进制不可能是四位数。95里面有两个36，因此在最高位上写个“2”。去掉两个36，95里只剩23。23里有三个6，数字3将填写在第二位上，去掉这三个6最后所剩的5留给最末位。换句话说，我们不断寻找最大的x使得6^x不超过当前数，当前数减去6^x并在右起第x+1位上加一。这事实上是前面六进制转十进制的逆过程。
    上面的进制互换方法是一套方法，这是我们所介绍的第一套方法。这套方法的特点是正确性很显然，但是计算比较复杂，又费马达又费电。我们需要一个计算更方便的进制转换方法。下面介绍的就是进制转换的第二套方案。

    再一次回到一个很基础的问题：在十进制中，为什么乘以10相当于在数的末尾加一个0？我们同样会联想到位运算：为什么二进制左移一位（末尾加一个0）相当于乘以2？事实上，这个结论普遍存在于所有进位制中：k进制数的末尾加个0，相当于该数乘以k。证明方法非常简单，乘以一个k就相当于进位制展开式的每个指数都加一，也就相当于所有数字左移一位。六进制235=2*6^2+3*6+5，乘以6的话式子将变为2*6^3+3*6^2+5*6，也即2350。利用这个性质，六进制235可以很快转为十进制：235相当于2后面添0，加上3，再添一个0，再加上5，写为算式即(2*6+3)*6+5=95。把(2*6+3)*6+5展开来，得到的式子和前面的那种计算方法(2*6^2+3*6+5)一模一样，但这里的计算方式更简便一些。如果写成程序，六进制字符串t转为十进制数a只需要一句话就可以完成：
for i:=1 to length(t) do a:=a*6+ord(t[i])-48;
    使用这种方法将十进制变回六进制是一个彻头彻尾的逆向操作：当前数不断除以6并把余数作为新的最高位。比如，95除以6等于15余5，余数5就是个位，15除以6的余数3作为“十位”，最终的商2是“百位”。这叫做短除法，是最常见的方法，网上随处可见。

    下面说一下进位制中的小数。前面的东西如果理解了，小数进制的转换将顺理成章地进行下去。六进制中的0.1相当于十进制的1/6，因为六进制中的0.1、0.2、0.3、0.4、0.5五个数把区间0到1均分为了6分。同样地，(0.05)6=(5/36)10。你会发现，一个“十分位”代表1/6，一个“百分位”代表1/6^2，之前的很多结论仍然成立。六进制小数12.345就等于1*6^1+2*6^0+3*6^(-1)+4*6^(-2)+5*6^(-3)，通过负指数把进制转换的整数部分和小数部分联系在了一起。(12.345)6转为十进制后居然变成了无限小数，其实这并不奇怪，这只是一个约数的问题：同样是三分之一，在我的六进制下正好分干净(0.2)，但在你十进制下就总也分不完，总要剩一点留给下一位(0.333333...)。这里有一些小数进制转换的实例。可以看到，一个进制下的有限小数很可能是另一个进制下的无限循环小数。另一个有趣的例子在这里。
    既然前面所说的第一套方法中六进制转十进制对于小数仍然成立，那么第一套方法的十进制转六进制也可以直接在小数上使用。如果你嫌无限小数很别扭，用分数进行操作是一种不错的选择。具体操作方法和前文叙述一模一样。针对纯小数的进制转换，我们把前文的描述换种方法再说一遍：不断寻找最小的正整数x使得1/6^x不超过当前数，当前数减去1/6^x并在小数点后第x位上加一。我就不再举例子了，下面主要讨论第二套方法在小数上的应用。
    我们曾说过，在k进制末尾加0相当于该数乘以k。可惜这对小数没有用，小数后你加它八百个“0”这个数仍然不变。其实，“末尾加0”只是这种性质反映在整数上的一种现象而已，我们还需要看到更本质的东西（还记得高二哲学么）。考虑到小数的乘k和除k，不难想到这种性质的实质是小数点的移动，整数的末尾加0其实是小数点向右移动一位的结果。显然小数也有类似的结论：将k进制小数的小数点左移一位，相当于该数除以k。比如，十进制中3.14除以10就变成了0.314。结论的证明和原来完全相同：除以k后展开式中的指数全部减一，相当于所有数右移一位。有了这个结论，我们的方法就出来了。来看六进制12.345如何转换为十进制。由于这种方法对整数和小数的处理方法有一些不同，转进制时我们通常对整数部分和小数部分分别进行操作。先把12转成十进制的8，然后单独考虑小数部分。0.345可以看作是数字“5”的小数点左移，加上4后小数点再次左移，再加上3并最后一次左移小数点；写成算式即((5/6+4)/6+3)/6。展开这个式子，实质与前面的方法仍然一样。小数部分十进制转六进制依然是彻头彻尾的逆向操作：当前数不断乘以6并取出整数部分写下来。
    这里有一个实例供大家参考，这个例子中的进制转换保证不涉及无限循环小数。1/4在十进制和六进制下的表示肯定都是有限小数，因为4的唯一一个因子2同样也是10和6的因子。先看0.25怎么变成六进制：0.25*6=1.5，取出1，留下0.5；0.5*6=3，没有小数部分了，因此(0.25)10就等于(0.13)6。现在我再把它变回去：(3/6+1)/6=(0.5+1)/6=1.5/6=0.25。这不是彻头彻尾的逆操作吗？

    每年NOIp前总有人问负进位制。事实上，如果你搞清了上面的问题，负进位制将非常好理解。负进位制有一个非常奇特的功能：它可以表示出负数但不需要用负号。一个负进制数可能是负数，也可能是正数。比如，负六进制下的12等于十进制下的-4，而负六进制下的123等于1*(-6)^2+2*(-6)^1+3，即十进制下的27。是正是负取决于位数的奇偶：若该数有偶数位，则该数为负数；若有奇数位，则该数为正数。原因很简单，小数点每右移一位，相当于这个数乘以-6；从一位数开始，乘奇数次后该数的位数变成偶数且值为负，乘偶数次该数仍有奇数位且值仍为正。由于末尾添0的性质（小数点移位的性质）仍然成立，负六进制与十进制的转换依然是上面的方法：(123)-6=(1*(-6)+2)*(-6)+3=(27)10。十进制转负六进制？还是那句话：彻头彻尾的逆操作。找到最小的非负整数x使得当前数减x能被6整除，这个x将作为新的最高位写到结果中，然后当前数减去x再除以-6。在这里我不说“余数”这个词，因为当除数为负数时对余数的定义很模糊。不再举例子了，例子都举烦了，自己把(123)-6=...=(27)10那一行倒过去看就是例子了。
    当然，还有更神奇的：-1+i进制可以表示出复数来，因为-1+i的幂有时含有虚数有时不含虚数。运算和转换依然和上面这些东西一样，我也就不多说了。

    进位制的问题结束了。我们这里是以六进制为例进行的说明，但是不要忘记，最有趣的仍然是二进制。与二进制有关的趣味问题遍地都是。举个例子，你可以在这里的第三题看到一个二进制的经典应用。


文章最后还是那三句话：
Matrix67原创
转贴请注明出处
请大家帮忙校对

这次的错别字可能很多，因为我不是用的紫光，而是用的fcitx，没办法使用原来的词库了。
讲解也可能有漏洞，很多东西是我突然想到，即兴写下的。大家帮忙纠错啊！


附一：四道进位制练习题及其简略解答
    下面这些题目是在我公布的那个课件里的，是我收集的一些很不错的具有代表性的题目，讲课时已经用过多次了。

1. 证明：Σ(n=1 to ∞)6^( (2-3n-n^2)/2 )是无理数。
  解答：用六进制表示此数，该数显然为无理数。

2. 在哪一种进制中，35与58互质？
  解答：由于出现了数字8，因此进位制至少为9。事实上，35和58在任何不小于9的进位制下都互质，因为辗转相减不会出现“不够减”的情况，任何进制下最终都得1。

3. 证明：没有一种进制使三位数aaa恰等于a^3。
  解答：设此数为k进制，则ak^2+ak+a=a^3。此方程无整数解。

4. 在哪一种进制中，792可以被297整除？
  解答：这道题目非常有趣。在任何一种进制下，200的四倍都已经超过792，300的两倍都还不足792。那么，792只可能是297的三倍。设进位制为k，问题转化为解方程7k^2+9k+2=3*(2k^2+9k+7)。



附二：进位制笑话不完全收集:)

1. What would the value of 190 in hexadecimal BE?

2. If only DEAD people understand hexadecimal, how many people understand hexadecimal?

3. There are only 10 types of people in the world — those who understand binary, and those who don't.

4. There are only 10 types of people in the world — those who understand trinary, those who don't, and those who mistake it for binary.

5. Why do mathematicians think Halloween and Christmas are the same? Because 31 Oct = 25 Dec.

    我喜欢各种各样的证明。有史以来我见过的最诡异的证明写在http://www.matrix67.com/blog/article.asp?id=34。人们很难想到这样一些完全找不到突破口的东西竟然能够证明得到。说“没有突破口”还不够确切。准确地说，有些命题多数人认为“怎么可能能够证明”却用了一些技巧使得证明变得非常简单。我看了五色定理的证明，定理宣称若要对地图进行染色使得相邻区域不同色，五种颜色就够了。没看证明之前，我一直在想这个玩意儿可以怎么来证明。直到看了证明过程后才感叹居然如此简单，并且立即意识到四色定理基本上也是这种证明方法。还有，像“一个单位正方形里不可能包含两个互不重叠且边长和超过1的小正方形”这样的命题竟然完全用初中学的那些平面几何知识证明到了，简单得不可思议。关键是，我们能够读懂证明过程，但只有牛人才能想到这个证明过程。
    今天在OIBH上看到了这个帖子，帖子中哲牛分享的一篇文章The Power Of Mathematics恰好说明了这一点。文章中包含有一个推翻“万物皆数”的新思路，相当有启发性。今天我想把我已经知道的四种证明连同新学到的这一个一起写下来。

    如何证明存在一种不能表示为两个整数之比的数？
    古希腊曾有“万物皆数”的思想，这种认为“大自然的一切皆为整数之比”的思想统治了古希腊数学相当长的一段时间，许多几何命题都是根据这一点来证明的。当时的很多数学证明都隐性地承认了“所有数都可以表示为整数之比”，“万物皆数”的思想是古希腊数学发展的奠基。直到有一天，毕达哥拉斯的学生Hippasus告诉他，单位正方形的对角线长度不能表示为两个整数之比。被人们公认的假设被推翻了，大半命题得证的前提被认定是错的，古希腊时代的数学大厦轰然倒塌，数学陷入了历史上的第一次危机。最后，Eudoxus的出现奇迹般地解决了这次危机。今天我们要看的是，为什么单位正方形的对角线长度不能表示为两个整数之比。
      
    单位正方形的对角线长度怎么算呢？从上面的这个图中我们可以看到，如果小正方形的面积是1的话，大正方形的面积就是2。于是单位正方形的对角线是面积为2的正方形的边长。换句话说，Hippasus认为不可能存在某个整数与整数之比，它的平方等于2。
    中学课程中安排了一段反证法。当时有个题目叫我们证根号2是无理数，当时很多人打死了也想不明白这个怎么可能证得到，这种感觉正如前文所说。直到看了答案后才恍然大悟，数学上竟然有这等诡异的证明。
    当然，我们要证明的不是“根号2是无理数”。那个时候还没有根号、无理数之类的说法。我们只能说，我们要证明不存在一个数p/q使得它的平方等于2。证明过程地球人都知道：假设p/q已经不能再约分了，那么p^2=2*q^2，等式右边是偶数，于是p必须是偶数。p是偶数的话，p^2就可以被4整除，约掉等式右边的一个2，可以看出q^2也是偶数，即q是偶数。这样，p也是偶数，q也是偶数，那么p和q就还可以继续约分，与我们的假设矛盾。

    根号2是无理数，我们证明到了。根号3呢？根号5呢？你可能偶尔看到过，Theodorus曾证明它们也是无理数。但Theodorus企图证明17的平方根是无理数时却没有继续证下去了。你可以在网上看到，Theodorus对数学的贡献之一就是“证明了3到17的非平方数的根是无理数”。这给后人留下了一个疑问：怪了，为什么证到17就不证了呢？一个俄国的数学历史家“猜”到了原因。
    他猜测，当时Theodorus就是用类似上面的方法证明的。比如，要证明根号x不是有理数，于是p^2=x*q^2。我们已经证过x=2的情况了，剩下来的质数都是奇数。如果x是奇数且p/q已经不能再约分，那么显然p和q都是奇数。一个奇数2n+1的平方应该等于4(n^2+n)+1，也即8 * n(n+1)/2 + 1，其中n(n+1)/2肯定是一个整数。如果p=2k+1，q=2m+1，把它们代进p^2=x*q^2，有8[k(k+1)/2 - x*m(m+1)/2] = x-1。于是x-1必须是8的倍数。如果当时Theodorus是这么证明的，那么他可以得到这样一个结论，如果x-1不能被8整除，那么它不可能被表示成(p/q)^2。好了，现在3、5、7、11、13减去1后都不是8的倍数，它们的平方根一定不是有理数。在x=9时发生了一次例外，但9是一个平方数。而当x=17时这种证明方法没办法解释了，于是Theodorus就此打住。

    实际上，我们上面说的这么多，在古希腊当时的数学体系中是根本不可能出现的。毕达哥拉斯时代根本没有发展出代数这门学科来，它们掌握的只是纯粹的几何。因此，Hippasus当时的证明不可能像我们现在这样搞点什么奇数x偶数y之类的高科技东西。事实上，Hippasus当时完全运用的平面几何知识来证明他的结论。有人觉得奇怪了，既然当时没有代数，古希腊人是怎么提出“所有数都可以表示为整数之比”的呢？其实古希腊人根本没有提出什么整数之比，这是后人的一个误解。当时毕达哥拉斯学派提出的，叫做“公度单位”。
    两条线段的公度单位，简单的说就是找一个公度量，使得两条线段的长度都是这个公度量的整倍数（于是这个公度量就可以同时作为两条线段的单位长度并用于测量）。寻找公度量的方法相当直观，就是不断把较长的那个线段减去短的那个线段，直到两个线段一样长。熟悉数论的同学一下就明白了这就是欧几里德的辗转相除算法求最大公约数。第一次数学危机的根结就在于，古希腊人理所当然地相信不断地截取线段，总有一个时候会截到两个线段一样长。后来，Hippasus画了这么一张图，告诉大家了一个反例：有可能这个操作会无穷尽地进行下去。
      
    现在看他怎么解释，在图中的BC和BD之间进行辗转相除为什么永远不能停止。把BD减去BC，剩下一段DE。以DE为边做一个新的小正方形DEFG，那么显然DE=EF=FC（∵△EDF为等腰直角且△BEF≌△BCF）。接下来我们应该在BC和DE间辗转相除。BC就等于CD，CD减去一个DE相当于减去一个FC，就只剩下一段DF了。现在轮到DE和DF之间辗转相除，而它们是一个新的正方形的边和对角线，其比例正好与最初的BC和BD相当。于是，这个操作再次回到原问题，并且无限递归下去。最后的结论用我们的话说就是，不存在一个数x使得BC和BD的长度都是x的整倍数。于是，BD/BC不能表示为两个整数之比p/q（否则BD/p=BC/q，这就成为了那个x）。

    有发现上面的代数证明和几何证明之间的共同点吗？它们都是这样的一个思路：假设我已经是满足这个性质的最小的那个了，那么我就可以用一种方法找出更小的一个来，让你无限循环下去，数目越来越小，永无止境。严格的数学证明中你或许会看到这样一句话：“不失一般性，设n为最小的满足……”
    这种证明方法应用很广。比如，证明3^n不能表示为两个正整数的平方和。我假设存在一个最小的n使得x^2+y^2=3^n，那么x^2+y^2可以被3整除，于是x和y也应该能被3整除（一个正整数的平方除以3，要么除尽，要么余1）。假如x=3p，y=3q，那么(3p)^2+(3q)^2=3^n，即9(p^2+q^2)=3^n，那么。p^2+q^2=3^(n-2)，这和n最小的假设矛盾。换句话说，你永远找不到最小的，你必须一直递归下去。
    对于根号2是无理数的问题，下面一个证明使用了与上例几乎相同的解决方法。
    如果√N不是整数的话，假设√N=A/B（化到最简），那么NB/A=A/B。化成带分数后，NB/A和A/B的分数部分是形如a/A和b/B的形式，其中a<A且b<B。如果两个数相同，那它们的小数部分也应该相同，于是a/A=b/B。我们发现，a/b = A/B =√N，即我们找到了√N的更简的表达形式a/b。

    接下来的两个证明才是我佩服的，真正的Very Simple & Very Tricky。
    下面的这个证明曾经是我最喜欢的关于无理数的存在性的证明，它实在是太神奇了。
    假设(p/q)^2=2，那么p^2=2q^2。我们将要证明，一个数的平方等于另一个数的平方的两倍是根本不可能的。如果对一个平方数分解质因数，它必然有偶数个因子（x^2的所有质因子就是把x的质因子复制成两份）。于是，p^2有偶数个质因子，q^2有偶数个质因子，2q^2有奇数个质因子。等号左边的数有偶数个质因子，等号右边的数有奇数个质因子，大家都知道这是不可能的，因为同一个数只有一种分解质因数的方法（唯一分解定理）。
    这个证明还有一种更加神奇的变化。p^2和2q^2的质因子中，因子2的个数肯定是一奇一偶。那么它们转化成二进制后，末尾0的个数肯定也是一奇一偶。因此，这两个数不可能相等。

    今天，我见到了一个更加简洁的证明。它就来源于哲牛介绍的那篇文章。这个证明虽然与前面的证明有些类似，但它的简洁性足以让我打算写下今天这篇4000字的文章。看后我大为折服，这真的叫做the power of simple ideas in mathematics。
    同样是证明不存在整数p, q使得p^2=2q^2，这个证明只需要一句话。假如p、q是最小的正整数使得p^2=2q^2，看图，两个边长为q的小正方形放在一个边长为p的大正方形里，那么图中深灰色正方形的面积就等于两个白色正方形面积之和（面积守恒），于是我们就找到了具有同样性质的更小的整数p和q。仔细体会一下这个“面积守恒”，如果A+B=C，那么A和B重复计算了的必然是C里还没有算过的。很有意思。

      


2007.05.21更新第六种方法：http://www.matrix67.com/blog/article.asp?id=251

Matrix67原创
转贴请注明出处