算法导论C Problems 答案

C-1

a

如果坚持自己的选择，那么可以忽略后来主持人的开门操作，概率是\(\dfrac{1}{3}\)。

如果坚持转换，考虑如下情形：

• 一开始选到的是车（有\(\dfrac{1}{3}\)的概率），那么主持人选择一个羊的门打开后，换门将会换到的必定是羊。此时中将的概率是\(0\)。

• 一开始选到的是羊（有\(\dfrac{2}{3}\)的概率），那么主持人选择一个羊的门打开后，换门将会换到的必定是车。此时中将的概率是\(1\)。

最终概率是\(\dfrac{1}{3}\cdot 0+\dfrac{2}{3}\cdot 1=\dfrac{2}{3}\)。

最终，坚持换门的策略是更优秀的。

b

\[\begin{array}{|l|l|l|l|l|} \hline \text{is car} & \text{can switch} & \text{do switch} & p & \text{is win}\\ \hline \text{Yes}&\text{Yes}&\text{Yes} & \dfrac{1}{3}\cdot p_{\text{right}}\cdot p_{\text{switch}} & \text{No}\\ \hline \text{Yes}&\text{Yes}&\text{No} & \dfrac{1}{3}\cdot p_{\text{right}}\cdot (1-p_{\text{switch}}) & \text{Yes}\\ \hline \text{Yes}&\text{No}&\text{No} & \dfrac{1}{3}\cdot (1-p_{\text{right}}) & \text{Yes}\\ \hline \text{No}&\text{Yes}&\text{Yes} & \dfrac{2}{3}\cdot p_{\text{wrong}}\cdot p_{\text{switch}} & \text{Yes}\\ \hline \text{No}&\text{Yes}&\text{No} & \dfrac{2}{3}\cdot p_{\text{wrong}}\cdot (1-p_{\text{switch}}) & \text{No}\\ \hline \text{No}&\text{No}&\text{No} & \dfrac{2}{3}\cdot (1-p_{\text{wrong}}) & \text{No}\\ \hline \end{array}\]

c

将胜利的三个事件加起来的概率即可得到：

\(F(p_{\text{right}},p_{\text{wrong}},p_{\text{switch}})=\dfrac{1}{3}\cdot p_{\text{right}}\cdot (1-p_{\text{switch}})+\dfrac{1}{3}\cdot (1-p_{\text{right}})+\dfrac{2}{3}\cdot p_{\text{wrong}}\cdot p_{\text{switch}}=\dfrac{1}{3}(2 p_{\text{wrong}} p_{\text{switch}}-p_{\text{right}} p_{\text{switch}} + 1)\)

d

一个很直观的想法是：只要参赛者选对了就必定给他机会换，只要选错了就不给参赛者机会换。也就是说，\(p_{\text{right}}=1,p_{\text{wrong}}=0\)。

从数学上的角度，相当于是让式子\(F(p_{\text{right}},p_{\text{wrong}},p_{\text{switch}})=\dfrac{1}{3}(p_{\text{switch}}(2 p_{\text{wrong}}-p_{\text{right}}) + 1)\)的值最小。

由于\(p_{\text{switch}}>0\)，因此令\(p_{\text{right}}=1,p_{\text{wrong}}=0\)，就能使这个式子的值最小。

e

令\(p_{\text{switch}}=0\)，那么胜利的概率为\(\dfrac{1}{3}\)，将含有\(p_{\text{right}},p_{\text{wrong}}\)的项都消去了。因此，无论此时主持人如何选择\(p_{\text{right}},p_{\text{wrong}}\)的值，局面都是一样的，或者是最优的。

f

从数学上的角度，相当于是让式子\(F(p_{\text{right}},p_{\text{wrong}},p_{\text{switch}})=\dfrac{1}{3}(p_{\text{switch}}(2 p_{\text{wrong}}-p_{\text{right}}) + 1)\)的值最大。

• 当\(2 p_{\text{wrong}}-p_{\text{right}}>0\)时，令\(p_{\text{switch}}=1\)，那么\(F(p_{\text{right}},p_{\text{wrong}},p_{\text{switch}})\)可以得到最大值\(\dfrac{1}{3}(2 p_{\text{wrong}}-p_{\text{right}}+1)\)。
• 当\(2 p_{\text{wrong}}-p_{\text{right}}=0\)时，不需要考虑\(p_{\text{switch}}\)的值，总有\(F(p_{\text{right}},p_{\text{wrong}},p_{\text{switch}})=\dfrac{1}{3}\)。
• 当\(2 p_{\text{wrong}}-p_{\text{right}}<0\)时，令\(p_{\text{switch}}=0\)，那么\(F(p_{\text{right}},p_{\text{wrong}},p_{\text{switch}})\)可以得到最大值\(\dfrac{1}{3}\)。

g

由于\(p_{\text{wrong}}\in[0,1],p_{\text{right}}\in [0,1]\)，因此\(2p_{\text{wrong}}-p_{\text{right}}\in[-1,2]\)。

令\(f(x)=\dfrac{kx+1}{3}\)，那么此问题相当于寻找一个\(x_0\in[0,1]\)，使得当\(k\in[-1,2]\)时，\(f(x_0)\)的最小值最大。

由于\(x_0\ge 0\)总是成立，因此\(f(x_0)\)的最小值在\(k=-1\)时取到，为\(\dfrac{-x_0+1}{3}\)。为保证最大，只能取\(x_0=0\)。

因此，令\(p_{\text{switch}}=0\)，就能说明无论\(p_{\text{wrong}},p_{\text{right}}\)怎么取，\(F(p_{\text{right}},p_{\text{wrong}},p_{\text{switch}})\)的最小值都能最大。

h

