Изменения
→Доказательство
Пусть <tex>p = \frac{2K}{2^k}</tex>.
* если <tex>|S| < K </tex> , то <tex>|h(s)| < \frac{p \cdot 2^k}{2} = K \Rightarrow P(</tex>успех<tex>) \le p/2</tex>.
* если <tex>|S| > 2K</tex>, и <tex>|S| < 2^{k-1} </tex>, то поступим следующим образом. Мы хотим, чтобы выполнялось:
<tex>P_{h,y}(\exists s: h(s)=y) \ge \frac{3}{4} \cdot \frac{|s|}{2K}</tex>
Рассмотрим <tex>y \in 2^m</tex>. <tex>P_{h}(\exists s: h(s)=y) = P_{h}(y \in \bigcup_{s}h(s)) = P_{h}(\bigcup_{s}E_s) \ge \sum_{j}P(E_s) - \sum_{s_1 \ne s_2}P(E_{s_1} \bigcap E_{s_2})= </tex>
