啊哈灵机一动(中译本20世纪科普经典特藏)

作者简介

马丁·伽德纳(Martin Gardner),1914年生于美国俄克拉荷马州的塔尔萨，1936毕业于芝加哥大学哲学系。l957年，伽德纳在《科学美国人》杂志上开设了一个数学游戏专栏，这个专栏一直延续了四分之一个世纪，成为杂志的一个招牌栏目。他的数学科普著作被翻译成多国文字出版。由于数学科普方面的贡献，他荣获l987年美国数学会斯蒂尔奖和l994年数学交流奖。

内容简介

1 组合
　　关于排列的谜题
　　组合分析，或者说组合数学，是研究如何对事物进行排列的。用稍为专业性的语言来表述，组合分析是将诸元素按不同的规则和特性组合为集合的研究方法。
　　例如，本章第一个问题是关于不同颜色的球的分组方法。这个问题要求读者按某一特性找到彩球的最小集合。第二个问题是关于参赛者按图表以淘汰制分组的方法—这是计算机科学中与数据分类有关的问题。
　　组合分析通常要找到根据某种规则进行分组的全部组合的总数。如所谓“穷举问题”在苏珊上学路径中的应用，在这个问题上，组合的元素是由方格的边组成的路径中的线段，由于涉及几何图形，我们称其为组合几何。
　　每个数学分支都有其组合问题，你将在本书各节中找到它们。有组合算术，组合拓扑，组合逻辑，组合集合论—甚至组合语言，这将在关于字、词、句的谜题一章看到。组合数学在概率论中尤为重要，在建立一个概率公式之前必须列出所有事件所有可能的组合。有一本著名的概率问题集叫作“机会与选择”，题目中“机会”这个词指的就是组合因素。
　　我们第一个问题就涉及概率，因为它要找出彩色糖球能确保（概率为1）满足某种特定要求的排列方式，文中讲述到，从计算元素的组合方式数的简单问题出发，可以引出许多概率问题。在“苏珊上学路径问题”中，可以看到帕斯卡三角在初等概率问题中的应用。
　　对于一个给定的组合问题符合要求的组合方式可能没有，可能只有一种，也可能有几种或无数种。例如，没有一种两个奇数的组合能使这两个奇数的和仍是奇数。只有一种两个质数的组合，使得这两个质数的积是21，满足两个正整数的和是7的组合有三种，有无限多种两个偶数的组合使得它们的和仍是偶数。
　　在组合理论中要找到“不可能事件”，即没有满足要求的组合，往往是极其困难的。例如，直到最近才证明地图的绘制不需要五种颜色，这在组合拓扑中曾是一个著名的长期未能解决的难题，这个不可能证明需要庞杂的计算机程序。
　　另一方面，许多初看很难证明其不可能性的组合问题，在找到某个“窍门”之后却很容易证明。在“瓷砖铺地”问题中，我们看到简单的奇偶检验就可证明用其他方式很难证明的组合的不可能性。
　　第二个关于药品混淆问题把组合思想与各种不同进位制的算术结合起来。我们看到，数的本身及其在位置计数法中的表示方式都决定于组合规则。事实上，一切演绎推理，无论是数学的还是纯逻辑的，都可看作是按某一系统的规则处理一串符号的组合。这就是为什么17世纪组合学的创始人莱布尼茨称演绎推理为组合的艺术。
　　糖球问题
　　琼斯太太路过一个口香糖球售货机时，想尽快地走过去，以免她的双胞胎孩子看到糖球。
　　第一个孩子：妈，我想要口香糖球。
　　第二个孩子：妈，我也要，我要和比利一样颜色的。
　　糖球售货机差不多空了，无法确定下一个出来的糖球是什么颜色，琼斯太太要想得到两个同样的糖球，她必须准备花多少钱？
　　琼斯太太可以花6角钱买2个红球—其中4角钱买所有白球，另2角钱买一对红球；或者花8角钱买2个白球。所以她必须准备8角钱，对吗？
　　当然不对。如果头两个球颜色不一样，那么第三个球必与前两个球中的一个颜色相同，所以3角钱就足够了。
　　现在假设售货机中有6个红球，4个白球，5个蓝球，你能算出琼斯太太需花多少钱才能保证买到一对同样颜色的球吗？
　　4角钱？你算对了。现在请你再思考一下，如果史密斯太太带着她的三胞胎从同一个口香糖球售货机旁走过，情况又会怎样？
　　这次售货机中有6个红糖球，4个白糖球和1个蓝糖球，史密斯太太要花多少钱才能保证买到3个颜色一样的糖球？
　　需要多少钱
　　第二个糖球问题实际上只是第一个糖球问题稍加变化而已，可以用同样的思路来解决。在这个问题中，取头3个球时，可能得到3种不同的颜色—红色、白色和蓝色。这是一种最糟糕的情况，即达到目的前抽取的次数最多，不过第四个球一定与前3个球中的1个相同。所以只要买4个球必能得到相同的2个球，琼斯太太要准备4角钱。
　　显然，这一情形可以推广：对于n组球，每组1种颜色，要想得到2个同样颜色的球，只要买n+1个球即可。
　　第三个问题比较难一些，史密斯太太的孩子是三胞胎而不是双胞胎，售货机中有6个红球，4个白球和1个蓝球，她得花多少钱才能买到3个同样颜色的球？
　　同上，我们首先要考虑最坏的情形，即史密斯太太先买到2个红球，2个白球和1个唯一的蓝球，总共5个球，那么，第6个球肯定是红球或白球。所以要使三胞胎都得到同样颜色的球，答案是6角钱。假如蓝球不止1个，就有可能每种颜色先抽出2个，那么第7个球就能满足三胞胎的要求。
　　噢！这里的关键在于搞清楚“最坏情形”的长度。如果我们采用笨办法给这11个球标上字母，然后检查字母所有可能排出的序列，看看哪个序列在出现3个同色球之前的部分序列是最长的。但是，这种解决办法需列出11！=39316800种排列，即使同样颜色的球不使用相同的字母来区分，也要列出2310种排列。
　　总之，要抽取k个同色球的方法如下：有n组球（每组1个颜色，每组至少k个），那么要得到k个同色球必须抽取n(k-1)+1个球。如果一组球或多组球的球数少于k个，情况又会怎样？请你不妨研究一下，那是颇有趣味的。