我唯一知道的事就是我一无所知 ----苏格拉底

本书是数学大师马丁.伽德纳所著，源自于一本科教杂志，为什么这样的集高学术水平和高施教水平的老师不能出现在中国？大多数中国人还是和以前一样，抱着所谓的国学成天研究，喜欢研究人与人之间的关系，对于自然科学的探索，对于大自然的好奇心，这正是我们国人所缺乏的，在如今的现代化社会中，科技的发展主要来自于自然科学，而科技已经是一个国家发展壮大的最主要的推动力，中国社会需要那种对于科学的热爱，那种求真的态度

组合数学

推测一件事情发生的概率，有三种方法
古典概率模型：基本空间由有限个元素或基本事件组成，其个数记为n，每个基本事件发生的可能性是相同的。若事件A包含m个基本事件，则定义事件A发生的概率为p（A）=m/n
几何概率模型：随机试验中的基本事件有无穷多个，且每个基本事件发生是等可能的，这时就不能使用古典概率，于是产生了几何概率。几何概率的基本思想是把事件与几何区域对应，利用几何区域的度量来计算事件发生的概率，布丰投针问题是应用几何概率的一个典型例子

“组合数学 + 古典概率模型"
为求概率提供了相当不错的思路

巧妙的借用

这个方法最早是从老头分马那儿看到的:一个富翁，留下17匹马，分给3个儿子，大儿子分1/2，二儿子分1/3，三儿子分1/9。聪明的老头牵了一头马来，分完后，又牵了回去，大家各得其所

分马问题虽然巧妙，给人一种思维启发，但是不具有普遍性，高中学数学的时候，多项式的因式分解就经常通过先加一个数，然后减去同一个数来达到目的，这才是借用的普遍用法，这种方法改变了的条件的状态，使之利于求解

本书中有这样一个有意思的问题：有一次n人参加的一对一的淘汰赛，估计出比赛轮空的总人数。这种问题当然可以在纸上通过一步一步的演算得出结果，但是如果n比较大，那会是相当耗时，书上有一个很妙的解法，先找到一个最小的m
，使得m + n = A（A是2的x次方），把n和m看成是二进制，m中1的个数，就是最终的解

为什么这样解可以呢？

首先，我们通过巧妙的借用m来使得出现了A这样一个数，因为A是2的x次方，所以A场比赛就可以无人轮空的完整进行下去，现在我们就可以把A看成两个小组，第一组有n个人，第二组有m个人，m组每轮比赛可能会多出一个人，也可能刚刚好，如果是多出一个人，那么把这个人和第一组轮空的那个人进行比赛，这样就能使无人轮空的进行完所有比赛，这样m中多出的人数就是第一组n人中轮空的人数，即二进制表示的m中1的个数

这个巧妙的借用没有改变问题的形态，只是从问题的反面进行了求解

有时候我们单独对于一个解无从下手，只能通过巧妙的借用，达到一个有利于求解的状态，根据这个“借用”和“状态”来求所解

奇偶消除

在《编程之美》上有这么一道题：假如已知一个数在数组中出现的次数超过数组个数的一半，用最快的速度找出这个数。书中给出的解法就是建立两个空间，A和B，有两个属性，一是记录存放的是哪个元素，一个是记录存放该元素的个数，初始值都为0，代表为空，遍历一遍数组，如果A或B为空则把数组元素放入其中一个，并计A或B的值为1，如果出现重复的元素，则在相应的A或B上加1，当A和B都不为空时，A和B同时减一，这样遍历一遍数组，最后留在A或B中的元素就是所求解，这里虽然没有用到奇偶消除，但是把放在A和B中不同元素想象成正负离子，也算是异曲同工

这里用了一种巧妙的方法简化问题的规模，同时，不改变问题的性质，这与本书中的“铺砖理论”如出一辙，在一个地板砖上，有偶数个小方块，每次铺砖必须覆盖到四邻域内的连续两个小方块，怎样快速判断是否能完整铺完

书中给出的解法：
在四邻域内依次标记小方块为红色和白色的，由于每次铺砖必须覆盖到四邻域内的连续两个小方块，这样同色的方块就可以看成具有相同的奇偶性，每次覆盖必须是一对具有相反的奇偶性才行，这样如果最初红色和白色的个数不一样（如19,21），所以不能进行奇偶配对，最后留下会两个同色的方块，则肯定无法按要求铺完，这样就能把问题规模最后规约到判断最后一对方块的奇偶性

运用奇偶性理论可以做两件事
消除问题规模：铺砖问题
判断问题状态是否发生改变：奇偶校验；反过来想，利用某些我们指定的操作，保持问题的状态不变（翻硬币问题，如果每次必须翻一对，那么正面和反面的奇偶性将是保持不变）

数的表示

古罗马人对于数的表示很呆板，简单的用和来表示一个数，聪明的印度人创造了十进制，数的表示清晰易懂，后来计算机的出现，由于硬件的限制，又带来二进制，其实在生活中，有很多事情也可以用二进制来表示，其中的1和0就代表是与非

最经典的一个问题就是1000瓶药，有一瓶毒药，有十只老鼠，药效发作是一天，需要在这一天里面来判断哪瓶药是毒药
小老鼠吃不吃药就是一个1和0的问题，这样可以有2的10次方中表达，每种表达就能对应某一瓶药

