牛客练习赛20 B题

未分类

---

题意：
有$n$个硬币，抛第$i$个硬币，其正面向上的概率为$p_i$，问这$n$个硬币的非空子集中满足最终有奇数个硬币正面向上的概率为$0.5$的个数.

题解：

先说结论：对$n$个硬币来说，如果其中有某个硬币正面向上的概率是$0.5$，那么总共有奇数个硬币正面向上的概率为$0.5$. 逆命题同样成立.
先证明原命题：在$n$个硬币中有一个正面向上概率为$0.5$的硬币，设其他$n-1$的硬币抛出奇数个正面向上的概率为$p$，那么对这$n$个硬币来说最终抛出奇数个正面向上的概率为：$p*(1-0.5)+(1-p)*0.5=0.5$.
再证明逆命题：这里使用数学归纳法证明，即需要证明如果$n$个硬币中没有正面向上概率为$0.5$的，那么最终正面向上的硬币个数为奇数的概率不会是$0.5$.
数学归纳法：
当$n=1$时，显然成立.
假设前$k$个均成立，下面要证明前$k+1$个成立.
假设前$k$个硬币正面向上个数为奇数的概率是$p_1(p_1\neq 0.5)$，第$k+1$个硬币正面向上的概率是$p_2$，那么前$k+1$个硬币正面向上个数为奇数的概率为

$$\begin{align*} P&=p_1*(1-p_2)+(1-p_1)*p_2 \\ &=p_1+p_2-2p_1p_2 \\ &=-2(p_1-0.5)(p_2-0.5)+0.5 \end{align*}$$
令$P=0.5$得$p_1=0.5$或$p_2=0.5$，显然矛盾，所以$P=0.5$无解.

综上证明当且仅当$n$个硬币中有正面向上概率为$0.5$的硬币才能让最终正面向上的个数为奇数的概率是$0.5$.
那么对原题来说，假设$n$个硬币中有$m(0\leq m\leq n)$个正面向上概率为$0.5$，那么：

$$\begin{align*} ans=(2^m-1)*2^{(n-m)} \end{align*}$$