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