猜多项式、两信封悖论、飞机座位

首先，请求出该多项式在 \(1\) 处的取值。设 \(x\) 为该多项式在 \(1\) 处的取值。接着，请求出该多项式在 \(x + 1\) 处的取值。将结果按 \(x + 1\) 进制展开，即可得到该多项式的所有系数。

解释：若多项式为 \(P(X) = a_n X^n + \cdots + a_0\)，其中 \(n = \deg P\)，则 \(P(x + 1)\) 的 \(x + 1\) 进制展开是一个形如 \(d_n \cdots d_0\) 的数，满足 \[ P(x + 1) = \sum_{i=0}^{n} d_i (x + 1)^i. \] 我们可以通过 \(x + 1\) 进制展开读出多项式的系数：展开中的每一位数字 \(d_i\) 就等于 \(a_i\)。

这之所以成立，是因为我们知道 \(x + 1\) 大于该多项式的任意一个系数。由于 \(x = P(1) = a_n + \cdots + a_0\) 且所有系数均为非负数，因此 \(x + 1\) 严格大于任意一个系数。本质上，第一步的目的是估计系数的大小，而第二步只要选取一个比每个单独系数都大的点即可（例如，你也可以请求多项式在 \(x + 2\) 处的取值，但数字越大，计算越麻烦）。

这并不与“\(d + 1\) 个点唯一确定一个次数不超过 \(d\) 的多项式”这一口诀矛盾。在此题中，我们限制了多项式的系数属于一个非常特殊的集合（非负整数），因此可以比请求 \(d + 1\) 个点做得更好。

令人惊讶的是，答案是肯定的。

首先，我们选取一个随机正整数 \(z\)。为了做到这一点，我们抛硬币！设 \(n\) 为你在首次出现正面之前需要抛硬币的次数。然后令 \(z = 2^{n-1} + 0.5\)（好吧我们撒了个谎；这不是整数，但加上 \(0.5\) 是为了在后续打破平局）。

策略如下：查看你选中的信封中有多少钱。如果信封中的金额超过 \(z\)，则保留该信封；否则，换成另一个信封。

假设 \(z\) 小于两个信封中的金额。那么你总会保留最初选中的信封，但由于你最初选中的信封是较有钱的那个的可能性相同，因此你选对信封的概率仍为 \(1/2\)。

如果 \(z\) 大于两个信封中的金额，类似的分析也成立：此时你总会换信封，选对信封的概率仍为 \(1/2\)。

然而，如果 \(z\) 恰好落在两个信封的金额之间会怎样？如果你最初选中的是钱较少的信封，你会换到较好的信封；如果你最初选中的是钱较多的信封，你会保留较好的信封。因此，在这种情况下，你保证最终拿到较好的信封！

由于 \(z\) 落在两个信封金额之间具有正概率，该策略使得你选到较好信封的概率严格大于 \(1/2\)。

设 \(p_n\) 为当飞机上有 \(n\) 名乘客时，最后一名乘客坐到自己座位的概率。我们通过强归纳法证明：对所有 \(n \geq 2\)，有 \(p_n = \frac{1}{2}\)。

首先，显然 \(p_2 = \frac{1}{2}\)。现在，假设对于某个 \(n\)，对所有 \(2 \leq m \leq n\)，均有 \(p_m = \frac{1}{2}\)。我们证明 \(p_{n+1} = \frac{1}{2}\)。

分三种情况讨论。

• 第一种情况，如果第一名乘客坐在座位 1，则最后一名乘客能够坐到自己座位的概率为 1。

• 第二种情况，如果第一名乘客坐在座位 \(n + 1\)，则最后一名乘客能够坐到自己座位的概率为 0。

• 最后，假设第一名乘客坐在座位 \(i\)，其中 \(2 \leq i \leq n\)。那么第 2 名到第 \(i - 1\) 名乘客都会坐在自己的指定座位上。当轮到第 \(i\) 名乘客时，第 \(i\) 名乘客会在剩余的 \(n - i + 2\) 把座位（座位 1，以及座位 \(i + 1, i + 2, \ldots, n + 1\)）中均匀随机地选择一把。我们可以将座位 1 重新标记为座位 \(i\)，并注意到结果与“第 \(i\) 名乘客是第一名乘客，且一开始共有 \(n - i + 2\) 名乘客”的情形相同（如果第 \(i\) 名乘客坐到了新的座位 \(i\)，则所有乘客都会坐到自己的指定座位；否则，我们重复与之前相同的过程）。换句话说，最后一名乘客坐到自己座位的概率为 \(p_{n-i+2}\)。

因此，若一开始有 \(n + 1\) 名乘客，最后一名乘客坐到自己座位的概率为 \[ p_{n+1} = \frac{1}{n + 1} \cdot 1 + \frac{1}{n + 1} \cdot 0 + \sum_{i=2}^{n} \frac{1}{n + 1} p_{n-i+2} = \frac{1}{n + 1} + \sum_{i=2}^{n} \frac{1}{n + 1} \cdot \frac{1}{2} = \frac{1}{n + 1} + \frac{n - 1}{n + 1} \cdot \frac{1}{2} = \frac{1}{2}, \] 其中第二个等号用到了归纳假设。由此我们得出结论：对所有 \(n\)，\(p_n = \frac{1}{2}\)，因此 \(p_{100} = \frac{1}{2}\)。