有趣的数学难题.doc
【泡泡糖咨询题】 悲伤的琼斯夫人路过泡泡糖出售机时,尽量不使她的双胞胎儿子有所发觉. 大儿子:"妈妈,我要泡泡糖." 二儿子:"妈妈,我也要,我要和比利拿一样颜色的." 分币泡泡糖出售机几乎空了,里面只有4粒白色的和6粒红色的泡泡糖.说不准下一粒是什么颜色.琼斯夫人假如要得到两粒同种颜色的泡泡糖,需要预备花多少钱? 是不是琼斯夫人需要花6分钱,准能够得到2粒红色的糖-就算所有白色的糖花去4分钱,还有两分钱能够买到2粒红色的糖.或者她花去8分钱准可得到2粒白色的糖,因而她需要花8分钱是吗?假如你如此算,那就错了,由于琼斯夫人并不要求必须得到两粒红色的糖或者两粒白色的糖,她只要求两粒同色的糖,即便先取到两粒不同色的糖,第三粒必定与前两粒中的一粒同色.因而她最多只需要花3分钱. 假如出售机内有6粒红色的,4粒白色的,5粒蓝色的.琼斯夫人最多要花多少钱?显然只要花4分钱即可. 假如琼斯夫人的小孩是三胞胎,那该怎么样呢?最坏的情况是她拿到了2粒红的,2粒白的和2粒兰的,第七粒确信与前六粒中的两粒同色,因而她最多需要花7分钱. 假如只有一粒蓝色的泡泡糖,那么显然只要花6分钱即可买到三粒同色的糖. 假设琼斯夫人是幼儿园的教师,她带着 k 个小孩路过泡泡糖出售机,出售机中有 n 组同色的泡泡糖,且每组糖至少有 k 粒,她需要花多少钱呢? 最坏情况是她每种颜色的泡泡糖都买了 k-1 粒,那么再买一粒即可,因而她最多需要花 n(k-1)+1 分钱. 假如 n 组糖中有一组或几组同色的糖少于 k 粒,又是什么情况呢? 让我们假设有 m 组同色的泡泡糖少于 k 粒,同时设其中第 i 组糖有 ai 粒,那么琼斯夫人最倒霉的事情是,她把所有少于 k 粒的同色糖都买了,同时其他品种的糖每种都买了 k-1 粒,最后再买一粒才能得到 k 粒同色的糖.因而她最多需要花: m (n-m)(k-1)+1+ai i=1 分钱. 这品种型的标题特别多,又比方从52张纸牌中抽出7张同花的牌,那么最多需要抽多少张牌呢?显然需要 4(7-1)+1=25 张.【炙肉片的策略】约翰逊先生在户外有个炙肉架,正好能包容2片炙肉.他的妻子和女儿贝特西都饥肠辘辘,急不可耐.咨询怎么样才能在最短时间内炙完三片肉. 约翰逊先生:"瞧,炙一片肉的两面需要20分钟,由于每一面需要10分钟.我能够同时炙两片,因而花20分钟就能够炙完两片.再花20分钟炙第三片,全部炙完需要40分钟." 贝特西:"你能够更快些,爸爸.我刚算出你能够节约10分钟." 啊哈!贝特西小姐想出了什么妙主意? 为了说明贝特西的解法,设肉片为A,B,C.每片肉的两面记为1,2.第一个10分钟炙烤A1,和B1.把B肉片先放到一边.再花10分钟炙烤A2和C1.现在肉片A能够炙完.再花10分钟炙烤B2和C2,仅花30分钟就炙完了三片肉,对吗? 这个简单的组合咨询题,属于现代数学中称之为运筹学的分枝.这门学科奇异地向我们提醒了一个事实:假如有一系列操作,并希望再最短时间内完成,统筹安排这些操作的最正确方法并非立即就能一眼看出.初看是最正确的方法,实际上大有改良的余地.在上述咨询题中,关键在于炙完肉片的第一面后并不一定立即去炙其反面. 提出诸如此类的简单咨询题,能够采纳多种方式.例如,你能够改变炙肉架所能包容肉片的数目,或改变待炙肉片的数目,或两者都加以改变.另一种生成咨询题的方式是考虑物体不止有两个面,同时需要以某种方式把所有的面都予以"完成".例如,某人接到一个任务,把 n 个立方体的每一面都涂抹上红色油漆,但每个步骤只能够做到把 k 个立方体的顶面涂色. 今天,运筹学用于处理事物处理,工业,军事战略等等许多领域的实际咨询题.即便是像炙肉片如此简单的咨询题也是有意义的.为了说明这一点,请考虑以下一些变相咨询题: 琼斯先生和夫人有三件家务事要办. 1.用真空吸尘器清洁一层楼.只有一个真空吸尘器,需要时间30分钟. 2.用割草机修整草地.只用一台割草机,需要时间30分钟. 3.喂婴儿入睡,需要时间30分钟. 他们应该怎么样安排这些家务,以求在最短时间内全部完成呢?你看出这个咨询题与炙肉片咨询题是同构的吗?假设琼斯先生和夫人同时进展操作,一般人开场往往以为做完这些家务需要60分钟.但是假如一件家务(譬如说用真空吸尘器做清洁工作)分为两个阶段,第二阶段延后进展(像炙肉片咨询题那样),那么三件家务能够在3/4的时间内即45分钟内完成. 下面有一个关于预备三片热涂奶油的烤面包咨询题.这个运筹学咨询题比拟困难.烤面包架是老式的,两边各有一扇翼门,能够同时包容两片面包,但是只能单面烘烤.假如要烤双面,需要打开翼门,把面包片翻过身来. 将一片面包放入烤面包架需要时间3秒钟,取出来也需要3秒钟,将面包片在烤面包架内翻身又需要3秒钟.这些都需要双手操作,即不能同时进展放,取或把两片面包同时翻身,也不能在放入一片面包,将其翻身或取出的同时把另一片涂抹上奶油.单面烘烤一片面包需要30秒钟,把一片面包涂抹上奶油需要12秒钟. 每片面包仅限于单面涂抹上奶油.未经烘烤不得事先在任何一面涂抹上奶油.单面已经烤过的和涂抹上奶油的面包片能够重新放入烤面包加内接着烘烤其另一面.假如烤面包架一开场确实是热的,试咨询双面烘烤三片面包丙涂抹上奶油最少需要多少时间? 在两分钟内完成上述工作并不太难.然而,假如你领悟到:一片面包在单面烘烤尚未完毕的情况下,也能够取出,以后再放回烤面包架内接着烘烤这一面,那么全部烘烤时间就能够缩减至111秒钟.使你想到这一点,统筹安排这些操作使效率到达最高也远非是一件易事.在这方面,尚有无数比此更为复杂的实际咨询题,需要借助于与计算机和现代图论有关的高度复杂的数学手段.【乒乓球赛咨询题】某中学将举行乒乓球竞赛,小明他们班有5人先进展淘汰赛,选出一人参加学校的决赛,班主任杨教师计罢了一下竞赛的次数:"嗯,由于5是奇数,因而第一轮有一个队员轮空,第二轮中还得出现一次轮空,一共需要进展4场竞赛.选拔出一个队员后,学校共有37个班级参加决赛,也采纳淘汰赛,你明白需要多少场竞赛吗?你还没有算出来吗?哈哈!还在画表格呀?告诉你吧,每场竞赛淘汰一名队员,一共要淘汰36名队员,因而要进展36场竞赛.不过,假如你想轻易地算出轮空的次数却没有这么容易,那么,怎么样计算轮空的次数呢?,请看如下的分析: 不明白你留意了没有,假如竞赛人数正好是2的幂,那么轮空次数确实是0,也确实是说,假如竞赛人数是2,4,8,16,32等等,就不会出现轮空,假如不是如此类型的数,则至少要有一次轮空.假设有n个队员参赛,假如是奇数,那么第一轮就有一名队员要轮空,从第二轮开场的轮空数与(n+1)/2个队员参赛的轮空数是一样的,因而这时总的轮空数是:(用L(n)表示n个队员参赛的轮空数) L(n)=1+L(n+1)/2) 假如n是偶数,那么,第一轮没有轮空,从第二轮开场的轮空数与n/2个队员参赛的轮空数是一样的,因而有: L(n)=L(n)/2) 我们能够统一处理以上两个公式: L(n)=a0+L(n+a0)/2) 其中a0为1或为0取决于n的奇偶性,下面的a1,a2,a3.也一样,假定2k<n<2k+1,同时规定n>=2,由于最后总是冠亚军决赛,因而最后一场竞赛总是2名队员.接着往下推,我们有: L(n)=a0+a1+L(a0/4+a1/2+n/4) =a0+a1+a2+L(a0/8+a1/4+a2/2+n/8) =a0+a1+a2+.+ak-1+L(a0/2k+a2/2k-1+.+ak-1/2+n/2k) k-1 k-1 = as+L(1/2kas2s+n/2k) s=0 s=0 由于最后总有: k-1 1/2kas2s+n/2k=2 s=0 即: k-1 as2s=2k+1-n s=0 我们看到,L(n)=a0+a1+a2+.+ak-1 因而,只要将2k+1-n化成二进制表示,其系数和确实是轮空数,也确实是其中1的个数.关于n=37,我们能够算出2k+1-n=64-37=27=11011,其中有4个1,因而共有四次轮空.【玻璃杯咨询题】巴尼在汽水柜台工作,他用10只玻璃杯给两名顾客出了个难题.巴尼:"这一排有10只玻璃杯,左边5只内有汽水,右边5只空着,请你使这排杯子变成满杯与空杯互相交织,条件是只同意挪动4只杯子."两位顾客看了看巴尼,又看了看杯子,摇了摇头,不明白如何办.巴尼:"好吧,我来告诉你们,只要分别把第二只杯子和第七只杯子,第四只杯子和第九只杯子交换一下位置就成了." 这时,奎贝尔教授正好来到柜台前,看到了他们的把戏,同时来了点小花招.奎贝尔教授:"何需挪动四只杯子,我只要挪动两只就行了,你行不行?"巴尼疑惑地瞧着奎贝尔教授,不明就里.奎贝尔教授:"特别简单,只要拿起第二只杯子,把里面的汽水倒进第七只杯子,再拿起第四只杯子,把里面的汽水倒入第九只杯子就行了." 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 -> 尽管奎贝尔教授抓住话语间的模棱两可之处处理了这个咨询题,但这个咨询题并不像乍看上去那么简单.例如,依然这么个咨询题,但改成100只满杯挨着100只空杯排成一排,请考虑一下,假设要使其变成满杯和空杯交织陈列,需将多少对杯子互换位置?显然,一般地,假如有2n只杯子,n只满杯,n只空杯,需要将n/2对杯子互换位置,方法是2k号杯子与2k+n号杯子互换位置即可(k=1,2,3,.)假设n=100,则需互换50次. 有一个与上面分析的咨询题类似但困难的多的古典难题.我们这回用两种不同颜色的杯子作为道具,但是挪动方法却大相径庭:每次只能一块儿挪动一对相邻的杯子,使结果成交织陈列,以n=3为例,解题过程如以下图所示:1 2 3 4 5 6 普遍的解是什么呢?当n=1时,没有意义,n=2时你会发觉,无解,当n>2时,解此咨询题至少需要挪动n次.n=4时,求解特别不容易,你不妨试试,煞是有趣,或许你能够把当n>=3时的解题过程公式化.不像上两道题比拟容易,这个咨询题我还没有细心研究过,先把这道题上载,大家也能够发表意见. 依照这一难题还能够产生许多奇异的变相咨询题,用来测验你的智力.这里试着举几例: (1).仍然是同时挪动两只相邻的杯子,但是假如颜色不同,则要在挪动过程中交换位置,如此一对黑白的杯子就变成一对白黑陈列了.解8只杯子需要挪动5次.关于10只杯子,5次挪动也够了.我还尚不明白他的普遍解,也许你能找出来. (2).某种颜色的杯子少一个,即某种颜色的杯子有n只,另一种杯子有n+1只,其余规则不变,已经证明(不好意思,不是我证的,我还没有细心研究过),关于任意n只杯子,其解须作n次挪动,而且这是最少的挪动次数. (3).使用三种不同颜色的杯子.按照通常的方法挪动一对相邻的杯子,使得所有这三种颜色交相辉映.当n=3(共有9个杯子),其解需要作5次挪动.在这些变相咨询题中,假设在最终构成的陈列中,不同意留有任何空距.假好像意留有空距,则咨询题的解法就令人惊奇地变为挪动4次了. 看来,尚有许多其他的变化方式,例如,假设一次能够同时挪动3只或更多的杯子,在上述各变相咨询题中改用这种挪动方式,结果会如何呢?假设是第一次挪动1只杯子,第二次挪动2只杯子,第三次挪动3只杯子,依次下去,那又会怎么样?给定某种颜色的杯子n个,另一种颜色的杯子也为n个,这个咨询题的解是否总是作n次挪动?这种种咨询题都有待于人们去处理,我还没有时间来考虑这些咨询题,这是特别有趣特别值得人们考虑的趣题.【帕斯卡三角形与道路咨询题】苏珊特别为难.她步行去学校,路上老是遇到斯廷基.斯廷基:"嘿嘿,苏珊,我能够陪你一起走吗?" 苏珊:"不!请走开."苏珊心想:我有方法了.每天早上我走不同的道路去学校.如此斯廷基就不明白在哪儿找到我了.这张地图表示苏珊的住所和学校之间的所有街道.苏珊去学校时,走路的方向总是朝南或朝东.她总共有多少条道路呢? 苏珊:"我真想明白有多少条道路可走.让我想一想.要算出多少条道路看来并不简单.嗯.啊哈!一点不难,简单的特别!"苏珊想到了什么好主意?她的推理如下:苏珊:"在我家这个角点上写一个1,由于我只能从这一点出发.然后在遇刺相隔一个街区的两个角点上各写一个1,由于到那儿只有一条途径.现在,我在这个角点上写上2,由于到达那儿能够有两条途径.苏珊发觉2是1加1之和,她忽然领悟:假设到某一个仅有一条途径,则该角点上的数字为前一个角点上的数字;假设有两条途径,则为前两个角点上的数字之和. 苏珊:"瞧,又有四个角点标上了数字,我立即把其他角点也标上数字."请你替苏珊把剩下的角点标上数字,同时告诉她步行到学校共有多少条不同的道路. 苏珊的家H1 11 21 3 2 5 学校 G 剩下的5个点,自上而下,从左至右分别标以1,4,9,4,13.最后一点上的13表示苏珊去学校共有十三条最短途径. 苏珊所发觉的是一种快速而简单的算法,用来计算从她家到学校的最短途径共有多少条.要是她把这些途径一条一条地画出来,然后再计数,如此确信烦恼,还容易出错.假如街道的数目特别多,那么这种方法根本就行不通.你不妨把这十三条道路都画出来,如此你就更能体会到苏珊的算法是多么地有效了. 你对这种算法是否已经理解,能够再画一些不同的街道网络,然后用这种算法来确定从任意点A到另一任意点B的最短道路共有多少条.网络能够是矩形网格,三角形网格,平行四边形网格和蜂窝状的正六边形网格.也能够用其他方法(例如组合公式)求解,但这种方法十分复杂,需要特别高的技巧. 在国际象棋棋盘上,"车"从棋盘的一角到对角线上另一角的最短途径共有多少条?就像苏珊给街道交点标上数字一样,把棋盘上所有格子也都填上数字,因而咨询题就迎刃而解了."车"只能沿着右上方向朝另一个角的目的挪动,便能够求出共有多少条最短途径.如下图:183612033079217163432172884210462924171616215612625246279215153570126210330141020355684120136101521283612345678车1111111 把整个棋盘正确标号,依照所标的数字,一眼就能看出在棋盘上从一个角出发到任意一角,有多少条最短道路.右上角的数字是3432,因而"车"从一角到对角线的另一角的最短途径共有3432条. 让我们把棋盘沿着左上至右下的对角线一截为二,使其成为如以下图所示的阵列.此三角形上的数字与著名的怕斯卡三角形(我国叫做杨辉三角形)的数字是一样的,所以,计算街道途径条数的算法,恰恰确实是构造怕斯卡三角形所依照的过程.这种同构现象使得怕斯卡三角构成为无数有趣特性的不竭的源泉.11 11 2 11 3 3 11 4 6 4 1. 利用怕斯卡三角形立即能够求出二项式展开的系数,即求(a+b)的任意次幂,同样也能够用来解出初等概率论中的许多咨询题.请留意,上图中自顶部至底部,从边沿一格来说是1,随着向中间挪动,数字逐步增加.也许你见过依照怕斯卡三角形所制成的一种装置:在一快倾斜的板上,成百个小球滚过木钉进入各格的底部.全部小球呈现出一条钟形的二项式分布曲线,由于到达每个底部孔位的最短途径的条数确实是二项式展开的系数. 显然,苏珊的算法同样适用于由矩阵格子组成的三维构造.设有一个边长为3的立方体,分成27个立方体单元,把它看成棋盘,处于某一个角格上的"车"能够向三个坐标上的任何位置作直线挪动,试咨询"车"到空间对角线的另一个角格有多少条最短途径?【错抱的婴儿咨询题】在某个医院,四个婴儿的身份标签被搞错了.两个婴儿的标签不错,其他两个婴儿的标签弄错了.发生这种错误的情况有多少种?一种简单的计算方法是把所有可能的情况列成一个表格,其结果说明两个婴儿搞错的情况共有六种.现在假设标签搞乱了后,恰有三个是正确的,只有一个搞错了,咨询这个咨询题有多少种不同情况?你是否用列表的方法求解?依然凭灵机一动想出来的? A B D CA D C BA C B DD B C AC B A DB A C D 这个咨询题许多人都茫然不解,其缘故是他们作了以下错误的假设:在四个婴儿中,三个婴儿与其标签相符的情况有许多种.但是你假如用"鸽笼原理"思索一下,情况就一清二楚了.假设有四个鸽笼,一一标出应放物品的名称.假设三样物品都放在了正确的位置中,那么第四样物品只有一处可放,自然该处即为那件物品应放的位置,正确的可能只有一种,即所有四样物品都放置恰当这一情况,而不可能有其他更多的情况.一般地,假如 n 件物品,其中已经有 n-1件放对了地点,那么剩下的一件也必定放置在正确的位置上了. 有一个关于三样东西都标签错误的古典咨询题.一旦领悟到能够把情况的数目缩小为1,这个咨询题也就迎刃而解了.设在桌子上有三个盖着盖子的盒子,其中一个盒子内有两粒绿豆,第二个盒子内有两粒红豆,另一个盒子内有一粒绿豆和一粒红豆,三个盒子盖子上分别写着"红豆","红绿豆"和"绿豆",但是所有标签都标错了.你能从任意一个盒子内取出一粒豆子后,便能推断出所有盒子内都装着什么豆子吗? 同上面的讨论一样,人们一般总是首先考虑有多少种不同的可能性,但是你假如能够洞悉底蕴,一眼就能够看出只可能有一种情况,从误标为"红绿豆"的盒子中取出一粒豆子,假如不是一粒绿豆确实是一粒红豆,假设是一粒绿豆,那么盒子里的另一粒也必定是一粒绿豆,那么两粒红豆必定在标着"绿豆"的盒子内,反之,假设取出的是一粒红豆,那么另一粒必定也是红豆,两粒绿豆确信放在标着"红豆"的盒子内,其他一盒内的情况就一清二楚了.能够看出,三个盒子全都误标的情况只可能有如上两种.从标着"红绿豆"的盒子内取出一粒便能够排除一种情况,仅剩下唯一正确的情况. 有时,上述咨询题也会以略微复杂的方式出现.在三个盒子中,从任意一个盒子内取出最少的豆子数进展试看,以此来推断三个盒子内各装有什么豆子.唯一的方法是从标着"红绿豆"的盒子中取出一粒豆子试看.也许你能提出一些更加复杂的咨询题,诸如每个盒子内不只两粒豆子,或者盒子不只三个等等. 其他许多发人深省的难题都与上面的婴儿咨询题有关,同样也涉及到初等概率论.例如,假设婴儿的标签以随机的方式搞乱,那么四个标签全部正确的概率是多少?全部弄错的概率是多少?至少有一个正确的概率是多少?恰好有一个正确的概率是多少?至少有两个正确的概率是多少?恰好有两个正确的概率是多少?最多有两个正确的概率又是多少?诸如此类,不一而足. "至少一个"的咨询题,就一般的方式来说,属于古典兴趣数学著作中的咨询题.这个咨询题通常如下所述:在一家旅店,由 n 个人在细心检查本人的帽子.存放部的粗心女郎没能使存放牌和帽子做到一一对应,她随意地把存放牌发了出去,咨询至少一人取回本人的帽子的概率是多少呢?结果发觉,当 n 增大时,其概率迅速地趋近于极限 (1-1/e),或者说比1/2略微好一点,其中 e 是著名的欧拉常数,等于2.71828182845904590.,在概率论咨询题中经常反复地出现.【塑料杯咨询题】奎贝尔教授出了个难题.奎贝尔教授:"取三个喝咖啡用的泡沫塑料空杯,把11枚硬币投入杯子中,要求每一只杯子中的硬币数目都是奇数.奎贝尔教授:"这不难做到,是吗?方法特别多,你能够在一只杯子中放入一枚硬币,第二只杯子中放入三枚硬币,最后一个杯子中放入七枚硬币.这确实特别容易.奎贝尔教授:"但是,你能否把十枚硬币放入同样的杯子中,使得每只杯子中的硬币数都是奇数?这也是能够办到的,不过你得动点脑筋才行.奎贝尔教授:"但愿你还没有气馁.你只要想到把其中一只杯子放入另一只装着偶数个硬币的杯子中,就使每只杯子中都是奇数枚硬币了." 啊哈!一旦悟出杯中套杯,同一个集合的硬币能够属于不止一只杯子,这个棘手的咨询题也就迎刃而解了.用集合论的术语来说,我们的解是7个元素的集合和3个元素的集合,后一个集合又包含1个元素的子集.此解能够用图表示如下: 1 2 7 试求所有其余的解亦特别有趣.要得到十个解并不困难,上述解法即为其中之一.但假设要发觉其余的五个解,或者说十五个全部的解,却还需要花费一番精力.求出十五个解之后,能够把硬币和杯子的数目,以及关于每只杯中放入硬币数的要求作一些改变,从而产生一些新的咨询题.领悟到一个集合的部分或全部能够包含于另一个集合之中,从而能够作两次计算,这是处理许多著名难题和悖论咨询题的钥匙.下面是一个兴趣咨询题. 一个男小孩逃学已经数周,学校考勤人员找到了他.小孩开场向他解释为何没有时间上学: "我每天睡觉需要8小时,8X365总共2920小时,一天有24小时,因而2920/24即122天. "星期六和星期日不用上学.一年总共约有104天. "我们还有60天暑假. "我一天吃饭需要花3小时,一年就要3X365,共有1095 小时,共有1095/24即45天左右. "我每天还需要2小时的课外活动.算起来一年也要有2X365,共730小时,或730/24即30天左右." 小孩把所有这些天数相加如下:睡觉 122周末 104暑假 60用餐 45课外活动 30 - 361天 "你瞧,"小孩说"仅剩下4天用作病假,我还没把学校每年应放的节假日算进去呢!" 考勤人员听了后对小孩的数字研究了半天,看不出有什么破绽.请你的朋友们试试这个悖论咨询题,看有多少人能够指出其错误所在,即把子集不止一次地算进去.这小孩所说的各项就像奎贝尔教授杯子中套杯子的硬币一样重复地作了相加.【难铺的瓷砖】布朗先生的院子里铺有40块四方瓷砖.这些瓷砖已经破损老化,他想予以更新.他为修整院子选购新的瓷砖.惋惜,目前商店里只供给长方形的瓷砖,每块等于原来的两块.店主:"布朗先生,您需要几块?".布朗先生:"嗯,我要更换40块方瓷砖,因而我可能需要20块." 布朗先生试着用刚买的新瓷砖铺院子,结果弄得烦闷不堪.不管他怎么样努力,总是无法铺好. 贝特西:"出了什么咨询题?爸爸?" 布朗先生:"这些该死的瓷砖,真叫人恼火.最后总是剩下两个方格没法铺上瓷砖." 布朗先生的女儿画了一张院子的平面图,同时涂上了颜色,看上去好像一张棋盘.然后她沉思了几分钟. 贝特西:"啊哈!我看出症结的所在了.请设想每块长方形瓷砖必定盖住一个红色的格子和一个白色的格子,咨询题就清晰了."这里面有什么微妙,你理解贝特西的意思吗? 共有19个白色的格子和21个红色的格子,因而铺了19块瓷砖后,总要剩下2个红格没有铺,而一块长方形瓷砖是无法盖住2个红格的.唯一的方法是把最后一块长方形瓷砖断为两块.AABBCKKLLMCDJTSUMNDJQSRRNEIQPPOOEIHHGGFF 布朗先生的女儿利用所谓"奇偶校验"解答了铺瓷砖咨询题.假如两个数都是奇数或都是偶数,则称其为具有一样的奇偶性,假如一个数是奇数,另一个数是偶数,则称其具有相反的奇偶性.在组合几何中,经常会遇到类似的情况. 在这个咨询题中,同色的两个格子具有一样的奇偶性,异色的两个格子具有相反的奇偶性.长方形瓷砖显然只能覆盖具有相反奇偶性的一对格子.布朗小姐首先说明,把19块长方形瓷砖在院子内铺上后,只有在剩下的两个方格具有相反的奇偶性时,才能把最后一块长方形瓷砖铺上.由于剩下的两个方格具有一样的奇偶性,因而无法铺上最后一块长方形瓷砖.因而用20块长方形瓷砖来铺满院子是不可能的. 数学中许多著名的不可能性的证明都建立在奇偶校验上.也许你特别熟悉欧几里德的著名证明:2的平方根不可能是一个有理数.证明是如此进展的:首先假设此平方根能够表示成一个既约的有理分数,则分子和分母不可能都是偶数,否则它就不是一个既约分数.分子,分母可能都是奇数或者一个是奇数,另一个是偶数.欧几里德证明接着论证此分数不可能属于上述两种情况,换句话说,分子和分母不可能具有一样的奇偶性或相反的奇偶性.而任何有理分数是两者必居其一,因而反证了2的平方根不可能是一个有理数. 在铺砌理论中,有许多必定要用奇偶校验才能论证其不可能性的咨询题.上述咨询题只是个极其简单的例子,由于它仅仅涉及用多米诺骨牌,即简单的,不平凡的波利米诺来铺砌.(一个波利米诺是一些边沿相连的单位正方形的集合)布朗小姐的不可能性证明适用于符合以下要求的单位方格矩阵:这种矩阵假设按照棋盘那样涂色后,一种颜色的方格要比另一种颜色的方格至少多一个. 在上述咨询题中,能够把院子看作缺少两个同色方格的一个6X7矩阵.显然,假如缺少的两个方格同色,20个多米诺骨牌无法覆盖其余的40个方格.一个有趣的并与此有关的咨询题是:假如缺少两个颜色不同的方格,20个多米诺骨牌是否能够覆盖住那缺格的6X7矩阵?尽管奇偶校验没有证明其不可能性,但着并不意味着一定能够覆盖.通过擦去一对异色的方格,能够生成所有可能的图形.但假设逐一加以研究则不胜其烦,由于各种可能的情况太多,以致于无法分析.关于所有的情况来说,是否有一种简单的可能性证明? 有的,此证明既简单又巧妙,为拉尔夫.戈莫里妙手偶得之.他同样也是利用了奇偶原理.假设此6X7矩阵有一条涉及整个内部的闭合回路,宽度为一格.假设把闭合回路上任何两个异色方格擦去,因而该闭合回路就一断为二,每一部分都是由格数成偶数的异色方格组成.显然,这两部分的路总是能够用多米诺骨牌覆盖(把骨牌看作能够停在弯曲车道上的篷车).你也许愿意尝试一下,把这个巧妙的证明应用于尺寸,形状与此不同的矩阵,也能够考虑擦去不止两个方格的情况. 铺砌理论作为组合几何中的一个范围广泛的领域,越来越遭到人们的注目.要铺砌的平面能够是任何形状-"有限的或无限的",瓷砖也能够五花八门,而且咨询题可能会涉及不同形状的集合,而并非要求单一方式.不可能性证明还经常涉及以某种规定的方式,用两种或两种以上的颜色为某一平面着色. 与多米诺骨牌类似的三维物体是砖块,其单位尺寸为1X2X4.用这种砖块"堆"成(空间铺砌)一个4X4X4的箱体并不困难,但是用这种砖块可否堆成一个6X6X6的箱体?这个咨询题完全能够应用布朗先生铺砌院子的咨询题的解法.设想把该立方体分成27个小立方体,每个为2X2X2.把这些阶为2的立方体交替涂上黑白两种颜色,好像一个三维的国际象棋棋盘.假如你把每种颜色的单位立方体的个数数一下,就会发觉,一种颜色的立方体比另一种颜色的多八个. 在那大立方体中,不管怎么样放置砖块,不多不少总是恰恰"盖住"一样的数目的黑色和白色的单位立方体,但一种颜色的单位立方体比另一种颜色的多八个,最初的26块砖不管怎么样放置,总会剩下同样颜色的八个单位立方体.因而无法安置第27块砖.假如诲人不倦地讨论所有可能的堆砌方式,以求证明这一点,如此做显然极其费事. 堆砌理论仅是三维空间堆砌理论的一部分.关于空间堆砌咨询题,各种材料文献正日趋增多.它们提出了大量悬而未决,引人入胜的咨询题,有许多咨询题的解法可应用于商品的纸箱包装和堆仓等等. 奇偶性在粒子物理学方面也起着特别重要的作用.1957年,两名中国血缘的美国物理学家(指杨振宁,李政道)由于他们在推翻著名的"宇称守恒定律"方面的奉献而获得诺贝尔奖金.但由于这一标题专业性太强,故此不做详述.但能够举一个有趣的硬币戏法的例子来说明奇偶性守恒的一种方式. 往桌子上抛一把硬币,数一下正面朝上的有多少,假设是偶数,则称正面朝上的硬币具有偶数性;假设是奇数,则称其具有奇数性.现在把一对硬币翻身,再翻第二对,第三对,任你翻转多少对.你将惊奇地发觉,不管翻转多少对,正面朝上的硬币的奇偶性一直不变.假如原来是奇数性,那么依然保持奇数性;假如原先是偶数性,则一直保持偶数性. 利用这一点能够耍一个巧妙的魔术.你背过身去,请人随心所欲地把硬币一对一对地翻转,再请他用手盖住其中任何一枚.然后,你回过身来,瞧一瞧硬币,即可正确地说出他手掌下的硬币是正面朝上依然反面朝上.秘诀是开场时数一下正面朝上的硬币有多少,记住是奇数依然偶数.由于一对一对地将硬币翻转并不会妨碍其原来的奇偶性,因而你只要在最后再把正面朝上的硬币数一下,就可确定被盖住的那枚硬币是正面朝上依然反面朝上了. 还有一个变相的咨询题:请他用手盖住两枚硬币,你再说出盖住的那一对硬币其朝上一面是否一样.许多心算扑克牌把戏的巧妙魔术都是利用奇偶校验来设计的.【药品混乱咨询题】一家药店收到运来的某种药品十瓶。每瓶装药丸1000粒。药剂师怀特先生刚把药瓶送上架子，一封电报接踵而来。怀特先生把电报念给药店经理布莱克小姐听。 怀特先生：“特急！所有药瓶须检查后方能出售。由于失误，其中有一瓶药丸每粒超重10毫克。请即退回分量有误的那瓶药。怀特先生特别气恼。 怀特先生：“倒霉极了，我只好从每瓶中取出一粒来秤一下。真是胡闹。 怀特先生刚要动手，布莱克小姐拦住了他。布莱克小姐：“等一下，没必要秤十次，只需秤一次就够了。这如何可能呢？ 布莱克小姐的妙主意是从第一瓶中取出1粒，从第二瓶中取出2粒，第三瓶中取出3粒，以此类推，直至从第十瓶中取出10粒。把这55粒药丸放在秤上，记下总重量。假如重5510毫克，也确实是超过规格10毫克，她当即明白其中只有一粒是超重的，同时是从第一瓶中取出的。 假如总重量超过规格20毫克，则其中有2粒超重，同时是从第二瓶中取出的，以此类推进展推断。因而布莱克小姐只要秤一次，不是吗？ 六个月后，药店又收到此种药品十瓶。一封加急电报又接踵而至，指出发生了一个更糟糕的错误。 这一次，对超重药丸的瓶数无可奉告。怀特先生气恼极了。怀特先生：“布莱克小姐，如何办？我们上次的方法不中用了。布莱克小姐没有立即答复，她在思索这个咨询题。 布莱克小姐：“不错。但假如把那个方法改变一下，我们仍然只需秤一次就能把分量有误的药品识别出来。这回布莱克小姐又有什么好主意？ 在第一个秤药丸咨询题中，我们明白只有一瓶药丸超重。从每瓶中取出不同数目的药丸（最简单的方式确实是采纳计数序列），我们就可使一组数字和一组药瓶成为一一对应的关系。 为理处理第二个咨询题，我们必须用一个数字序列把每瓶药单独标上某个数字，且此序列中的每一个子集必须有一个单独的和。有没有如此的序列？有的，最简单的确实是以下二重序列：1，2，4，8，16，。这些数字是2的连续次幂，这一序列为二进制记数法奠定了根底。 在这个咨询题中，解法是把药瓶排成一行，从第一瓶中取出1粒，从第二瓶中取出2粒，从第三瓶中取出4粒，以此类推。取出的药丸放在秤上秤一下。假设总重量超重270毫克，由于每粒分量有误的药丸超重10毫克，因而我们把270除以10，得到27，即为超重药丸的粒数。把27化成二进制数：11011。在11011中自右至左，第一，二，四，五位上的“1”表示其权值分别为1，2，8，16。因而分量有误的药瓶是第一，二，四，五瓶。 在由2的幂组成的集合中，每个正整数是单一的不同组合中的元素之和。鉴于这一事实，二进制记数法极为有用。在计算机科学和大量应用数学领域中，二进制记数法是必不可少的。在兴趣数学方面，同样也有难以计数的应用。 这里有一个简单的扑克魔术，可叫你的朋友莫明其妙。这个戏法也许看上去与药瓶咨询题毫无关系，但他们的依照是一样的，都是二进制原理。 请别人把一副牌洗过，然后放进你的口袋，再请人说出一个1至15以内的数字。然后你把手插进你的口袋里，一伸手就取出一组牌，其数值相加正好等于他所说的数字。 此机密简单的特别。在耍魔术之前，预先取出A，2，4，8各一张放入口袋。这副牌缺少区区四张，不大可能为人发觉。洗过的牌放入口袋后，背地将其排置于原先已经放在口袋中的四张牌的后面。请别人说出一个数字，你用心算将此数表示成2的幂的和。假如是10，那你就应想到：8+2=10，随即伸手入袋，取出2和8的牌示众。 卜算卡片的依照也是二进制原理，预备六张卡片，分别记为A，B，C，D，E，F。然后将一些数字填写在卡片上，确定每张卡片上的数字集合的规则是如此的：在一个数的二进制表示中，假设右起第一位是“1”，则此数字就在卡片A上。该卡片上的数字集合自1起始，全部数字确实是1至63范围内所有的奇数；卡片B则包括1至63范围内的二进制记数法中右起第二位为“1”的全部数字；卡片C包括1至63范围内的二进制记数法中右起第三位为“1”的全部数字；卡片D，E，F以此类推。留意：63这个数字的二进制记数法是“111111”，每一位都是“1”，因而每张卡片上都有这个数字。 这六张卡片能够用来确定1至63范围内的任意一个数字。请一位观众想好此范围内的一个数字（例如某个人的年龄），然后请他把所有上面有此数字的卡片都交给你