如果一系列东西中某些东西只允许出现一次（即可以出现，或者不能出现），用二进制表示是最恰当的，比如说用一系列数字表达0~14，每个数字最多只能出现一次，那么最简洁的表达方式就是 1 2 4 8

图形

切蛋糕

对于一个平面的蛋糕，切n刀，最多能切出多少块？
因为第k刀与之前的每一刀最多只有一个交点，所以第k+1刀最多和已存在的k刀有k个交点，再加上边缘的两个交点，共k+2个交点，这样就会产生k+1条线，每条线把之前的切块一分为二，那么就会产生k + 1个新块

切第一刀，会有两块
如果切了n刀后的，切出的块数位m，那么n+1刀切出后的块数就应该是 m + （n + 1 + 1）

所以f(n)表示切n刀后的块数
f(n) = 1, n == 1
f(n) = f（n -1） + n + 1 , n > 1

又是一个归纳法！！！

逻辑推理

集体智慧推理

基于逻辑推理的归纳法

在多人参与的一个事件中，有一种推理，是基于参与这个事件的所有人有着和计算机一样的准确思维

例1，有三个人，头上可能会是红色帽子或者蓝色帽子，如果某人看到了谁戴了红色帽子，就举手，如果你是其中一位，看见了其余两人举手了（自己也举手说看到了红帽），当过了片刻还没有人说自己头上是什么帽子，要求猜出头上的帽子

有三个人的时候，分别为A,B,C，可以一步一步的进行简单的推理，如果我是A，我如果头上是蓝帽子，那么其余两个人就会看到一个是蓝色一个是红色，B看到C也举手了，说明他看到了红色，这样他就会知道自己头上戴的是红色，但是他不知道，所以我头上的是红色

这种情况可以推论到n个人，即有n个人，头上可能会是红色帽子或者蓝色帽子，如果某人看到了谁戴了红色帽子，就举手，如果你是其中一位，看到所有人都举手了（自己也举手说看到了红帽），当过了片刻还没有人说自己头上是什么帽子，要求猜出头上的帽子

这里就要用到归纳法，如果要用到归纳法，一般是首先确定f(n)代表的是什么，然后确定f(n +１)与f(n)的关系,在这里，是一种很特别的归纳法，f(n)并不能直接表示某个具体的解，而是表示一个事实：f(n)表示的是共有n +１个人，其中一个人看到了n顶红帽（自己也举手说看到了红帽），但是大家都不暂时知道自己的帽子，那么他自己戴的肯定是红帽

当有n个人时，一个人看到了其余的全是红帽（自己也举手说看到了红帽），但是过了片刻还没有人说自己头上是什么帽子，这说明自己的问题可以简化为当自己的帽子为蓝色时，求f(n - 1),这样一直就可以简化成f(2)即最开头的那样，这样就得出了解

例2，即有n个人，头上可能会是红色帽子或者蓝色帽子（肯定有一顶是蓝色的），每一轮主持人都会问偷偷问每个人，他知不知道自己头上帽子的颜色，如果有人发现了，则主持人宣布游戏介绍，问如果有m只蓝帽子（m < n）时，这个游戏能进行多少轮？

如果只有一顶蓝帽子，那么第一天就会被人发现，游戏结束
设如果有n顶蓝帽子，那么在第n天会被人发现，游戏结束

这时如果有n+1顶蓝帽子，即当一个人A看到了n顶蓝帽子，过去了n天都没人说自己发现了头顶的颜色，这时A在第n+1天肯定会知道自己头上的颜色，游戏结束

所以最终答案是进行m轮

上面两个题都是以每个人十分聪明和理性，即按照自己设想的来，大家达到一种共识，因为一个人第一题看到有k只蓝帽子，他需要进行判断的是自己也是蓝帽子，如果没有之前的共识，即“如果有n顶蓝帽子，那么在第n天发现”，他是不可能猜到自己的帽子的
，这类问题只有理论价值

操作设计

能量消耗

许多问题是问最少多少次能够完成，这就可以用能量消耗法来考虑，不考虑具体的操作，先确定总任务量为A，每次操作能减少任务量为B，这样A/B就为最少的次数

例1，举办一个淘汰赛，总参加人数为n，为最少多少场比赛能够决出第一名

首先不考虑怎么安排比赛，最后留一个人，总任务量为n - 1，因为每场比赛会淘汰一个人，每次操作能减少任务量为1，这样结果就为 (n - 1)/1 就为最少的次数

例2，考牛排问题，一个烤架只能放n块牛排，现有m块牛排(m > n)，牛排两面都需要烤熟，牛排从生到熟需要k分钟，问所有牛排烤熟至少需要多少分钟

总任务量为 m * 2， 每次减少的任务量为n，所有所需时间为 k * ( (m * 2) / n )(如果不是整除，那么还得加1)
;

例3，有n个医生，m个病人，每个医生都会给每个病人看一种传染病（医生和护士都可能得病），看病的时候手套内侧和医生接触，手套外侧和病人接触，问要使病人之间不传染，医生之间不传染，至少需要多少副手套

这个题如果一个个推的话就很麻烦，其实每个人分配一副手套的一侧，这样需要的手套数就为 （m + n)/ 2

上面三个问题其实都需要一个前提，就是证明 “每次操作能减少任务量B，不多不少，就是B，同样，某次减少任务量后，面对的情况（即问题模型）和减少前是一样的”