这是一场豪赌

这是一场豪赌

题目描述

小徐（上帝角色）准备了 $n$ 个盒子，其中恰有一个盒子里放着礼物，其余盒子都是空的。

小张和小樊轮流进行“猜盒子”游戏，小张先手，整个过程分为两部分，如下。

「选择阶段」：当前玩家从剩余的盒子中任选一个盒子：

• 若选中有礼物的盒子，则当前玩家获得礼物，游戏结束。
• 若选中空盒，则移除该盒子；若移除空盒后仍有多于 $0$ 个盒子，轮到另一名玩家继续选择。

「特权阶段」：在小张的回合，若剩余盒子数量多于 $2$ 个且其特权尚未使用，他可以选择使用该特权来代替常规的「选择阶段」：

• 小张从剩余盒子中，任选一个持有（暂不打开）；
• 小徐（上帝角色）从剩余空盒中，任选一个移除（不会移除小张选中的那个）；
• 小张可选择是否放弃手中盒子，若放弃，则从其他所有剩余盒子中，任选一个新盒子持有；
• 小张打开持有的盒子，同「选择阶段」判定。

其中，“任选”意为等概率的随机选择。

双方的目标都是最大化自己获得礼物的概率。请计算，若小张采用最优策略，其最终获胜的概率是多少？可以证明答案可以表示为一个不可约分数 $\frac{p}{q}$，为了避免精度问题，请直接输出整数 $\left(p \times q^{-1} \bmod M\right)$ 作为答案，其中 $M = (10^9+7)$，$q^{-1}$ 是满足 $q\times q^{-1} \equiv 1 \pmod{M}$ 的整数。

输入描述:

在一行上输入一个正整数 $n\left(1\leq n\leq 10^9\right)$ 代表当前游戏开始前小徐拿出了多少个盒子。

输出描述:

输出一个整数，表示小张在此次游戏使用最佳策略的情况下获得礼物的概率，答案对 $\left(10^9+7\right)$ 取模。

示例1

输入

2

输出

500000004

示例2

输入

3

输出

666666672

 

解题思路

  官方题解省略了太多证明细节，导致理解困难，所以在此完整推导并严格证明一遍。

  先分析没有特权操作时，先手获胜的概率。定义 $p_n$ 表示当前有 $n$ 个盒子，且双方仅能进行常规选择时，先手获胜的概率。获胜的情况分为两种：

1. 直接选中含礼物的盒子，概率为 $\frac{1}{n}$。
2. 选中空盒（概率为 $\frac{n-1}{n}$），移除后轮到后手，此时剩下 $n-1$ 个盒子，后手获胜概率为 $p_{n-1}$，故先手获胜概率为 $\frac{n-1}{n}(1 - p_{n-1})$。

  因此，先手获胜的总概率为 $p_n = \frac{1}{n} + \frac{n-1}{n}(1 - p_{n-1})$。该式子可以通过递推的方式进行求解，边界条件为 $p_1 = 1$：

