Uyhip2016 July

这么难的题目窝根本不会做。。part1的思路就很逆天了。。这里做个搬运工

题目

part1：

令$l(i)$为第$i$个人最底下的白帽子的层数。设一个数$k$，我们考虑这样的策略：只考虑每个人头上的前$k$顶帽子，我们假设所有$l(i)\le k$且所有$l(i)$之和是$k$的倍数。每个人都可以根据这样的策略猜出一个位置。。如果他看到别人的$l(i)>k$那就乱猜(我们甚至可以把此时的成功概率计算成$0$)。现在算成功概率。

所有$l(i)\le k$：$(1-(\frac{1}{2})^k)^n$

所有$l(i)$之和是$k$的倍数：$\frac{1}{k}$

所以概率是$\frac{(1-(\frac{1}{2})^k)^n}{k}$

取$k=\log_2 n$，这个柿子变成$\frac{(1-\frac{1}{n})^n}{\log_2 n}$，当$n\to+\infty$时就是$\frac{1}{\text{e}\log_2 n}$了。符合条件。

part2还没看→_→