\(\begin{aligned} \Pr\{\text{is win=Yes}\mid \text{can switch=Yes}\}&=\dfrac{\Pr\{\text{is win=Yes}\land \text{can switch=Yes}\}}{\Pr\{\text{can switch=Yes}\}}\\ &=\dfrac{\dfrac{1}{3}\cdot p_{\text{right}}\cdot (1-p_{\text{switch}})+ \dfrac{2}{3}\cdot p_{\text{wrong}}\cdot p_{\text{switch}}}{\dfrac{1}{3}\cdot p_{\text{right}}\cdot p_{\text{switch}}+\dfrac{1}{3}\cdot p_{\text{right}}\cdot (1-p_{\text{switch}})+ \dfrac{2}{3}\cdot p_{\text{wrong}}\cdot p_{\text{switch}}+\dfrac{2}{3}\cdot p_{\text{wrong}}\cdot (1-p_{\text{switch}}) }\\ &=\dfrac{p_{\text{right}}-p_{\text{right}}p_{\text{switch}}+2p_{\text{wrong}}p_{\text{switch}}}{p_{\text{right}}+2 p_{\text{wrong}}} \end{aligned}\)

由于现在主持人已经给予了机会给参赛者进行换门，因此说明\(p_{\text{right}}>0\lor p_{\text{wrong}}>0\)，因此有\(p_{\text{right}}+2 p_{\text{wrong}}>0\)。

i

令\(G(p_{\text{right}},p_{\text{wrong}},p_{\text{switch}})=\dfrac{p_{\text{right}}-p_{\text{right}}p_{\text{switch}}+2p_{\text{wrong}}p_{\text{switch}}}{p_{\text{right}}+2 p_{\text{wrong}}}\)。

当\(p_{\text{switch}}=\dfrac{1}{2}\)，有\(G(p_{\text{right}},p_{\text{wrong}},\dfrac{1}{2})=\dfrac{p_{\text{right}}-p_{\text{right}}\cdot\dfrac{1}{2}+2p_{\text{wrong}}\cdot\dfrac{1}{2}}{p_{\text{right}}+2 p_{\text{wrong}}}=\dfrac{1}{2}\)

考虑二元函数\(f_k(x,y)=\dfrac{x-xk+2ky}{x+2y}\)在\(x,y\in[0,1]\)时的值。

可以知道，\(f_k(1,0)=1-k,f(0,1)=k\)。因此，只要\(k\neq \dfrac{1}{2}\)，总存在\((x_0,y_0)\in\{(0,1),(1,0)\}\)，使得\(f(x,y)<\dfrac{1}{2}\)。

回到题目上，这说明只要\(p_{\text{switch}}\neq \dfrac{1}{2}\)，主持人就可以选择适当的\(p_{\text{wrong}},p_{\text{right}}\)使得\(G(p_{\text{right}},p_{\text{wrong}},p_{\text{switch}})\)的最小值小于\(\dfrac{1}{2}\)。

j

使用题目C-1.i的结论。在不知道主持人的策略的情况下，如果他提供了更换的机会，那么当选择\(p_{\text{switch}}= \dfrac{1}{2}\)时，无论主持人是否带有恶意，参赛者都能够以\(\dfrac{1}{2}\)的概率得到汽车。如果\(p_{\text{switch}}\neq \dfrac{1}{2}\)，只要主持人带有恶意，参赛者获得汽车的概率就不是最大的。

这一道题说明，如果题目背景假设不同，那么最终得出来的答案和策略完全不一样。

C-2

a

由于没有讲究桶中的球的先后顺序，因此独立考虑每个球任意的放法。每个球都可以选择\(n\)个桶中的一个桶的放法。因此最终一共有\(b^n\)种方法。

b

本题讲究了桶中球的顺序。先将第\(1\)个桶的球按顺序拿出来，再将第\(2\)个桶的球按顺序放在第\(1\)个桶拿出来的球的后面……最后将第\(n\)个桶的球按顺序放在第\(n-1\)个桶的球的后面。如此拿出所有的球后，\(n!\)个不同球的排序指定了桶中球的顺序。

那么现在考虑假设\(n\)个球都是一样的，将\(n\)个球放在\(b\)个桶中（桶可以留空）。那么可以考虑将这\(b\)个相同的球排成一排，然后用\(b-1\)个板插入到这些球的空隙，隔成了\(b\)份，第\(i\)份球投入第\(i\)个桶中。由于可能会有留空，这意味着可能有同一块板插入同一空隙中。这时考虑将\(b\)个球加进来，那么此时问题就转化成了桶不能留空的条件。这意味着当前这\(b+n-1\)个空隙可以分别插入\(b-1\)块板。此时有\(\dbinom{n+b-1}{b-1}\)种插法。

再考虑上球的顺序，那么最终有\(\dbinom{b+n-1}{b-1}\cdot n!=\dfrac{(b+n-1)!}{(b-1)!}\)种方法。

c

本题和C-2-b题的区别在于仅需要假设球是一样的即可，不需要有序。因此有\(\dbinom{n+b-1}{b-1}\)种方法。

d

这\(b\)个桶最多可以放一个球。因此可以视为从\(b\)个桶中选择\(n\)个桶来放这\(n\)个一样的球，因此有\(\dbinom{b}{n}\)种方法。

e

可以考虑将这\(b\)个相同的球排成一排，然后用\(b-1\)个板插入到这些球的空隙，隔成了\(b\)份，第\(i\)份球投入第\(i\)个桶中。由于桶不能留空，那么同一空隙下最多插\(1\)块板。这意味着当前这\(n-1\)个空隙可以分别插入\(b-1\)块板。此时有\(\dbinom{n-1}{b-1}\)种方法。