Изменения

Заметим, что <tex>|s|\frac{1}{2^k} > p</tex>, а <tex>\frac{|s|}{2^{k+1}} < \frac{1}{4}</tex>. Итак, действительно, <tex>P_{h}(\exists s: h(s)=y) > \frac{3}{4}p</tex>, т.е. в этом случае <tex>V</tex> примет слово с вероятностью <tex>\frac{3}{4}p > \frac{p}{2}</tex>.

Теперь, выберем <tex>K</tex>: <tex>K = \frac{1}{3}2^{P(|x|)}</tex>. Итак, <tex>IP \subset AM</tex>. Теорема доказана.