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

甲乙丙丁四人在考虑周末要不要外出郊游

已知:

  1. 如果周末下雨,并且乙不去,则甲一定不去
  2. 如果乙去,则丁一定去
  3. 如果丙去,则丁一定不去
  4. 如果丁不去,而且甲不去,则丙一定不去

如果周末丙去了,则:

  1. 甲(去了/没去)
  2. 乙(去了/没去)
  3. 丁(去了/没去)
  4. 周末(下雨/没下雨)

约束都列出来然后推推不就行了么
$$
\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}
$$