1
在一条长度为 $1$ 的线段上随机取两个点，求以这两个点为端点的线段的期望长度
等等这不就是证明 ODT 的推平操作的长度期望吗
有一个简单粗暴的做法，就是直接用期望的定义，即$E(x)=\sum p(x_i) \cdot x_i$
也就是说（希望没有算错）：
$$
\begin{aligned}
E=&\lim_{n \to +\infty}\sum_{i=0}^{n}\sum_{j=0}^{n}\frac{|\frac{i}{n}-\frac{j}{n}|}{(n+1)^2} \\
=&\lim_{n \to +\infty}\frac{1}{(n+1)^2n}\sum_{i=0}^{n}\sum_{j=0}^{n}|i-j| \\
=&\lim_{n \to +\infty}\frac{1}{(n+1)^2n}\sum_{i=0}^{n}\left(\left(\sum_{j=0}^{i}i-j\right)+\left(\sum_{j=i+1}^{n}j - i\right)\right) \\
=&\lim_{n \to +\infty}\frac{1}{(n+1)^2n}\sum_{i=0}^{n}\left(\left(\sum_{j=0}^{i}j\right)+\left(\sum_{j=1}^{n-i}j\right)\right) \\
=&\lim_{n \to +\infty}\frac{1}{2(n+1)^2n}\sum_{i=0}^{n}\left((1+i)i+(1+n-i)(n-i)\right) \\
=&\lim_{n \to +\infty}\frac{1}{2(n+1)^2n}\sum_{i=0}^{n}\left(i+i^2+n-i+n^2-in-in+i^2\right) \\
=&\lim_{n \to +\infty}\frac{1}{2(n+1)^2n}\sum_{i=0}^{n}\left(2i^2-2in+n+n^2\right) \\
=&\lim_{n \to +\infty}\frac{1}{2(n+1)^2n}\left(2\frac{n(n+1)(2n+1)}{6}-2n\frac{(1+n)n}{2}+(n+n^2)(n+1)\right) \\
=&\lim_{n \to +\infty}\frac{1}{2(n+1)^2n}\left(\frac{n(n+1)(2n+1)}{3}-n^2(1+n)+n^2+n+n^3+n^2\right) \\
=&\lim_{n \to +\infty}\frac{1}{2(n+1)^2n}\left(\frac{n(n+1)(2n+1)}{3}+n^2(2-1-n)+n+n^3\right) \\
=&\lim_{n \to +\infty}\frac{1}{6(n+1)^2n}\left(n(n+1)(2n+1)+6n^2(1-n)+6n+6n^3\right) \\
=&\lim_{n \to +\infty}\frac{1}{6(n+1)^2}\left((n+1)(2n+1)+6n(1-n)+6+6n^2\right) \\
=&\lim_{n \to +\infty}\frac{1}{6(n+1)^2}\left(2n^2+n+2n+1+6n-6n^2+6+6n^2\right) \\
=&\lim_{n \to +\infty}\frac{1}{6(n+1)^2}\left(2n^2+9n+7\right) \\
=&\lim_{n \to +\infty}\frac{1}{6(n+1)^2}\left(2(n+1)^2+9n+5\right) \\
=&\lim_{n \to +\infty}\frac{1}{3}+\frac{9n+5}{12(n+1)^2} \\
=&\frac{1}{3}
\end{aligned}
$$
从积分的角度来看，是这个（实际上是与上式等价的）：
$$
\begin{aligned}
E=&\int_{0}^{1}\int_{0}^{1}|x-y|,dx,dy \\
=&2\int_{0}^{1}\int_{x}^{1}(y-x),dx,dy \\
=&2\int_{0}^{1}\int_{0}^{1-x}y,dx,dy \\
=&2\int_{0}^{1}\frac{1}{2}(1-x)^2,dx,dy \\
=&\int_{0}^{1}(1+x^2-2x),dx,dy \\
=&1+\frac{1}{3}1^3-2\frac{1}{2}1^2 \\
=&\frac{1}{3}
\end{aligned}
$$
顺便一提，从$[0,p]$中随机选取一个点的值的期望是：
$$
\lim_{n \to +\infty}\sum_{i=0}^{n}\frac{ip}{n}\frac{1}{n+1}=\int_{0}^{p}x,\frac{dx}{p}=\frac{p}{2}
$$
因此期望最大值不会超过$\frac{1}{2}$，因为第一个选择之后，第二个点的期望值是$\frac{1}{2}$（可能这句话会有一些偏差，忽略掉）
一般的，从$[a,b]$中随机选取一个点的值的期望为：
$$
\lim_{n \to +\infty}\sum_{i=0}^{n}\left(a+\frac{i(b-a)}{n}\right)\frac{1}{n+1}=\int_{a}^{b}x,\frac{dx}{b-a}=\frac{a+b}{2}
$$
2
假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一
有足够多的人每人都用这台抽奖机抽奖
假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止
最后每个人都把自己获得的所有球放到一个大箱子里
求最终大箱子里的红球与蓝球的比例期望
在发现更大的世界的时候 你可能会听说这么一句话：“男女比例失调与重男轻女无关”
虽然这句话是错的 这句话的意思是想表达这么一件事：如果生了女儿就接着生，直到生到儿子就停止
这么做下去后男女比例依然是$1:1$
那么回到这道题，依然是考虑期望的定义
可以发现：
$$
\begin{aligned}
E=&\sum_{k=0}^{\infty}\left( \frac{1}{2} \right)^{k+1}\frac{k}{1}\\
=&\frac{1}{2}\sum_{k=0}^{\infty}\left( \frac{1}{2} \right)^{k}k \\
=&\frac{1}{2}T
\end{aligned}
$$
$$
\begin{aligned}
\because,& T=\sum_{k=0}^{\infty}\left( \frac{1}{2} \right)^{k}k \\
\therefore,&\frac{1}{2}T=\sum_{k=0}^{\infty}\frac{k}{2^{k+1}}=\sum_{k=1}^{\infty}\frac{k-1}{2^k} \\
\therefore,&\frac{1}{2}T=\frac{1}{2^0}\sum_{k=1}^{\infty}\frac{1}{2^k}=1
\end{aligned}
$$
所以，$E=1$
3
甲乙丙丁四人在考虑周末要不要外出郊游
已知：
- 如果周末下雨，并且乙不去，则甲一定不去
- 如果乙去，则丁一定去
- 如果丙去，则丁一定不去
- 如果丁不去，而且甲不去，则丙一定不去
如果周末丙去了，则：
- 甲（去了/没去）
- 乙（去了/没去）
- 丁（去了/没去）
- 周末（下雨/没下雨）
约束都列出来然后推推不就行了么
$$
\begin{aligned}
\left.\begin{aligned}\text{下雨} \\ \text{乙不去}\end{aligned}\right\} \to& \text{甲不去} \\
\text{乙去} \to& \text{丁去} \\
\text{丙去} \to& \text{丁不去} \\
\left.\begin{aligned}\text{丁不去} \\ \text{甲不去}\end{aligned}\right\} \to& \text{丙不去} \\
\end{aligned}
$$
由于丙去了，所以丁不去（条件三）
由于丁没去，所以乙也没去（条件二）
由于丙去了，且丁没去，所以甲去了（条件四）
由于甲去了，且乙没去，所以没下雨（条件一）
4
方程 $a \times b = (a \mathop{or} b) \times (a \mathop{and} b)$，在 $a,b$ 都取 $[0, 31]$ 中的整数时
求共有多少组解？
（$\times$ 表示乘法；$\mathop{or}$ 表示按位或运算；$\mathop{and}$ 表示按位与运算）
设$x=a \mathop{and} b,y=x \mathop{xor} a, z = x \mathop{xor} b$
则此时$x$是$a$和$b$共有的位构成的数，$y$是$a$去掉共有的位后的数，$z$是$b$去掉共有的位之后的数
则有$ab=(x+y)(x+z)$，且$(a \mathop{or} b)(a \mathop{and} b)=(x+y+z)x$
也就是说，$(x+y)(x+z)=x(x+y+z)$
化简得$yz=0$，即要么$y=0$，要么$z=0$，也就是说这个等式成立，当且仅当$a,b$中的某一个数是另一个数的二进制下的子集时才成立
因此解的个数就是：
$$
\left(\sum_{i=0}^{31}2^{\mathop{popcount}(i)}\right)-32=454
$$
当然可以这么算（十分简单）：
$$
\begin{aligned}
2\left(\sum_{i=0}^{5} {5 \choose i}2^i\right)-32=2 \times 3^5-32=454
\end{aligned}
$$
