又一种证明根号2是无理数的方法

    今天的最后一篇日志了,仍然是翻译的cut-the-knot。发完我就睡觉去了。

    这里已经有五种证明根号2是无理数的方法了。现在我们算是介绍第六种方法了。
    一个有限小数的平方绝对不可能变成整数,因为小数部分不可能消失。观察有限小数的小数部分最后一个数字你会发现结论是显然的,平方后它总会产生新的“最后一位”。
    下面证明,(n/m)^2不可能等于2。n/m不可能是整数,于是把它写成小数形式,而有限小数的平方不可能是整数。如果n/m不是有限小数的话,可以把它转换成另外的进制使得n/m是有限小数,因而上面的结论仍然成立。一个进制下的无限小数可能是另一个进制下的有限小数。比如,把分数n/m转化为m进制,得到的小数肯定是有限小数。

漫话进位制

    人有十个手指,用手指的伸屈来计数非常方便。但一旦对象的数目超过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的幂有时含有虚数有时不含虚数。运算和转换依然和上面这些东西一样,我也就不多说了。

    进位制的问题结束了。我们这里是以六进制为例进行的说明,但是不要忘

非传统题型练习:三道答案提交类题目

    不少人可能为找不到非传统题型的练习题而头疼。这几天我专门发出一些用于省选集训的题目供大家参考。

Problem 1: cell 手机
题目来源:USACO Contest FEB06 Gold (Translated by Matrix67)

问题描述
    奶牛们已经开始使用手机交流了,但它们发现手机的按键设计不适合它们的蹄子。它们想设计一个新的手机,让它的按键更少,但是更大。
    它们喜欢普通手机的一个功能:词语联想。每个按键都有一些字母和它对应,打出一个单词只需要按对应的按键。因为一个按键可能对应多个字母,因此某些单词可能会发生“歧意”。不过,大多数时候这种歧意可以通过用字典判断的方法来消除。
    考虑到奶牛们在自定义一款新的手机,它们还需要用奶牛字母表替换英文字母表。神奇的是,奶牛字母表中的字母恰好是英语字母表中的前L个字母,即使顺序也一样。它们想知道如何把这些字母分配给B个按键(1<=B<=L)使得在字典中不会产生歧意的单词最多。就像普通的手机一样,他们希望每个按钮上的字母都是字母表中一段连续的字母。

    这是一个答案提交类的题目。你只需要在你自己的计算机上计算出你的答案,然后把输出文件提交上来。与输入文件cell.3.in相对应的输出文件应该为cell.3.out,这里“3”表示你提交的答案是第3个输入文件的解。当然,其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入数据
    第一行:一个整数N,表示这是第N个输入文件。
    第二行:两个用空格隔开的整数:B和L
    第三行:D,字典中的单词数(1<=D<=1000)
    第四行到第D+3行:每一行包含一个字典中的单词,用1到10个大写字母表示。这些单词按照字典序给出,并且保证没有重复。

输出数据
    第一行:字典中具有唯一的按钮序列的单词数。
    第二行到第B+1行:其中的第n行包含有第n个按钮上的字母,用大写的字母按照字典的顺序表示。所有行必须按照字典序排列,每个字母出现恰好一次。如果有多个最优解,选用第一个按键上字母最多的解。如果最优解仍然不唯一,考虑第二个按键上字母最多,依此类推。

样例输入(cell.1.in)
1
3 13
11
ALL
BALL
BELL
CALK
CALL
CELL
DILL
FILL
FILM
ILL
MILK

样例输出(cell.1.out)
7
AB
CDEFGHIJK
LM

样例说明
    第一个按键上只有AB两个字母,第二个按键上含有C到K,第三个按键上为LM。单词CELL、DILL、FILL和FILM的输入都是2233,其它7个单词的输入都是唯一的。

题解(Ctrl+A):
    这道题目……搜索,乱搞。

Problem 2: selfstr 自描述序列
题目来源:Matrix67根据经典问题改编

