@1 强迫症的投掷器 20240420
$n$ 个东西，每次等概率随机一个东西摸一下。问期望几次能摸过所有 $n$ 个东西。
显然第一次一定会摸到一个新东西。考虑期望多少次操作能拿到第二种新东西。显然有 $\frac{n - 1}n$ 的概率摸到新东西，于是期望次数就是 $\frac n{n - 1}$ 次。再摸到第三个东西的期望次数就是 $\frac n{n - 2}$ 次。
于是总答案就是
$$\sum\limits_{0 \leq i < n} \frac n{n - i} = nH_n$$
Bonus：如果以指定的不同的概率随机摸，问摸到 $k$ 种不同东西的期望次数。
@2 独立集大小下界 20240424
任意一个 $n$ 个点，$m$ 条边的图 $G\left(V, E\right)$，给出一个下界 $L$，使得存在一个独立集，它的大小至少是 $L$。
随机独立集期望大小显然是下界。我们用这种方法来算下界。
算法 1
考虑一个独立集的生成方式：
每个点以固定的 $p$ 的概率，加入到当前集 $S$ 中。
对于每条边，如果它的两个顶点都在当前集 $S$ 中，则随便删一个点。
考虑计算它的期望大小 $E\left[\lvert S \rvert\right]$，则对于任意一个 $n$ 个点，$m$ 条边的图，一定存在一个独立集，它的大小不小于 $E\left[\lvert S \rvert\right]$。
在第一步中，当前集 $S$ 的大小期望是 $np$。
在第二步中，我们期望会删掉 $mp^2$ 个点（考虑一条边，它的两个顶点都被选中的概率是 $p^2$，一共是 $m$ 条边，所以是 $mp^2$）。
因此最终独立集的期望大小是 $np - mp^2$，取 $p = \frac n{2m}$，得到 $\frac{n^2}{4m}$。
算法 2
考虑另一个独立集的生成方式：
对于每个点随机生成一个在 $0$ 到 $1$ 之间的实数，称为它的权。
如果一个点的权比它的所有邻居都大，那么把它加入当前集 $S$ 中。
容易发现，$S$ 是独立集。
考虑计算它的期望大小 $E\left[\lvert S \rvert\right]$。
设 $d_v$ 为点 $v$ 的度数。
$$E\left[\lvert S \rvert\right] = \sum\limits_{v \in V}\frac1{d_v + 1}$$
当所有 $d_i$ 全部相等时，会取到最小值 $\frac{n^2}{2m + n}$。
考虑将一个点的度数 $d_a$ 减一，并将另一个点的度数 $d_b$ 加一，总度数不变，但 $\frac1{d_a + 1} + \frac1{d_b + 1} < \frac1{d_a} + \frac1{d_b + 2}$，因此当所有 $d_i$ 全部相等时，会取到最小值。
这次得到的界 $\frac{n^2}{2m + n}$ 比上次的 $\frac{n^2}{4m}$ 更优，原因就在于这次的独立集生成方式比上次的优。
@3 组合数不互质 20240608
求证，对于 $1 \leq a, b < n$，有 $\gcd\left(\binom na, \binom nb\right) \neq 1$。
不妨假设 $b \geq a$
$$ \begin{aligned} \gcd\left(\binom na, \binom nb\right) &= \gcd\left(\frac{n!}{\left(n - a\right)!a!}, \frac{n!}{\left(n - b\right)!b!}\right) \\ &= \gcd\left(\frac{n!}{\left(n - a\right)!} \cdot \frac{b!}{a!}, \frac{n!}{\left(n - b\right)!}\right) / b! \end{aligned} $$
当 $a = 1$ 时：
$$ \begin{aligned} \gcd\left(n, \binom nx\right) \neq 1\\ \gcd\left(n, \frac{n!}{x!\left(n - x\right)!}\right) \neq 1\\ \end{aligned} $$
考虑 $n$ 的每个质因子 $p$ 在 $n!$ 和 $x!$ 和 $\left(n - x\right)!$ 中的出现次数：
$$\sum\limits_{i \geq 1}\left\lfloor\frac n{p^i}\right\rfloor \geq \sum\limits_{i \geq 1}\left\lfloor\frac {n - x}{p^i}\right\rfloor + \sum\limits_{i \geq 1}\left\lfloor\frac x{p^i}\right\rfloor$$
但如果对于所有的 $p$，都有
$$\sum\limits_{i \geq 1}\left\lfloor\frac n{p^i}\right\rfloor = \sum\limits_{i \geq 1}\left\lfloor\frac {n - x}{p^i}\right\rfloor + \sum\limits_{i \geq 1}\left\lfloor\frac x{p^i}\right\rfloor$$
，那最终的 $\gcd$ 还是 $1$，但是我们发现，如果对于一个 $p$，
$$\sum\limits_{i \geq 1}\left\lfloor\frac n{p^i}\right\rfloor = \sum\limits_{i \geq 1}\left\lfloor\frac {n - x}{p^i}\right\rfloor + \sum\limits_{i \geq 1}\left\lfloor\frac x{p^i}\right\rfloor$$
成立，那么 $x$ 必定为 $p$ 的整数次幂。而 $p$ 是质数，因此 $x$ 只能对最多一个 $p$ 取等。因此对于质因数个数大于等于 $2$ 的 $n$，都有
$$\gcd\left(n, \binom nx\right) \neq 1$$
而对于只有一个质因数的 $n$，即 $n = p^k$，显然在 $i = k$ 时，
$$\left\lfloor\frac n{p^k}\right\rfloor = 1$$
而
$$\left\lfloor\frac {n - x}{p^k}\right\rfloor + \left\lfloor\frac x{p^k}\right\rfloor = 0$$
因此也满足要求。
接下来，我们关注 $a$ 增加 $1$ 时的情况。
逗号左边会乘上 $\frac{n - a}{a + 1}$，如果这时我们假设 $a \leq \frac n2$，且 $b \geq \frac n2$（注意这样满足我们之前假设的 $b \geq a$），那么 $n - a$ 就会出现在右边的 $\frac{n!}{\left(n - b\right)!}$ 中，从而产生贡献。而我们需要让损失 $a + 1$ 不超过贡献 $n - a$，如果 $a < \frac n2$，就会满足条件，在 $a = \frac n2$ 时，$\frac{n - a}{a + 1} = \frac n{n + 2}$，而 $\frac{n - \left(a - 1\right)}{\left(a - 1\right) + 1} = \frac{n + 2}n$，仅仅只是把上次的增加消去了。
@4 随机数最大值 20240707
$n$ 个 $\left[1, m\right]$ 的整数随机变量 $x_1, \ldots, x_n$，求期望最大值。
设 $M = \max\limits_{i = 1}^nx_i$。
$$ \begin{aligned} E\left(M\right) &= \sum\limits_{i = 1}^mP\left(M = i\right)i \\ &= \sum\limits_{i = 1}^m \left(P\left(M \leq i\right) - P\left(M \leq i - 1\right)\right)i \end{aligned} $$
我们发现，$M \leq i$ 等价于所有 $x_i$ 都小于等于 $i$，于是 $P\left(M \leq i\right) = \left(\frac im\right)^n$。
$$ \begin{aligned} E\left(M\right) &= \sum\limits_{i = 1}^m \left(P\left(M \leq i\right) - P\left(M \leq i - 1\right)\right)i \\ &= \sum\limits_{i = 1}^m \left(\left(\frac im\right)^n - \left(\frac{i - 1}m\right)^n\right)i \\ &= m - \frac{H_{m - 1}^{\left(-n\right)}}{m^n} \end{aligned} $$
其中 $H_n^{\left(r\right)}$ 为广义调和数（Generalized Harmonic Numbers）。
@5 不等随机变量期望和 20240707
$m$ 个 $\left[1, n\right]$ 的整数随机变量 $x_1, \ldots, x_n$，互不相等，求期望和。
我们可以看值为 $i$ 的变量的贡献 $x_i$。
$$x_i = [\text{i is chosen}]i$$
设 $S = \sum\limits_{i = 1}^nx_i$。由于期望具有线性性，于是
$$ \begin{aligned} E\left(S\right) &= \sum\limits_{i = 1}^n E\left(x_i\right) \\ &= \sum\limits_{i = 1}^n\sum\limits_jP\left(x_i = j\right)j \\ &= \sum\limits_{i = 1}^nP\left(x_i = i\right)i \\ &= \sum\limits_{i = 1}^n\frac mni \\ &= \frac{\left(n + 1\right)m}2 \end{aligned} $$
有趣的是，如果这些变量允许相同，这个期望和也是 $\frac{\left(n + 1\right)m}2$。
@6 随机变量不同个数 20240708
$n$ 个 $\left[1, n\right]$ 的整数随机变量 $x_1, \ldots, x_n$，求期望不同的变量个数。
$i$ 被选过的概率是 $1 - \left(\frac{n - 1}n\right)^n$，乘以 $n$ 之后是 $n - n\left(\frac{n - 1}n\right)^n$，洛朗（Laurent）展开后是
$$n\left(1 - \frac1e\right) + \frac1{2e} + \mathcal O\left(\frac1n\right)$$
@7 横跳游戏 20240708
初始 $X = N$，不断等概率将 $X$ 增加 $1$ 或减少 $1$，直到 $X = 0$ 或 $X = M$。问最终 $X = M$ 的概率。
$0 < N < M$
设 $P_t\left(x\right)$ 表示 $t$ 次操作后 $X = x$ 的概率。
根据定义有 $P_0\left(x\right) = \left[x = N\right]$。我们先不妨令 $P_t\left(0\right) = P_t\left(N\right) = 0$。
若 $0 < x < N$，根据题意有
$$P_t\left(x\right) = \frac{P_{t - 1}\left(x - 1\right) + P_{t - 1}\left(x + 1\right)}2$$
和
$$P_t\left(1\right) = \frac{P_{t - 1}\left(2\right)}2$$
与
$$P_t\left(M - 1\right) = \frac{P_{t - 1}\left(M - 2\right)}2$$
证明 $t$ 趋近于正无穷大时 $P_t\left(x\right) = 0$ 容易。
考虑计算答案
$$\Pr = \sum\limits_{t = 0}^{\infty}\frac12P_t\left(M - 1\right)$$
设 $F\left(x\right) = \sum\limits_{i = 0}^{\infty}\frac12P_t\left(x\right)$
$$ \begin{aligned} F\left(x - 1\right) + F\left(x + 1\right) &= \sum\limits_{t = 0}^{\infty}\frac{P_t\left(x - 1\right) + P_t\left(x + 1\right)}2\\ &= \sum\limits_{t = 0}^{\infty}P_{t + 1}\left(x\right)\\ &= \sum\limits_{t = 1}^{\infty}P_t\left(x\right)\\ &= 2F\left(x\right) - P_0\left(x\right) \end{aligned} $$
所以，当 $0 < x < M$ 且 $x \neq N$ 时，有 $F\left(x\right) - F\left(x - 1\right) = F\left(x + 1\right) - F\left(x\right)$。
于是有 $F\left(N\right) = NF\left(1\right)$ 和 $F\left(N\right) = \left(M - N\right)F\left(M - 1\right)$，又因为 $F\left(1\right) + F\left(M - 1\right) = 1$，所以 $F\left(M - 1\right) = \frac NM$。
@8 抛硬币 20240716
期望抛多少次硬币，才能出现连续两次正面朝上的情况？
看似很简单，其实需要分析一下的。
假设我们不一开始就抛出两次正面，那么结尾的三次必然是 反，正，正。
我们可以考虑用 $k$ 次都凑不出来的方案数。
设 $f_{i, j = 0 / 1}$ 表示正在抛第 $i$ 次，这次抛的结果是 $j$ 的方案数，注意不能出现连续两次正面的情况。显然有转移方程：
$$f_{i, 0} = f_{i - 1, 0} + f_{i - 1, 1}$$
和
$$f_{i, 1} = f_{i - 1, 0}$$
我们设 $g_i$ 表示抛 $i$ 次都凑不出来的方案数，显然有 $g_i = f_{i, 0} + f_{i, 1}$。于是我们可以弄出 $g_i$ 的转移方程：
$$g_i = g_{i - 1} + g_{i - 2}$$
初始状态为 $g_1 = 2$ 和 $g_2 = 3$。
考虑原问题，根据题意
$$Ans = \sum\limits_{k \geq 2}k\frac{g_{k - 3}}{2^k}$$
然后就是生成函数求解级数了，答案是 $6$。
@9 重要性排名（PageRank）20240716
定义图上一个状态的重要性如下
$$r\left(x\right) = \sum\limits_{y \to x}\frac{r\left(y\right)}{d_{out\left(y\right)}}$$
其中 $d_{out}\left(x\right)$ 表示 $x$ 的出度。
这么看上去，好像我们用这个等式只能验证某个图是否平衡。但我们其实可以通过一些方式算出一个平衡的 $r$。
我们随机从一个点开始随机游走，等概率在所有出边中等概率随机一条走，走到点 $x$ 的概率，就是 $r\left(x\right)$。
这个概率就是马尔可夫（Markov）链达到稳态分布（Stationary Distribution）是的转移矩阵。
但是这个马尔可夫链很可能是可约（Reducible）或者周期性（Periodic）的。于是我们需要先对这个马尔可夫链进行扰动。
如果该矩阵可约，我们完全可以把他拆成不同的连通块，根据大小附加权重。
如果具有周期性，我们可以添加自环，在答案不变的情况下消去周期性。
@10 $4k + 3$ 型质数有无穷个 20240720
证明 $4k + 3$ 型质数有无穷个，其中 $k \in \mathbb N$。
若没有无穷个，我们设 $4k + 3$ 型质数有 $n$ 个，从小到大是 $p_1, \ldots, p_n$。
令 $m = 4p_1p_2\cdots p_n - 1$。显然 $m$ 是奇数，所有因子都必然可以被表示为 $4k + 1$ 或 $4k + 3$ 的形式。
我们先来分析一下，假设有两个 $4k + 1$ 型数，记为 $4p + 1$ 和 $4q + 1$，则他们的乘积
$$\left(4p + 1\right)\left(4q + 1\right) = 4\left(4pq + p + q\right) + 1$$
也是 $4k + 1$ 型数。但 $m$ 是 $4k + 3$ 型数，说明不可能全部由 $4k + 1$ 型数相乘得到，于是 $m$ 中一定包含一个 $4k + 3$ 型数，记为 $a$。一个 $4k + 3$ 型合数一定可以被表示为一个 $4k + 1$ 型数和一个更小的 $4k + 3$ 型数的积。因此，我们可以一直拆 $a$，直到拆成 $4k + 3$ 型质数，记为 $b$。
至此，我们得到两个性质：$b \mid m$ 和 $b \mid p_1 p_2 \cdots p_n$，于是有
$$b \mid \left(4p_1 p_2 \cdots p_n - m\right)$$
注意到 $4p_1 p_2 \cdots p_n - m = 1$，于是 $b \mid 1$，所以 $b$ 不是质数。导出了矛盾，因此假设不成立。
所以 $4k + 3$ 型质数有无穷多个。
@11 Wilson 定理证明 20240720
证明：如果 $p$ 是质数，则有 $\left(p - 1\right)! \equiv -1 \pmod p$。
我们要证明，在 $\mathbb Z_p^*$ 中所有元素的乘积为 $-1$。
若 $a \in \mathbb Z_p^*$，则 $a^{-1} \in \mathbb Z_p^*$。
而 $aa^{-1} \equiv 1 \pmod p$，于是我们可以配对消去。
但是注意到有些时候 $a = a^{-1}$。这时我们有 $a^2 \equiv 1 \pmod p$，于是有 $a \equiv \pm1 \pmod p$。
因此对于其他的 $a$，我们不用管他们，因为他们的乘积就是 $1$。
所以 $\left(p - 1\right)! \equiv 1 \cdot \left(p - 1\right) \equiv -1 \pmod p$。
@12 这界有点松 20240721
来自 https://www.luogu.com/paste/nnhhar1a
这条中的变量 $p$ 一定是质数。
证明：对于任意 $n \geq 2$，都有
$$\prod\limits_{p \leq n} p < 4^{n - 1}$$
设 $q$ 是不超过 $n$ 的最大质数，我们只需证 $\prod\limits_{p \leq q}p<4^{q - 1}$。$q = 2$ 时显然成立。以下归纳证明。设 $q = 2r + 1$，我们假设 $\prod\limits_{p \leq r + 1}p < 4^r$ 成立。
$$\prod\limits_{p \leq 2r + 1}p = \left(\prod\limits_{p \leq r + 1}p\right)\left(\prod\limits_{r + 1 < p \leq 2r + 1}\right)$$
由于 $r + 2$ 到 $2r + 1$ 中有 $r$ 个偶数，我们不需要统计，于是：
$$\left(\prod\limits_{p \leq r + 1}p\right)\left(\prod\limits_{r + 1 < p \leq 2r + 1}\right) < 4^r\frac{\left(2r + 1\right)!}{\left(r + 1\right)!r!} = 4^r\binom{2r + 1}r$$
根据二项式定理，$\binom{2r + 1}r$ 在 $\left(1 + 1\right)^{2r + 1}$ 中出现两次，于是有 $\binom{2r + 1}r \leq \frac{2^{2r + 1}}2$，因此：
$$4^r\binom{2r + 1}r \leq 4^r\frac{2^{2r + 1}}2 = 4^{2r}$$
Q.E.D..
@13 哇！20240729
灵感来源 ABC214G
给出 $k$ 个长度为 $n$ 的数组 $a_1, \ldots, a_k$，每个元素都从 $\left[1, n\right]$ 中随机选取。
现在生成一个长度为 $n$ 的数组 $b$，每个元素也都从 $\left[1, n\right]$ 中随机选取。
问 $\bigwedge\limits_{1 \leq i \leq k}b_j \neq a_{i, j}$ 的概率。
说人话就是求
$$\lim\limits_{n \to \infty}\left(\frac{n - k}n\right)^n$$
$$ \begin{aligned} \lim\limits_{n \to \infty}\left(\frac{n - k}n\right)^n &= \lim\limits_{n \to \infty}\exp\left(\log\left(\left(\frac{n - k}n\right)^n\right)\right) \\ &= \lim\limits_{n \to \infty}\exp\left(n\log\left(\frac{n - k}n\right)\right) \\ &= \lim\limits_{n \to \infty}\exp\left(\frac{\log\left(\frac{n - k}n\right)}{\frac1n}\right) \\ &= \lim\limits_{n \to \infty} \exp\left(\frac{\frac k{kn - n^2}}{-\frac1{n^2}}\right) \\ &= \lim\limits_{n \to \infty} \exp\left(\frac{nk}{k - n}\right) \\ &= \lim\limits_{n \to \infty} \exp\left(k\frac1{\frac{k - n}n}\right) \\ &= \lim\limits_{n \to \infty} \exp\left(k\frac1{\frac kn - 1}\right) \\ &= e^{-k} \end{aligned} $$
@14 素数倒数和发散 20240822
来自 https://www.luogu.com/paste/nnhhar1a
这条中的变量 $p$ 一定是质数。
证明：
$$\lim\limits_{n \to \infty}\sum\limits_{p \leq n}\frac1p = \infty$$
如果存在 $k$ 使得
$$\sum\limits_{p > k}\frac1p < \frac12$$
那么级数收敛，同时有 $\sum\limits_{p > k}\frac np < \frac n2$。
每个 $2$ 到 $n$ 的数要么是大于 $k$ 的质数的倍数，要么是几个小于等于 $k$ 的质数的乘积。假设前者有 $x$ 个，后者有 $y$ 个，有 $x + y = n - 1$，同时 $x \leq \sum\limits_{p > k}\left\lfloor\frac np\right\rfloor \leq \sum\limits_{p > k}\frac np < \frac n2$ 和 $y \leq 2^k$。
取 $n = 2^{k + 2}$，有 $2^{k + 2} - 1 = N - 1 < \frac n2 + 2^k = 2^{k + 1} + 2^k$，$2^k < 1$，矛盾。
Q.E.D..
@15 Wolstenholme 定理 Unknown
来自 https://www.luogu.com/paste/nnhhar1a
$$\sum\limits_{1 \leq i < p}\frac1i \equiv 0 \pmod {p^2}$$
其中，$p$ 是大于等于 $5$ 的质数。
$$ \begin{aligned} \sum\limits_{1 \leq i < p}\frac1i &\equiv \sum\limits_{1 \leq i < p}\left(\frac1i + \frac1{p - i}\right)\\ &\equiv p \sum\limits_{1 \leq i \leq \left(p - 1\right)/2}\frac1{i\left(p - i\right)}\\ &\equiv \frac p2 \sum\limits_{1 \leq i < p}\frac1{i\left(p - i\right)}\\ &\equiv -\frac p2 \sum\limits_{1 \leq i < p}\frac1{i^2}\\ &\equiv -\frac p2 \sum\limits_{1 \leq i < p}i^2\\ &\equiv -\frac p2\frac{\left(p - 1\right) \cdot p \cdot \left(2p - 1\right)}6\\ &\equiv 0 \end{aligned} $$
@16 急积鸡 20241122
$$ \begin{aligned} F\left(n\right) &= \sum\limits_{x = 1}^nx^2\\ &= \int_1^nx^2 dx + \left(\sum\limits_{x = 1}^nx^2 - \int_1^nx^2 dx\right)\\ &= \frac13\left(n^3 - 1\right) + 1^2 + \sum\limits_{x = 2}^n\left(x^2 - \int_{x - 1}^xy^2 dy\right)\\ &= \frac13\left(n^3 - 1\right) + 1 + \sum\limits_{x = 2}^n\left(x^2 - \left(x^2 - x + \frac13\right)\right)\\ &= \frac13\left(n^3 - 1\right) + 1 + \sum\limits_{x = 2}^n\left(x - \frac13\right)\\ &= \frac13\left(n^3 + 2\right) + \frac{\left(2 + n\right)\left(n - 1\right)}2 - \frac{n - 1}3\\ &= \frac16\left(2n^3 - 2n + 6 + 3\left(2 + n\right)\left(n - 1\right)\right)\\ &= \frac16\left(2n^3 - 2n + 6 + 6n + 3n^2 - 6 - 3n\right)\\ &= \frac16\left(2n^3 + 3n^2 + n\right)\\ &= \frac{n\left(n + 1\right)\left(2n + 1\right)}6 \end{aligned} $$
@17 gcd 20241203
设 $a_n = 2^{2^n} + 1$，证明对于任意 $0 < i < j$，都有 $\gcd\left(a_i, a_j\right) = 1$。
$$a_{n + m} = \left(a_n - 1\right)^{2^m} + 1$$
$$a_{n + m} = \left(-1\right)^{2^m} + 1 = 2 \pmod {a_n}$$
$$\gcd\left(a_{n + m}, a_n\right) = \gcd\left(2, a_n\right) = 1$$
haokee · 2024-11-26 17:27
%%%%%%%%%%
rbtree · 2024-10-25 22:20
orz