[转帖]妙想奇思——趣味数学谜题
<P>希望大家喜欢</P>奇妙的组合——关于排列的迷题
<Palign=left>组合分析，即组合学，是研究事件如何排列的。用专业的说法，组合分析是将诸元素按不同的规则和特性组合为集合的研究方法。</P><Palign=left> </P>
<Palign=left>例如，第一个问题是关于不同颜色的球的分组方法。这个问题要求读者按某一特性找到彩球的最小集合。第二个问题是关于参赛者按图表以淘汰制分组的方法——这也是计算机中重要的计算部分数据分类的问题。</P>
<Palign=left> </P>
<Palign=left>组合分析通常要找到根据某种规则进行分组的全部组合，如所谓“穷举问题”在苏珊上学路径中的应用，在这个问题上，组合的元素是沿模型边缘的曲线路径，由于几何图形被引入，我们称其为组合几何。</P>
<Palign=left> </P>
<Palign=left>每个数学分支都有其组合问题，你将在本书各节中找到它们。有组合数学，组合拓扑，组合逻辑，组合集合理论——甚至组合语言，这将在语词游戏一章看到。组合学在概率理论方面尤为重要，在找到概率公式以前列举所有可能的组合是非常必要的。有一个著名的概率问题集叫作“机会与机遇”，题目中“机会”这个词指的就是组合因素。</P>
<Palign=left> </P>
<Palign=left>我们第一个问题涉及概率是因为彩球按某一特定要求排列，文中提出了如何解决类似的简单的概率问题。列举苏珊上学路径问题提供了帕斯卡三角在概率问题中的应用。解决已知组合问题的排列可能没有，可能只有一种，也可能有几种或无数种。没有一种两个奇数的组合能使这两个奇数的和仍是奇数。只有一种两个质数的组合，使得这两个质数的积是21，满足两个正整数的和是7的组合有三种，有无限多种两个偶数的组合使得它们的和仍是偶数。在组合理论中更多的是很难找到“不可能事件的证明”，即没有满足要求的组合。例如，直到最近才证明地图的绘制需要五种颜色，这在组合拓扑中曾是一个著名的无解问题，这个不可能证明需要庞杂的计算机程序。</P>
<Palign=left> </P>
<Palign=left>另一方面，许多最初很难证明其不可能性的组合问题，在具有了巧妙的想法后却很容易证明。在“恼人的花砖”问题中，我们看到简单的奇偶检验马上导致了用其它方式很难证明的组合的不可能性。</P>
<Palign=left> </P>
<Palign=left>关于小球的第二个问题把组合思想和不同数学体系的应用结合了起来。我们知道，可以依赖组合的规则，用数学做各个位置的记号，实际上，所有的推理，无论是数学的还是逻辑的，都能用一串组合符号来进行，不管这是不是合适的说法。</P>
<Palign=left> </P>
<Palign=left>所以17世纪组合学的创始人莱布尼茨称这种推论技巧为排列组</P>
<Palign=left></P>
<Palign=left></P>
<Palign=left>待续................</P>
口香糖问题
a．琼斯太太竭力想快点走过那个口香糖售货机，以免她的双胞胎看到。<BR>第一个孩子：妈，我想要口香糖。<BR>第二个孩子：妈，我也要，我要和比利一样的。 <BR>b．口香糖售货机差不多空了，没法知道下一个糖球是什么颜色，琼斯太太要想得到两个同样的糖球，她必须准备花多少钱? <BR>c．琼斯太太可以花6便士买2个红球——其中4便士买所有的白球，另2便士买一对红球；或者花8便士买2个白球。所以她必须准备8便士，对吗? <BR>d．错了。如果头两个球颜色不一样，那么第三个球必与其一相配，所以3便士就足够了。 <BR>e．现在假设机器中有6个红球，4个白球，5个蓝球，你能算出琼斯太太需花多少钱能买一对同样的球吗?<BR> f．如果史密斯太太带着她的三胞胎从同一个口香糖售货机旁过，你仔细想想，你认为4便士够吗? g．这次售货机中有6个红球，4个白球和一个蓝球，史密斯太太要花多少钱能买三个一样的球?<BR><BR><BR><Palign=left><B>需要多少钱?</B></P>
<Palign=left> </P>
<Palign=left>第二个口香糖问题是第一个口香糖问题的简单变化。可以用同样的思路来解决。在这个问题中，取头三个球可能是不同颜色——红色、白色和蓝色。这是没有达到预想结果的最长排列，第四个球一定与前三个球中的一个相同。所以只要买4个球必能得到相同的一对球，琼斯太太要准备4便士。 </P>
<Palign=left> </P>
<Palign=left>总之，对于n组球，每组一种颜色，就应准备买n+1个球。第三个问题比较难，史密斯太太是三胞胎而不是双胞胎，口香糖售货机中有6个红球，4个白球和1个蓝球，她得花多少钱才能买到3个同样的球? </P>
<Palign=left> </P>
<Palign=left>同上，我们首先要考虑最坏的情况，史密斯太太买到2个红球，2个白球和唯一的蓝球，总共5个红球，第6个球肯定是红球或白球。所以要使三胞胎都得到同样颜色的球，答案是6便士。假如蓝球不只一个，她每种颜色先抽2个，那么第7个球就能满足三胞胎的要求。</P>
<Palign=left> </P>
<Palign=left>噢!关键在于最“坏”情形的长。有人可能想通过给这11个球标上字母来解决这个问题，然后检查所有可能排列，看看在出现三个同样球的排列中哪个是最长的。但是这种解决办法需列出ll!=3931680O种排列，即使同样颜色的球不用字母区分，也要列出2310种排列。</P>
<Palign=left> </P>
<Palign=left>总之，要抽取k个同色球的方法如下：有n组球（每组一个颜色，每组至少k个)，那么要得到k个同色球必须抽取n（k--1）+1个球。你肯定还想研究一组球或多组球的球数少于k的情形。</P>
<Palign=left> </P>
<Palign=left>这种问题的模式也能用于其它方面。例如，你要从52张牌中抽取7张同花色的牌，你要抽几次?这里n=4，k=7，公式给出的答案是：4(7--1)+1=25。尽管这是些简单的组合问题，但引出了有趣而复杂的概率问题。比如．你从n张牌中抽取7张牌(n从7到24)，每次抽取后不再放回(显然，假如抽的张数小于7概率为0，如抽取25张以上概率为1)，同花色的概率是多少?如果抽取的牌再放回经冼脾后再抽概率又是多少?一个更难的问题是：无论牌是否放回，获得同花色牌的期望值(概率的平均值)是多大呢?</P>
乒乓问题
<TABLE cellSpacing=0 cellPadding=0 width=600 border=0><TR>
<TD width=277></TD>
<TD width=319>a．米拉德·费尔默中学乒乓球俱乐部的5名成员决定举办一次淘汰赛。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>b．教练解释他的比赛安排。<BR>教练：5是一个奇数，所以第一轮比赛一名队员轮空。第二轮比赛仍有一个轮空，需比赛4场。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>c．第二年乒乓球运动非常流行，俱乐部已拥有37名成员。教练还是按使轮空次数最少来安排比赛，你能算出要比多少场吗?</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>d．你还没算出来吗?你还在画表吗?你失去了好机会！每场比赛淘汰一名队员，有36名队员要被淘汰，要比36场，对吗?</TD></TR></TABLE>
<P><B><FONT size=4> </FONT></B></P>
<Palign=left><B>有多少人轮空</B></P>
<Palign=left> </P>
<Palign=left>如果你用直观的方法解决这个问题，你可以实际画一下37个人实际的比赛表。你可以看到无论怎样画，总有4个轮空。轮空数是比赛者人数n的函数，怎样来计算这个数呢?</P>
<Palign=left> </P>
<Palign=left>n已知，可按如下方祛确定轮空数。用2的最小指数幂，要求它大于等于n，减去n，差额用二进制来表示。二进制表达式中1的个数就是转空数。在我们的例子中，我们用64(2<SUP>6</SUP>)减去37得到27，用二进制表示27=11011，有4个1，所以比赛中共有4个轮空，这是满足这种奇妙算法的有趣验证。</P>
<Palign=left> </P>
<Palign=left>这种问题所描述的比赛被称为是淘汰赛。计算机专家们总结这种算法是通过成对比较，确定一组几个元素中最大元素。我们看到要确定最大值，实际需要n-1次比较，计算机处理器可以比较3组，4组，5组等等这样的集合。</P>
<Palign=left> </P>
<Palign=left>数据处理这个问题在计算机理论和应用上非常重要，所有的书都阐述这个问题。你可以很容易想到许多实际问题在数据处理方面的重要性。据估计，在科技、商业和工业方面花费在数据处理问题上的计算时间要占计算机运行时间的1/4。</P>
奎伯的杯子问题
<TABLEheight="85%" width="95%" align=center border=0><TR>
<TDvAlign=top width=* height="100%">
<DIV align=center>
<CENTER>
<TABLE cellSpacing=0 cellPadding=0 width=600 border=0>
<TR>
<TD width=319>a．巴尼在饮店工作，他给他的两位顾客表演10个杯子游戏。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>b．巴尼：这有一排10个杯子，前5个杯子装着可乐，后5个杯子空着，你能挪4个杯子，使满杯和空杯间隔排列吗?</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>c．巴尼：好，只需第2个杯子和第7个杯子交换位置，第4个杯子和第9个杯子交换位置。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>d．奎伯教授总想一些奇特的方法，碰巧听到了这个问题。<BR>奎伯教授：为什么要挪4个杯子，我们能否只动2个杯子?</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>e．奎伯教授：很简单，把第2个杯中的可乐倒进第7个杯中，把第4个杯中的可乐倒进第9个杯中。</TD></TR></TABLE></CENTER></DIV>
<P><B><FONT size=4> </FONT></B></P>
<Palign=left><B>不寻常的奎伯</B></P>
<Palign=left> </P>
<Palign=left>尽管奎伯教授通过巧辩解决了这个问题，但普遍问题并不像这个问题这么平常。例如，同样的问题，如果是100个满杯和100个空杯需要对调多少次才能使满杯和空杯间隔排列?</P>
<Palign=left> </P>
<Palign=left>用200个杯子做实验不很实际，我们首先分析较小的n值的解决方法，这里n是满杯或空杯数。你可以用两种颜色的记号来解题(或者牌的正反面、硬币的正反面、不同面值的硬币等等)当n=1时无解。n=2时显然只对调一次。n=3时也对调一次。进一步努力，你可以发现简单的公式，n是偶数时，对调数为n/2。n是奇数时，为(n—1)/2。所以，如果是100个满杯和100个空杯，需要对调50次。</P>
<Palign=left> </P>
<Palign=left>这需要移动100个杯子，奎伯的幽默作法把移动杯数减少了一半。</P>
<Palign=left> </P>
<Palign=left>又有一个类似的分隔同题，但比较难解。在同一排中有n个一类物体，相邻的是n个另一类物体(如上面用玻璃杯、记号、牌等来表示)你还是要把这一排列变为互相间隔状态，但我们移动原则不同了。我们必须移动一对记号放到队列中任何空白处，移动中不能改变这两个记号的顺序。例如，这是n=3时的做法：<BR><BR>XXXOOO<BR>XOOOXX<BR>X00XOX<BR> OXOXOX</P>
<Palign=left> </P>
<Palign=left>一般的解法是什么呢?n=1时无解。你很快也发现，n=2时也无解。对所有大于2的n，最小的移动次数是n。</P>
<Palign=left> </P>
<Palign=left>当n=4时，解决这个同题就很不易，或许你已经解决了，或许当n大于等于3时你能用公式来表示这个问题的解。</P>
<Palign=left> </P>
<Palign=left>这些问题变化一下，可以产生一些其它的难题：</P>
<Palign=left>(1)规则同前，只是当你移动一对记号时，如果是不同颜色的，在移动前交换它们的位置。也就是黑红对在移动前变为红黑对，8个记号移动5次可以完成，10个记号移动5次也可以完成。我们还不知道一般的解决方法，或许你能找到。</P>
<Palign=left> </P>
<Palign=left>(2)规则和原题一样，只是一种颜色的记号有n个，另一种颜色的记号有n+1个，并且只有颜色不同的一对才能移动。可以证明：无论n为何值，都需移动n<SUP>2</SUP>次，且这是最小的移动次数。</P>
<Palign=left> </P>
<Palign=left>(3)三种不同颜色的记号，移动每对相邻的记号使三种颜色相互间隔，如果n=3(即总共9个记号)需移5次。在以上的变化中，我们都设变化为最后排列时排列中没有空隙，如果允许空隙存住，移动4次就能得到结果。</P>
<Palign=left> </P>
<Palign=left>一些变化的假设迄今还没有提出来，更不必说解决了。比如，在以上的变化中，一次移动3个或更多相邻记号。</P>
<Palign=left> </P>
<Palign=left>还有，如果先移动1个记号，再移动2个相邻的记号，接下来是3个以至4个等等。已知各有n个两种颜色的记号，移动n次能解决问题吗?</P></TD></TR>
<TR>
<TD>
<DIV class=info></DIV></TD></TR></TABLE>
复杂的路
<TABLE cellSpacing=0 cellPadding=0 width=600 border=0><TR>
<TD width=277></TD>
<TD width=319>a．苏珊有一个问题，她上学时总遇到斯蒂克。<BR>斯蒂克：喂，苏珊。我和你一起走好吗?<BR>苏珊：讨厌，走开。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>b．苏珊：我有主意了，我每天早上上学都走不同的路，斯蒂克就找不到我了。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>c．这个图表示苏珊家和学校间的所有街道，图中苏珊上学这条路不是向东就是向南。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>d．这是苏珊上学的另一条路，到底有多少条路?</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>e．苏珊：我想知道到底我能走几条路，我想这很难算。嗨！一点儿也不难，太简单了！苏珊想到什么办法了?</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>f．苏珊：我在住处所在的角标上1，因为只有一个起点。再在这个角相邻的两个角标上1，因为只有1条路能到达。</TD></TR>
<TR>
<TD width=277> <BR>
<P align=center> </P></TD>
<TD width=319>g．苏珊：现在我把2标在这个角上，因为我能通过两条路到达这里。<BR>当苏珊意识到2是1加1的和时，她突然想到每个角的数字一定是相邻能到达这个角的两角的数字和。</TD></TR>
<TR>
<TD width=277>
<P align=center> <BR>
<P align=center> </P></TD>
<TD width=319>h．苏珊：已经标出了几个角，我马上就会标上其它角。<BR>你能为苏珊标上其它角并告诉她上学能走几条路吗？</TD></TR></TABLE>
<P><B><FONT size=4> </FONT></B></P>
<Palign=left><B>多少条路?</B></P>
<Palign=left> </P>
<Palign=left>剩下的五个顶点，从上至下，从左到右应标上1，4，9，4和13，最后一个顶点的13表示苏珊按最短路径有13条路去上学。</P>
<Palign=left> </P>
<Palign=left>苏珊的发现的确是计算学上最短径数的简单快捷的算法。如果她试图画出所有路径，再数它们那就太繁杂了，而且当街道网络量大时也是根本办不到的。当你实际画一下13条路径时，你会更好地体验算法的有效性。</P>
<Palign=left> </P>
<Palign=left> </P>
<Palign=left>为了检验你对这种算法的理解程度，试着画一下其它几种街道网络，并应用这种算法确定从顶点A到顶点B的最短路径的数量。图1给了这种类型的四个同题，它们也可用其它方法求解，如使用组合数学的公式，但这种方法太复杂了。</P>
<Palign=left> </P>
<Palign=left> </P>
<Palign=left>国际象棋中的车从棋盘的一角到达对角线另一角的最短路径数是多少呢?根据苏珊为街道标号的方法，通过为每个棋格标号很快就可解决。因为车只能沿直角(水平和垂直)移动，所以最短路径只能限制在向目标方向的移动上，如图2所示，整个棋盘已正确标记，标号马上就给出了从起始区域到盘上任何其它区域的最短路径数。右上<BR>角格中的数字是3432，所以车从一角沿对角线到另一角的最短路径数是3432条。</P>
<Palign=left> </P>
<Palign=left> </P>
<Palign=left>把棋盘沿对角线切成一半，然后转动成为图3所示的三角形。底排格中的数字就是从顶点到底排各格的最短路径数。这个三角形的标号和著名的帕斯卡三角形①中的数字是相等的。</P>
<Palign=left> </P>
<Palign=left>这种从顶到底最短路径的算法，准确地构成了帕斯卡三角形，这种同构的精确推<BR>广，就是帕斯卡三角形的迷人之处。由帕斯卡三角形马上就可得到二项式展开式各项的系数和一些基本概率问题的解答。注意图3中从三角形顶端到底部外边格中数字都是1，越往中心移数字越大，或许你见到过这种按帕斯卡三角形原理构造的装置，一块倾斜的板，几百个小球沿着桶滚入板底各栏、球准确地按漏斗型二项式函数曲线排列，这是因为进入每个口的最短路径致都是二项展开式的系数。</P>
<Palign=left> </P>
<Palign=left>苏珊算法同样适用于具有长体小格的立方体。想一想，边长3个单位的立方体被分为27个小立方体，有一个车在一个小格中，车可以沿三个座标方向平等移动，它沿着空间对角线到达另一端的最短路径数是多少呢?</P>
<Palign=left>————————</P>
<Palign=left>①中国人称之为杨辉三角，系中国南宋数学家杨辉发现。</P>
<Palign=center> </P>
混淆的婴儿
<TABLE cellSpacing=0 cellPadding=0 width=600 border=0><TR>
<TD width=277></TD>
<TD width=319>a．某医院，四名婴儿的身份卡弄混了，两名婴儿的卡是对的，另外两名是错的，发生这种情况的方式有多少种?</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>b．计算这个问题的简便方法就是把所有可能的情况列成表，它显示出当两名婴儿标错时有六种情况。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>c．现在假设标签混了以后，实际上三个对的，一个错的，发生这种情况又有几种方式。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>d．你还要画个表来算吗?或许你已经发现其奥妙了。</TD></TR></TABLE>
<P><B><FONT size=4> </FONT></B></P>
<Palign=left><B>弄错了的标签</B></P>
<Palign=left> </P>
<Palign=left>这个问题蒙混了许多人的原因是假设错误：有许多途径可以正确标识四个婴儿中的三个。如果按“鸽子窝原理”考虑，答案是显然的。假如有四个鸽子窝，每个都用它们的名字标记，如果三个鸽子放到它们各自的窝里，那么第四个鸽子只有一个口可进，当然是正确的口。只有一种情形而不是很多情形，显然这种情形下四个鸽子正确地放进窝里了。</P>
<Palign=left> </P>
<Palign=left>有一个著名的标识混淆的难题，也涉及三物体，解决的方法也靠巧妙的想法：把发生事件数减少到1。假设在桌上有三个密封的盒，一个盒中有2枚银币(l银币=10便士)，一个盒中有2枚镍币(1镍币=5便士)，还有一个盒中有1枚银币和l枚镍币。这些盒子被标上10便士、15便士和20便士，但每个标签都是错误的。现在，有人从一个盒中拿出1枚硬币放在盒前，看到这枚硬币，你能否说出每个盒内装的东西呢?</P>
<Palign=left> </P>
<Palign=left>同前一个问题，人们首先可能会认为有许多不同的可能性，但用正确的观点看只有一种情形。从错标15便士的盒中取出的硬币不是银币就是镍币。如果是1枚银币就知道这盒里原本装的是2枚银币，如果是镍币，这盒里原本装的就是2枚镍币。在这两种情形下，其它两盒内所装的东西也完全决定了。为了弄明白原因，可以画一个六种可能情形的表，可以看到三个盒子全部错标只有其中两种情形，从15便士的盒中取1枚硬币样品又排除一种情形，唯一剩下的一种情形就是正确的情况。</P>
<Palign=left> </P>
<Palign=left>这个问题有时给出的形式略难一些，让某人随便在哪个盒中取最小数目的硬币样本来确定三个盒子的内装物。当然，唯一的答案就是从15便士的盒中取1枚硬币。或许你还能发明更复杂的方法，当每个盒中有两个以上物体或是多于三个盒子的情况。</P>
<Palign=left> </P>
<Palign=left>许多吸引人的难题都和婴儿问题有密切联系，这也引入了基本的概率理论。比如，婴儿的标签随意混淆了，四个都对的概率是多少?都错的呢?至少一个对的呢?恰好一个对的呢?至少两个对的呢?恰好两个对的呢?至多两个对的呢?等等。</P>
<Palign=left> </P>
<Palign=left>以“至少一个”形式的问题，是著名的娱乐数学问题，它常以一个故事的形式给出，n个男人把帽子寄存在饭店里，粗心的存帽姑娘漫不经心，随便递出对号牌，那么至少有一个人能取回他自己帽子的概率是多少?当n增加时这个概率很快达到其极限(1-1/e)，略大于1/2。这里e是一个著名的相关系数，称作欧拉系数等于2.71828，它在概率问题中经常遇到，如同几何问题中</P>
奎伯的杯子
<TABLE cellSpacing=0 cellPadding=0 width=600 border=0><TR>
<TD width=319>a．奎伯教授又给你出了一个难题。<BR>奎伯教授：拿3个空塑料杯，放进11便士的硬币，使得每个杯中的数是奇数。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>b．奎伯教授：这并不难，可以有许多办法。你可以一个杯里放3个，一个杯里放7个，第3个杯里放1个。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>c．奎伯教授：但是，你能在3个杯中放10个便士使每个杯中仍是奇数吗?这是可能的，但需要你想一个巧妙的办法。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>d．奎伯教授：我希望你锲而不舍，你所要做的就是把一个杯子放进另一个杯子中去，这不是很容易吗?每个杯子中就都是奇数了。</TD></TR></TABLE>
<P><B><FONT size=4> </FONT></B></P>
<Palign=left><B>奎伯子集</B></P>
<Palign=left> </P>
<Palign=left>通过把一个杯子放进另一个杯子的灵感解决了奎伯的智力难题。同一组硬币可以属于不止一个杯子。用集合理论用语，我们的答案是一个7元素的集合加上一个3元素的集合，这个3元素的集合包括一个单元素子集。这个答案也可以用如下的圆表示：</P>
<Palign=left> </P>
<Palign=center> </P>
<Palign=left>你可能找到了其它的答案。很容易找到10个答案，但总共能找到15个答案。</P>
<Palign=left> </P>
<Palign=left>找到这15个答案以后，你就可以通过硬币数的变化，杯子数的变化以及每个杯子中硬币数的变化对这个问题归纳总结。</P>
<Palign=left> </P>
<Palign=left>一个集合的部分或全部可以包括在另一个集合中并且可以两次记数。这个根本观点可以解决许多著名的似是而非的难题，这里就有一个幽默故事。</P>
<Palign=left> </P>
<Palign=left>一个男孩逃学几周以后，教师来找他，这个男孩为他没时间上学作了解释。</P>
<Palign=left> </P>
<Palign=left>我每天睡8小时，8X365是2920小时，每天24小时，那么2920/24就是122天。</P>
<Palign=left> </P>
<Palign=left>星期六和星期天不上学，一年就是104天。</P>
<Palign=left> </P>
<Palign=left>我们还有60天暑假。</P>
<Palign=left> </P>
<Palign=left>我每无需要3小时吃饭，3X365是1095小时，1095/24就是45天。</P>
<Palign=left> </P>
<Palign=left>每天还至少有2小时娱乐，2X365是730小时，730/24就是30天。</P>
<Palign=left> </P>
<Palign=left>男孩把这些数字记下来并加到一起。</P>
<Palign=left> </P>
<Palign=left>全部天数：</P>
<Palign=left>睡觉：l22</P>
<Palign=left>周末：104</P>
<Palign=left>暑假：60</P>
<Palign=left>吃饭：45</P>
<Palign=left>娱乐：30</P>
<Palign=left>361</P>
<Palign=left> </P>
<Palign=left>这个男孩说；“你瞧，我只剩下4天还病了，这我还没算每年学校的假日。”</P>
<Palign=left> </P>
<Palign=left>老师看了男孩前数字，没能找到错处。把这个问题讲给你的朋友，看看谁能发现错误：不只一次的计算子集。这个男孩问题的重选类型和奎伯杯子问题是一样的。</P>
牛排战略
<TABLE cellSpacing=0 cellPadding=0 width=600 border=0><TR>
<TD width=319>a．约翰逊先生有一个很小的烤架，只能烤两块牛排。他妻子和女儿贝齐都饿极了，问题是要在最短时间内烤三块牛排。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>b．约翰逊先生：让我们想想，烤一面需要10分钟，那么一块牛排烤两面需20分钟。因为一次只能烤两块牛排，20分钟烤好，另外2O分钟烤第三块，所以总共需要40分钟。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>c．贝齐：爸爸，你可以再快些。我刚算出你能节约10分钟。多聪明啊！贝齐是怎么想的？</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>d．为解释贝齐的算法，把牛排记作A、B和C，每面记为1和2，头10分钟里烤A1和B1。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>e．把牛排B放到一边，第二个10分钟烤A2和C1，A牛排烤完了。</TD></TR>
<TR>
<TD width=277>
<P align=center> </P>
<P align=center> </P></TD>
<TD width=319>f．下面的时间烤B2和C2，所有三块牛排只用30分钟，对吗?</TD></TR></TABLE>
<P><B><FONT size=4> </FONT></B></P>
<Palign=left><B>一般战略</B></P>
<Palign=left> </P>
<Palign=left>这个简单的组合问题是现代数学的一个重要分支，被称为“运筹学”。当一个人面临一系列的工作，并要在最短时间完成，制定工作时间表的最佳途径并不是很明显的。起先看来最好的方式，可能还会有更大改善之处。在这个问题中，我们恍然领悟到，牛排烤完第一面，不必马上就烤另一面。</P>
<Palign=left> </P>
<Palign=left>像这样的简单问题可以从很多方面来总结。比如，你可以改变烤架一次可烤牛排的数量，或者改变需烤牛排的数量，或者二者都变。另外还可考虑两面以上的物体，每面都要按某种方式“完成”。例如，一个人要把n个立方体涂成红色，但每一次可以只涂K个立方体的顶。</P>
<Palign=left> </P>
<Palign=left>今天，运筹学已被用来解决商业、工业和军事战略等许多领域的问题。为应用解决牛排问题的简单原理考虑下面的问题。</P>
<Palign=left> </P>
<Palign=left>琼斯先生和太太要干三项家务：</P>
<Palign=left>1．他们的地板要吸尘，他们只有一部吸尘器，干这活儿要30分钟。</P>
<Palign=left> </P>
<Palign=left>2．草坪需要修剪，他们只有一部割草机，这活儿也要花30分钟。</P>
<Palign=left> </P>
<Palign=left>3．他们的孩子要喂，还要哄他上床，这要用30分钟。</P>
<Palign=left> </P>
<Palign=left>他们应当怎样安排这些任务以便在最短时内完成呢?你看这个问题与牛排问题是否一样呢?如果琼斯先生和太太一起干，或许有人想60分钟可以干完。但是如果一项工作，比如说吸尘被分为两半，后半部分延迟(像牛排同题一样)，那么这三项工作只需3/4时间，即45分钟就够了。</P>
<Palign=left> </P>
<Palign=left>下面是一个更复杂的运筹学问题：制作三片奶油烤面包，烤炉是老式的，它的两边各有一个挂门，每次能烤两片面包，一边烤一片，只能烤一面，烤两面必须要打开门翻转。放进一片面包要3秒钟，取出一片面包要3秒钟。翻转要3秒钟，这些作业都要双手进行，因此不能同时放取或同时翻转两片面包，当放进、取出或翻转一片面包时，不能给另一片面包抹奶油。面包烤一面要30秒，一片面包抹奶油要12秒。每一片面包只在一面抹奶油，烤过的面才能抹。一片面包烤过一面，抹上奶油再送入烤炉烤另一面。烤炉已预热，多长时间面包才能烤好并抹上奶油?</P>
<Palign=left> </P>
<Palign=left>计算出这项工作需要2分钟并不很难。然而你要用如下观点，整个时间就可以减少到114秒：一片面包先烤一面，翻转，然后接着烤直至完成。</P>
<Palign=left> </P>
<Palign=left>以最有技的方式制定工作时间表决非易事，无数的实际问题在制定时间表时要比这个例子复杂得多，需要非常复杂的数学技巧，包括计算机和现代图论。</P>
页:
[1]