\begin{aligned}
p_n
&= \frac{1}{n} + \frac{n-1}{n} \left( 1 - p_{n-1} \right) \\
&= \frac{n-1}{n} - \frac{n-2}{n} \left( 1 - p_{n-2} \right) \\
&= \frac{2}{n} + \frac{n-3}{n} \left( 1 - p_{n-3} \right) \\
&= \frac{n-2}{n} - \frac{n-4}{n} \left( 1 - p_{n-4} \right) \\
&= \frac{3}{n} + \frac{n-5}{n} \left( 1 - p_{n-5} \right) \\
&= \frac{n-3}{n} - \frac{n-6}{n} \left( 1 - p_{n-6} \right) \\
&\vdots \\
&= \begin{cases}
\frac{(i+1)/2}{n} + \frac{n-i}{n} \left( 1 - p_{n-i} \right), &i \equiv 1 \pmod 2 \\
\frac{n-i/2}{n} - \frac{n-i}{n} \left( 1 - p_{n-i} \right), &i \equiv 0 \pmod 2 \\
\end{cases} \\
&\vdots \\
&= \begin{cases}
\frac{n/2}{n} + \frac{1}{n} \left( 1 - p_{1} \right) &= \frac{1}{2}, &n \equiv 0 \pmod 2 \\
\frac{n-(n-1)/2}{n} - \frac{1}{n} \left( 1 - p_{1} \right) &= \frac{n+1}{2n}, &n \equiv 1 \pmod 2 \\
\end{cases} \\
\end{aligned}

  因此，在没有特权操作的情况下，先手获胜的概率取决于 $n$ 的奇偶性。当 $n$ 为偶数时，先手获胜的概率为 $p_n = \frac{1}{2}$；当 $n$ 为奇数时，先手获胜的概率为 $p_n = \frac{n+1}{2n}$。

  接下来考虑特权操作。我们首先证明，使用特权后，交换盒子一定优于保留盒子。

  若保留原有盒子，其含礼物的概率为 $\frac{1}{n}$；若交换，则相当于放弃原选择，并在移除一个空盒后，从剩余的 $n-2$ 个盒子中重新选择。由于原选择为空盒的概率为 $\frac{n-1}{n}$，且在移除一个空盒后，礼物等概率位于剩余的 $n-1$ 个盒子中，因此交换后选中礼物的概率为 $\frac{n-1}{n} \cdot \frac{1}{n-2}$。由于 $\frac{n-1}{n(n-2)} > \frac{n-1}{n(n-1)} = \frac{1}{n}$，故交换后直接选中礼物盒子的概率更大。

  进一步，无论是否直接选中礼物盒子，后续博弈均为无特权情况，剩余 $n−2$ 个盒子，由后手先行动，其获胜概率为 $p_{n-2}$。因此，保留盒子时，先手获胜的概率为：$$\frac{1}{n} + \left(1 - \frac{1}{n}\right)(1 - p_{n-2}) = 1 - \left(1 - \frac{1}{n}\right)p_{n-2}$$

  而交换盒子时，先手获胜的概率为：$$\frac{n-1}{n(n-2)} + \left(1 - \frac{n-1}{n(n-2)}\right)(1 - p_{n-2}) = 1 - \left(1 - \frac{n-1}{n(n-2)}\right)p_{n-2}$$

  由于 $\frac{n-1}{n(n-2)} > \frac{1}{n}$，交换盒子的获胜概率严格更大（当 $n > 2$ 时）。因此，一旦使用特权，最优选择必然是交换盒子。

  剩下的问题是，先手应在何时使用特权。定义 $f_n$ 表示当前有 $n$ 个盒子，且先手仍有特权时，其获胜的最大概率。如果使用特权，先手获胜的概率为 $P_n = 1 - \left( 1 - \frac{n-1}{n} \frac{1}{n-2} \right) p_{n-2}$。如果不使用特权，先手获胜的概率为 $Q_n = \frac{1}{n} + \frac{n-1}{n} \frac{n-2}{n-1} f_{n-2}$（后续回合仍保留特权）。因此，先手获胜的最大概率为 $f_n = \max\left\{ P_n, Q_n \right\}$。只有当 $P_n > Q_n$ 时，先手才会选择使用特权。由于该式子难以递推，我们将计算前几项，观察是否存在规律。

  当 $n$ 为奇数时：

\begin{aligned}
f_1 &= 1, \\
f_3 &= \max\left\{ 1 - \left(1 - \frac{2}{3 \cdot 1}\right) p_1,\ \frac{1}{3} + \frac{1}{3} f_1 \right\} = \max\left\{ \frac{2}{3},\ \frac{2}{3} \right\} = \frac{2}{3}, \\
f_5 &= \max\left\{ 1 - \left(1 - \frac{4}{5 \cdot 3}\right) p_3,\ \frac{1}{5} + \frac{3}{5} f_3 \right\} = \max\left\{ \frac{23}{45},\ \frac{3}{5} \right\} = \frac{3}{5}, \\
f_7 &= \max\left\{ \frac{88}{175},\ \frac{4}{7} \right\} = \frac{4}{7}, \\
f_9 &= \max\left\{ \frac{221}{441},\ \frac{5}{9} \right\} = \frac{5}{9}.
\end{aligned}

  上述结果均有 $P_n \leq Q_n$，因此我们猜测对于所有 $n > 1$ 的奇数，$P_n$ 始终小于等于 $Q_n$。我们可以通过数学归纳法来证明这一猜测。

  假设对于所有 $n > 1$ 的奇数，有 $f_n = \max\left\{ P_n, Q_n \right\} = Q_n = \frac{n+1}{2n}$（递推过程与 $p_n$ 类似）。首先，验证基础情形，当 $n=3$ 时，$f_3 = \max\left\{ \frac{2}{3}, \, \frac{2}{3} \right\} = \frac{2}{3}$，成立。假设对于所有小于 $n$ 的奇数 $k$，有 $f_k = \frac{k+1}{2k}$，则 $f_{n-2} = \frac{n-1}{2(n-2)}$。于是 $Q_n = \frac{1}{n} + \frac{n-2}{n} f_{n-2} = \frac{n+1}{2n}$。要证 $f_n = Q_n$，只需证明 $P_n \leq Q_n$，即：

