算法导论 33.2 Exercises 答案

33.2-1

引理 33.3 说明了，只要至少有一次算法 $A$ 进行了一次错误判断，那么整个集合就排除掉至少一半的专家。也就是说，$A$ 只要产生最多 $\lceil \lg n\rceil$ 次错误的答案，就清空一次集合 $S$。考虑 $A$ 回答错误了某个问题后，集合 $S$ 是第 $k$ 次被清空，这说明 $A$ 最多回答错误了 $k\lceil \lg n\rceil$ 次。

如果专家在某一次回答中被从 $S$ 中移出去，那么它进行了一次错误的回答。由于 $S$ 被清空 $k$ 次，因此他至少在这个过程中回答错误了 $k$ 次问题。也就是说，$\mathrm{\forall }i\in [1,n],m_i\ge k$ 均成立，因此有 $m^{\ast }\ge k$。

使用 $k\le m^{\ast }$ 这个事实，回代到上面的 $k$，我们可以知道 $A$ 最多回答错误了 $m^{\ast }\lceil \lg n\rceil$ 次。

33.2-2

令 $f(x)=\ln (1-x)+x^2+x$，那么我们只需要证明 $\mathrm{\forall }x\in [0,1/2],f(x)\ge 0$ 即可。

实际上，$f(0)=0,f(1/2)={\displaystyle \frac{3}{4}}-\ln 2>0$。

可以知道，$f^{\prime }(x)=-{\displaystyle \frac{1}{1-x}}+2x+1={\displaystyle \frac{x(2x-1)}{1-x}}$。那么 $\mathrm{\forall }x\in [0,1/2],f^{\prime }(x)\ge 0$ 成立。

因此 $f(x)$ 在 $[0,1/2]$ 上是单调递增的，有 $f(x)\ge f(0)=0$，因此原结论成立。