为什么最直观的称法 6-6 不是最优的？在 6-6 称的时候，天平平衡的可能性是0，而最优策略应该是让天平每次称量时的概率均等，这样才能三等分答案的所有可能性。
具体怎么实施呢？ 将球编号为1-12，采用 4, 4 称的方法。
我们先将 1 2 3 4 和 5 6 7 8 进行第1次称重。
如果第1次平衡，则坏球肯定在 9-12 号中。则此时只剩下 9-12 4个球，可能性为 9- 10- 11- 12- 9+ 10+ 11+ 12+ 这8种可能。接下来将 9 10 11 和 1 2 3称第2次：如果平衡，则 12 号小球为坏球，将12号小球与1号小球称第3次即可确认轻还是重。如果不平衡，则如果重了说明坏球重了，继续将9和10号球称量，重的为坏球，平衡的话则11为坏球。
如果第1次不平衡，则坏球肯定在 1-8号中。则还剩下的可能性是 1+ 2+ 3+ 4+ 5- 6- 7- 8- 或者 1- 2- 3- 4- 5+ 6+ 7+ 8+，如果是1 2 3 4 这边重，则可以将 1 2 6 和 3 4 5 称，如果平衡，则必然是 7 8 轻了，再称一次7和1，便可以判断7和8哪个是坏球了。如果不平衡，假定是 1 2 6 这边重，则可以判断出 1 2 重了或者 5 轻了，为什么呢？因为如果是3+ 4+ 6-，则 1 2 3 4 比 5 6 7 8 重，但是 1 2 6 应该比 3 4 5 轻。其他情况同理，最多3次即可找出坏球。
下面这个图更加清晰说明了这个原理。
题： 在重男轻女的国家里，男女的比例是多少？在一个重男轻女的国家里，每个家庭都想生男孩，如果他们生的孩子是女孩，就再生一个，直到生下的是男孩为止。这样的国家，男女比例会是多少？
解： 还是1：1。在所有出生的第一个小孩中，男女比例是1：1；在所有出生的第二个小孩中，男女比例是1：1；.... 在所有出生的第n个小孩中，男女比例还是1：1。所以总的男女比例是1：1。
3）约会问题题： 两人相约5点到6点在某地会面，先到者等20分钟后离去，求这两人能够会面的概率。
解： 设两人分别在5点X分和5点Y分到达目的地，则他们能够会面的条件是 |X-Y| <= 20，而整个范围为 S={(x, y): 0 =< x <= 60, 0=< y <= 60}，如果画出坐标轴的话，会面的情况为坐标轴中表示的面积，概率为 (60^2 - 40^2) / 60^2 = 5/9。
4）帽子问题题： 有n位顾客，他们每个人给餐厅的服务生一顶帽子，服务生以随机的顺序归还给顾客，请问拿到自己帽子的顾客的期望数是多少？
解： 使用指示随机变量来求解这个问题会简单些。定义一个随机变量X等于能够拿到自己帽子的顾客数目，我们要计算的是 E[X]。对于 i=1, 2 ... n，定义 Xi =I {顾客i拿到自己的帽子}，则 X=X1+X2+...Xn。由于归还帽子的顺序是随机的，所以每个顾客拿到自己帽子的概率为1/n，即 Pr(Xi=1)=1/n，从而 E(Xi)=1/n，所以E(X)=E(X1 + X2 + ...Xn)= E(X1)+E(X2)+...E(Xn)=n*1/n = 1，即大约有1个顾客可以拿到自己的帽子。
5）生日悖论题： 一个房间至少要有多少人，才能使得有两个人的生日在同一天？
解： 对房间k个人中的每一对(i, j)定义指示器变量 Xij = {i与j生日在同一天} ，则i与j生日相同时，Xij=1，否则 Xij=0。两个人在同一天生日的概率 Pr(Xij=1)=1/n 。则用X表示同一天生日的两人对的数目，则 E(X)=E(∑ki=1∑kj=i+1Xij) = C(k,2)*1/n = k(k-1)/2n，令 k(k-1)/2n >=1，可得到 k>=28，即至少要有 28 个人，才能期望两个人的生日在同一天。
6）概率逆推问题题： 如果在高速公路上30分钟内看到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过的几率是多少？(假设常概率条件下)
解： 假设10分钟内看到一辆车开过的概率是x，那么没有看到车开过的概率就是1-x，30分钟没有看到车开过的概率是 (1-x)^3，也就是 0.05。所以得到方程 (1-x)^3 = 0.05 ，解方程得到 x 大约是 0.63。
数据结构和算法面试题系列—递归算法总结 0.概述