硬币问题

两个人轮流抛硬币，谁先抛到正面就赢。求第一个抛硬币的人获胜的概率？

答案

第一个人1次获胜概率：$\frac{1}{2}$
3次获胜概率: ${\frac{1}{2}}^3$
5次获胜概率: ${\frac{1}{2}}^5$
…
n次获胜概率: ${\frac{1}{2}}^n$

第一个人获胜总概率P=$\frac{1}{2}+{\frac{1}{2}}^3+…+{\frac{1}{2}}^n$
使用等比数列求和公式，当$n\to+\infty$时，$P=\frac{2}{3}$

抛硬币

抛硬币，平均需要多少次才能连续出现三次正面？

答案

设$E_t$表示已经连续抛出了$t$次正面，期望还需要多少次才能连续出现三次正面。
$E_0=1+\frac{1}{2}E_0+\frac{1}{2}E_1$
$E_1=1+\frac{1}{2}E_0+\frac{1}{2}E_2$
$E_2=1+\frac{1}{2}E_0$
解得：$E_0=14$

投骰子1

投骰子，连续两次6则结束，平均几次结束？

答案

设$E_t$表示已经连续抛出了$t$次6，期望还需要多少次才能结束。
$E_0=1+\frac{5}{6}E_0+\frac{1}{6}E_1$
$E_1=1+\frac{5}{6}E_0$
解得：$E_0=42$

投骰子2

投骰子，每个点数都出现1次就结束，求期望次数。

答案

设$E_t$表示已经出现了t种点数，期望还需要多少次才能结束。
$E_t=\frac{t}{6}(1+E_t)+\frac{6-t}{6}(1+E_{t+1})$
$E_6=0$
$E_0=14.7$

生育

生育规则是，如果生女孩就继续生，直到生出男孩。问最终男女比例？

答案

最终每个家庭至少有一个男孩。
此时每个家庭女孩的期望个数,可以用尾和公式计算。
$$
\begin{aligned}
E&=P(x\geq1)+P(x\geq2)+… \
&=\frac{1}{2}+(\frac{1}{2})^2+… \
&=1 \
\end{aligned}
$$
所以每个家庭期望一个男孩，一个女孩，男女比例为$1:1$。

投不均匀硬币

一枚硬币，正面概率为0.7，反面概率0.3，问怎么高效获得一个0.5的事件。

答案

抛两次，如果两次都是一样的面，重抛。这时“正反“和“反正“出现概率各为0.5.

扑克

一份扑克牌54张，平均分成两份，求这两份都有两张A的概率。

答案

$P=\frac{ {4 \choose 2}{50 \choose 25} }{54 \choose 27}=\frac{351}{901}$

生日

50个人的班级，至少有两人同一天生日的概率是多少。

答案

$P=1-\frac{365}{365}\times\frac{364}{365}\times\frac{363}{365}…\approx97.04\%$

球

红球50个，蓝球50个，放在两个盒子里面，随机重盒子里面拿出一个球，问怎么分配，拿到红球的概率最高？

答案

一个盒子里面放1个红球，另外一个盒子里放49个红球和50个蓝球。

天平称重

有8个球，其中有1个球偏重。使用一个天平，至少需要多少次才能找到这个偏重的球？

答案

两次。方案如下：
将小球分为3组，每组分别有3、3、2个球。天平左右先放1、2两组，如果相等，说明重的球在第三组里，只需要多一次就可以找到。否则，3个球里面随机取两个，如果不想等，重的球就找到了。如果相等，剩下那个球是重的。

量水问题

有一个5L的瓶子和一个4L的瓶子，如何量出3L的水？

答案

我们设5L的是1号瓶子，4L的是2号瓶子。先倒满1号瓶子，用1号瓶子倒满2号瓶子，倒掉2号瓶子，再把1号瓶子的倒到2号瓶子，此时2号瓶子里面有1L水。再次倒满1号瓶子，用1号瓶子倒满2号瓶子，倒掉2号瓶子，再把1号瓶子的倒到2号瓶子，此时2号瓶子里面有2L水。再倒满1号瓶子，用1号瓶子倒满2号瓶子，此时1号瓶子里有3L水。

步骤 操作 5L 瓶 4L 瓶
1 装满 5L 5 0
2 5L → 4L（倒满 4L） 1 4
3 倒空 4L 1 0
4 4L 中的 1L → 4L 0 1
5 装满 5L 5 1
6 5L → 4L（4L 还能装 3L） 2 4
7 倒空 4L 2 0
8 4L 中的 2L → 4L 0 2
9 装满 5L 5 2
10 5L → 4L（4L 还能装 2L） 3 4

赛马问题

有25匹马，有5个赛道，问至少需要几场比赛，才能得到top3

答案

7场。首先分成五组，每组各自比。接下来，每组的冠军（一共5个）比一场，根据这个对组排序，倒数两名的组已经可以全部淘汰，剩下的组各有5匹马。第一组的冠军已经可以确定是全场冠军，剩下的只有第二名第三名才有可能是top3，第二组只有前两名才有可能是top3，第三组只有冠军才有可能是top3。可能是top3的一共5匹马，他们之间比一场，就可以知道第二名和第三名。

钝角三角形概率

圆周上随机取三个点，问这三个点构成的三角形是钝角三角形的概率。

答案

本质上是算三点都在同一个半圆的概率。
所有情况都可以规约到第一点在 $0^\circ$，第二点在 $x \in [0, \pi]$。
第三个点合法的区间是$[0,\pi]\cup[\pi+x,2\pi]$
最终概率
$$
\begin{aligned}
P&= \frac{1}{\pi} \int_0^\pi \frac{2\pi - x}{2\pi},dx \
&= \frac{1}{\pi} \left[x-\frac{x^2}{4\pi} \right]_0^\pi \
&= \frac34
\end{aligned}
$$

老虎吃羊

岛上有100只老虎和1只羊，老虎可以吃草但是更愿意吃羊。每次老虎吃完羊之后自己就变成了羊，所有老虎都很聪明而且很理性，他们都想活下去。请问这只羊会被吃吗？

答案

首先考虑1只老虎的情况，羊肯定会被吃。
2只老虎，一旦一只老虎吃了羊，就会被另外一只老虎吃，所以羊不会被吃。
3只老虎，一旦一只吃了羊，就变成了两只老虎一只羊的局面，不会被吃，所以这时候羊会被吃。
4只老虎，一只老虎吃了之后，变成3只老虎一只羊的局面，会被吃，所以这时候羊不会被吃。
…
可以一路递推，100只老虎的时候羊不会被吃。

毒酒问题

有1000瓶毒酒，其中一杯有毒，喝了之后第二天会发作。有10只老鼠，每只老鼠可以喝多杯酒，一杯酒也可以被多只老鼠喝。问如何分配，能在第二天知道哪瓶酒有毒？

答案

酒的编号，转换成二进制，正好是10位。第一只老鼠喝第一位bit为1的酒，第二只老鼠喝第二位bit为1的酒…这样就可以知道毒酒哪位是1，也就可以还原出毒酒编号了。

取书游戏

桌上有100本书，两个人可以轮流取，每人每次可以取1/2/3本，取到最后一本的人获胜。两人都足够聪明，问是否有先手必胜的策略？

答案

计算每种状态SG值。
SG(0)=0,SG(1)=1,SG(2)=2,SG(3)=3,
SG(4)=0,SG(5)=1,SG(6)=2,SG(7)=3,
…
SG(100)=0
所以先手必败。