\begin{aligned}
& P_n \leq Q_n \\
\Rightarrow& 1 - \left( 1 - \frac{n-1}{n} \frac{1}{n-2} \right) p_{n-2} \leq \frac{n+1}{2n} \\
\Rightarrow& 1 - \left( 1 - \frac{n-1}{n(n-2)} \right) \frac{n-1}{2(n-2)} \leq \frac{n+1}{2n} \\
\Rightarrow& 1 - \frac{(n(n-2)-(n-1))(n-1)}{2n(n-2)^2} \leq \frac{n+1}{2n} \\
\Rightarrow& 1 - \frac{(n^2-3n+1)(n-1)}{2n(n-2)^2} \leq \frac{n+1}{2n} \\
\Rightarrow& 2n - \frac{(n^2-3n+1)(n-1)}{(n-2)^2} \leq n+1 \\
\Rightarrow& \frac{(n^2-3n+1)(n-1)}{(n-2)^2} \geq n-1 \\
\Rightarrow& (n^2-3n+1) \geq (n-2)^2 \\
\Rightarrow& n \geq 3
\end{aligned}

  该不等式对 $n \geq 3$ 的奇数成立，且当 $n=3$ 时取等。因此 $P_n \leq Q_n$，故 $f_n = \max\left\{ P_n, Q_n \right\} = Q_n = \frac{n+1}{2n}$，证毕。

  因此，当 $n$ 为奇数时，先手始终不使用特权，其获胜的最大概率为 $\frac{n+1}{2n}$。

  当 $n$ 为偶数时：

\begin{aligned}
f_2 &= \frac{1}{2}, \\
f_4 &= \max\left\{ 1 - \left(1 - \frac{3}{4 \cdot 2}\right) p_2,\ \frac{1}{4} + \frac{2}{4} f_2 \right\} = \max\left\{ \frac{11}{16},\ \frac{1}{2} \right\} = \frac{11}{16}, \\
f_6 &= \max\left\{ \frac{29}{48},\ \frac{5}{8} \right\} = \frac{5}{8}, \\
f_8 &= \max\left\{ \frac{55}{96},\ \frac{19}{32} \right\} = \frac{19}{32}, \\
f_{10} &= \max\left\{ \frac{89}{160},\ \frac{23}{40} \right\} = \frac{23}{40}.
\end{aligned}

  除 $n=4$ 外，其余均为 $Q_n > P_n$。因此我们猜测对于所有 $n>4$ 的偶数，$P_n$ 始终小于 $Q_n$。类似于前面的推导过程，可以使用归纳法证明，这里省略详细步骤。最终，通过归纳法可以得出结论：对于所有 $n>4$ 的偶数 $f_n = \max\left\{ P_n, Q_n \right\} = Q_n = \frac{2n+3}{4n}$。其中 $f_n$ 的递推过程如下：

\begin{aligned}
f_n &= \frac{1}{n} + \frac{n-2}{n} f_{n-2} \\
&= \frac{2}{n} + \frac{n-4}{n} f_{n-4} \\
&= \cdots \\
&= \frac{i}{n} + \frac{n-2i}{n} f_{n-2i} \\
&= \cdots \\
&= \frac{n-4}{2n} + \frac{4}{n} f_{4} \\
&= \frac{2n+3}{4n}
\end{aligned}

  因此，当 $n$ 为偶数时：

• $n=2$，先手获胜的概率为 $\frac{1}{2}$；
• $n=4$，使用特权，先手获胜的最大概率为 $\frac{11}{16}$；
• $n > 4$，先手始终不使用特权，获胜的最大概率为 $\frac{2n+3}{4n}$。

  注意到代入 $n=4$ 到公式 $\frac{2n+3}{4n}$ 也能得到 $\frac{11}{16}$，因此对于 $n \geq 4$ 的情况，可以将其合并为统一的表达式。

  综上，最终结论如下：

• $n=1$，获胜的概率为 $1$；
• $n=2$，获胜的概率为 $\frac{1}{2}$；
• $n \geq 3$ 且为奇数，获胜的最大概率为 $\frac{n+1}{2n}$；
• $n \geq 4$ 且为偶数，获胜的最大概率为 $\frac{2n+3}{4n}$。

  AC 代码如下：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int mod = 1e9 + 7;int qmi(int a, int k) {int ret = 1;while (k) {if (k & 1) ret = 1ll * ret * a % mod;a = 1ll * a * a % mod;k >>= 1;}return ret;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;if (n == 1) cout << 1;else if (n == 2) cout << qmi(2, mod - 2);else if (n & 1) cout << (n + 1ll) * qmi(2 * n, mod - 2) % mod;else cout << (2 * n + 3ll) * qmi(4ll * n % mod, mod - 2) % mod;return 0;
}

 

参考资料

  牛客练习赛145 组题人题解：https://blog.nowcoder.net/n/09f12ea60a164e289a9f0854bde2ca54