20
правок
Изменения
→Оценка на количество линейных программ над \{\downarrow\} длины r
<tex>\log_2{K_{n, r}} \leq 2 r \log_2 {(n+r)} < \frac{2 \cdot 2^n}{2n} \log_2{(n+ \frac{2^n}{2n})} \leq \frac{2^n}{n} \log_2 {2^n} = 2^n \Rightarrow</tex>
<tex>K_{n, r} < 2^{2^n} \Rightarrow \exists \; f_n: r> \geq \frac{2^n}{2n} </tex>
}}
Таким образом, количество линейных программ длины <tex>< \leq \frac{2^n}{2cn}</tex> меньше не больше <tex>2^{\frac{2^n}{c}}</tex>
===Возвращение к теореме о нижней оценке===
<tex>|F_g| < 2^{\frac{2^n}{c}} \Rightarrow \frac{|F_g|}{2^{2^n}} < \frac{2^\frac{2^n}{c}}{2^{2^n}} = 2^{2^n (\overset{< 0}{\frac{1}{c}-1})}\rightarrow 0</tex>
