Изменения
→Доказательство
Итак, есть множество <tex>S \subset 2^{m}</tex>, и мы хотим доказать, что либо <tex>|S| > 2K</tex>, либо <tex>|S| < K</tex>.
Выберем <tex>k</tex> так, чтобы <tex>2^{k-2} \le 2K \le 2^{k-1}</tex>.
<tex>h(s)=y</tex>, и проверяем, верно ли в действительности, что <tex>s \in S</tex>.
Пусть <tex>p=\frac{2K}{2^k}</tex>.