《精编》有趣的数学难题.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=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/2k∑as2s+n/2k) s=0 s=0 由于最后总有: 　 k-1 1/2k∑as2s+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).某种颜色的杯子少一个,即某种颜色的杯子有。