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