不败的石头 坚硬的博客

有n个人，其中超过半数是好人，剩下的是坏人
好人只说真话，坏人可能说真话也可能说假话
这n个人互相都知道对方是好人还是坏人

现在要你从这n个人当中找出一个好人来，只能通过以下方式：
每次挑出两个人，让这两个人互相说出对方的身份，
你根具两个人的话进行判断。

问通过何种方法才能最快的找出所有人的身份(最坏的情况下)

解法：

首先分析只有两个人的情况：a和b

1、a说b是好人，b说a是好人：则a和b是同样的人，同为好人或者同为坏人

2、a说b是好人，b说a是坏人：则a肯定是坏人，b不确定

3、a说b是坏人，b说a是好人：要么a好b坏，要么a坏b坏，则b肯定是坏的

4、a说b是坏人，b说a是坏人：要么a好b坏，要么a坏b好，要么a坏b坏。

那么现在就顺序的从n人中抽出一个人i来，和剩下的人来依次比较。

假设挑出来的坏人，那么最坏的情况前面n/2个都相互说是坏人，这样就无法判断了？

如果符合1的情况超过1/2，则i是好人

如果符合2，则i是坏人，去掉i，再取一个i

如果符合3，则把集合中的对应的人去掉，继续下一个

如果符合4的情况超过1/2，则i是坏人，去掉i，再取一个i

反复如此，可以找到所有人的身份。

• 无穷多素数证明

假定有有限多个素数，A1…An，现在制造一个素数等于A1*A2*…An+1，这个数肯定是一个素数因为他被任意的素数整除都余一。因此有无穷多个素数。

• 素数中间可以相隔无穷大

可以创造一系列的合数，可以是任意的数目，中间不含有任何的素数。例如取1000的阶乘1000！，然后制造一系列的数1000！+2……1000!+1000，这999个数全部是和数。还可以制造任意大小的数N，N!+2……N!+N，这一系列数也都是和数。

• 柯尼斯堡七桥问题

通过某一点的路线如果是偶数个，则从这个点出和入可以不重复地行走，如果是奇数个，则只能是起点或者终点。

• 拉姆赛定理

六 个人被邀请参加晚会总会有三个人认识或者三个人不认识，如果是四个人认识或者不认识，则需要至少18个人与会。换句话说，只要有足够的人参加，总会找到N 个人认识或者不认识的规律。更深一步说，只是事物足够复杂就一定会有某种规律存在，完全没有规律的事物是不存在的。例如在圣经中找到某种预言（或者其他的 比较大部头的作品），生命的产生，火星上的人脸。这些惊人的巧合都是对大量随机数据进行大量试验的必然结果。（参见我的大脑打开了P71）

• 正方形的分割

一个正方形分割成多个正方形的最小个数是21个，边长为112

• 猜奖概率

有 三扇门，其中一扇门的后面是黄金，另外两扇门后面是山羊。参与者从三扇门中任选一扇门。在参与者选完一扇门后，主持人会打开一座后面有山羊的门（不管参与 者选择得如何，都会有一座门后有山羊），这个时候参与者可以选择坚持自己的方案，也可以改变到另一扇门。换与不换的概率是不同的，我们从出错概率着手：
不换的出错概率是：2/3
换的出错概率是：2/3*1/2 = 1/3
因此应该换。

• 实数集合比自然数集合大（康托尔证明法）

假定在0到1之间的实数和所有的自然数一一对应，
1 - 0.13493358
2 - 0.85195719
3 - 0.14159265
4 - 0.17283845
5 - 0.04146492
6 - 0.71582381
…………………
现 在取第一个数的第一位小数，第二个数的第二位小数，以此类推，换言之用表中的对角线构造一个新数，然后把这个数的每一位小数都换成另一个数，无论怎么换都 可以只要和原数不同就行（不要换成9或者0避免0.24999=0.25000这种情况出现）。这个变化后的新数与上面的任意个数都不相同，因为在对应的 N（N=1到无穷）位上与原数都不相同。

• 生日悖论

• 贝切特称重

• π的无穷级数表示

• 网络的欧拉公式

• 找到不变量

• 三人决斗问题

• 删除重复组合的问题

1. 1×6×6＝36，表示从第一组中拿出一个1，然后从另两组中任选


2. 5×1×6＝30，表示从第二组中拿出一个1，从第一组中取除了1以外的另五个数，然后从第三组中任取6个


3.  

1. 5×5×1＝25，表示从第三组中拿出一个1，从第一组中取除了1以外的另五个数，从第一组中取除了1以外的另五个数。