问题描述
    “这句话里有1个数字零,2个数字一,1个数字二,0个数字三”。

    在N(N>=2)进制中只允许0到N-1这N个数字出现。一个N位的N进制数(允许有前导0)可以由另一个同样多位的数来描述。我们定义一个N位N进制数的描述序列为:左起第i个数字为原数中数字i-1出现的次数。
    例如,在4进制中,0023的描述序列为2011,因为0023中有2个0,0个1,1个2和1个3。
    我们惊奇地发现,4进制数1210的描述序列是它本身!我们称这样的数叫做“自描述序列”。

    你需要编写程序计算出在某个进制下的自描述序列。一个进制下的自描述序列可能有很多个,你只需要给出其中一个即可。
    这是一个答案提交类的问题。你只需要在你自己的计算机上计算出你的答案,然后把输出文件提交上来。与输入文件selfstr.3.in相对应的输出文件应该为selfstr.3.out,这里“3”表示你提交的答案是第3个输入文件的解。当然,其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入格式
    输入数据只有一个正整数N

输出格式
    输出N个字符,它表示N进制下的自描述序列。在高于10的进位制下,大于9的数字请用大写字母表示。
    如果有多种可能的解,你只需要输出其中一个。
    如果该进制下无解,请输出“NONE”。

样例输入(selfstr.1.in)
4

样例输出(selfstr.1.out)
1210

题解:
    这道题太有意思了!首先,你需要先算几个小数据。你会发现,算到N>=6后,渐渐有规律了:


   N   N进制下的自描述序列
   4    1210 or 2020
   5    21200
   6    NONE
   7    3211000
   8    42101000
   9    521001000

    事实上,这道题目就是考你当搜索到一些解后能不能找到规律得到所有解。这里我们发现,对所有N>6,至少存在一个解为R21(0…0)1000,其中R=N-4,中间0的个数为N-7。结论显然正确。
    有可能除了这个之外存在其它的解,因此我们仍然需要写一个check来核对答案。

Problem 3: relation 大小关系
题目来源:Matrix67根据经典问题改编

问题描述
    用关系“ < ”和“ = ”将3个数a、b、c依次序排列时,有13种不同的序列关系:
      a=b=c, a=b<c, a<b=c, a<b<c, a<c<b
      a=c<b, b<a=c, b<a<c, b<c<a, b=c<a
      c<a=b, c<a<b, c<b<a

    用这两种关系连接N个数有多少种不同的方案?

    这是一个答案提交类的问题。所有选手将得到10个输入数据,你只需要在你自己的计算机上计算出你的答案,然后把你的答案提交上来。与输入文件relation.x.in相对应的输出文件应该为relation.x.out,这里x表示一个1到10之间的数。

输入格式
    输入一个整数,表示N。

输出格式
    输出用小于和等于符号将N个数进行有序排列的方案数。

样例输入(relation.1.in)
3

样例输出(relation.1.out)
13

题解:
    组合数学+高精度。由于数据规模很小,我就直接搞成了答案提交类的题目。
    下面给出两种递推方法:
    Solution 1: N个数中必然存在一个最大的“等价类”,如果这个等价类里有k个数,那么剩下的数就有F(N-k)种排列方案。别忘了我们需要枚举这k个数是哪k个数。于是,F(N)
=C(N,1)F(N-1)+C(N,2)F(N-2)+C(N,3)F(N-3)+ … +C(N,N)F(0)
    Solution 2: 用F[ i, j]表示 i个数中有j 个等价类的排列方案(就是说有j-1个小于符号)。第 i个数有可能并入了F[i-1, j]中的 j个等价类中的一个,也有可能不与任何一个已有的数相等,独自成为一个等价类插入F[i-1, j-1]里产生的 j个空位中。于是,F[ i,j ]=F[i-1, j]*j + F[i-1,j-1]*j。

其它问题:
    如何用Cena评测答案提交类问题?
        见http://www.matrix67.com/blog/article.asp?id=176
    这些题的数据哪里有?
        第一题:http://ace.delos.com/FEB06,GOLD DIVISION里面的第三个
        第二题:自己写check,不需要数据
        第三题:http://www.research.att.com/~njas/sequences/b000670.txt,吓死你

Matrix67原创
转贴请注明出处