1 生日悖论
一个房间的人数必须要达到多少，才能使得有两个人生日相同的机会达到50%？
1）用概率来分析
假设一年 n = 365天，
两个人的生日都落在某一个固定的天数r上的概率为 1/n * 1/n = 1 / n^2
两个人的生日落在同一天上的概率为n * 1 / n^2 = 1 / n
注意两个人的生日落在同一天的概率 = 某个人的生日落在指定一天的概率 = 1 / n 这个巧合依赖于个各人生日独立。
k个人中至少有2人生日相同的概率等于1减去所有人生日都不互不相同的概率。即：
1 - 1 * (n-1)/n * (n-2)/n......* (n-k+1)/n >= 1/2
=> (n-1)/n * (n-2)/n......* (n-k+1)/n <= 1/2
由不等式：1+x <= e^x
=> e^{-1/n -2/n ... -(k-1)/n} = e^{ -k*(k-1) / 2n} <= 1/2
=> k * (k-1) >= 2n*ln2
可以解除k为23时，至少有2个人生日相同的概率在50%以上。
2）用指示器随机变量来计算 期望至少有2个人的生日相同 时需要的人数。
用X表示具有相同生日的对数（一对是2个人），
那么一共是C(k,2)对人，每一对人生日相同的概率都是1/n
所以当有k个人时，生日相同的人的对数的期望是 C(k,2) * 1/n = k(k-1) / 2n
k(k-1) / 2n >= 1 即可求出k=28人时，可以期望有一对人的生日相同。
注意1）和2）的描述不同，是2个不同的问题。
---------------------------------------------------------------------------------------------------------------------------------------------------
2 球与盒子（赠券收集者问题）
一个人如果想要收集齐b种不同赠券中的每一种，大约需要b*lnb张随机得到的赠券才能完成。
用球和盒子的模型说明：把相同的球随机投到b个盒子中去。
1>有多少个求落入指定的盒子中？服从二态分布(k；n，1/b)，则期望值为n/b
2>在给定的盒子中至少一个球之前，平均需要投多少个球？服从几何分布，概率为1/b，成功前的期望个数为1/(1/b)=b
3>在每个盒子至少有一个球之前，要投多少个球？
大约投球b*lnb次就可以满足条件
证明见书
-------------------------------------------------------------------------------------------------------------------------------------------------
3 序列（抛掷n次硬币连续正面次数的期望）
在CSDN的算法版上有这样一个讨论：
adrew教授招了一个研究生，给他布置了一个任务，让他拿着硬币抛100次，如果是正面则在纸上写1，若是反面则在纸上写0，最后把这个序列给adrew教授。这个学生半个小时后回来，给出了下面的数据，Adrew教授立刻就识破了这个学生是随便写的数据，并没有确实去做这个实
验，你能猜出为什么吗？
数据
1 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1
1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 1
0 0 1 1 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 1
1 0 1 1
设想你抛一枚硬币n次，你期望看到的连续正面的最长序列是多长？答案是O(lgn)
证明见书
--------------------------------------------------------------------------------------------------------------------------------------------------
4 在线雇佣问题（苏格拉底的捡麦穗问题）
对雇佣问题进行修改，现在我们只雇佣一次：
选择一个正整数k < n,面试前k个应聘者然后拒绝他们，再雇佣其后第一个比前面所有应聘者分数都高的人，如果没有这个人，就雇佣最后一个人。
ON-LINE-MAXIMUM(k, n) 1 bestscore ← -∞ 2 for i ← to k 3 do if score(i) > bestscore 4 then bestscore ← score(i) 5 for i ← k + 1 to n 6 do if score(i) > bestscore 7 then return i 8 return n
怎么才可以捡到期望的最大麦穗呢？
方法是在前k次中不捡麦穗，但是比较找出最大麦穗并记住，在后面的n-k个麦穗中第一次遇到比前k个中的最大的还要大的麦穗就捡起，就是目标麦穗。如果没有发现比前k个还要大的，就捡最后一个第n个。
这里的关键是取好k的值，使得能够捡到最大的麦穗的可能性最大，根据算法导论（中文版）第67和68页分析，这个k值取n/e时，则可以至少有1/e的概率渠道最大的麦穗。k=n/e
---------------------------------------------------------------------------------------------------------------------------------------------------
总结：
了解这些问题。证明见书
前5章是算法导论的第一部分--基础知识
其中第5章不乏许多有意思的问题