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>\Rightarrow K_{n, r} < 2^{2^n}</tex> {{---}} такого быть не может, следовательно, <tex>\exists \; f_n: r> \frac{2^n}{2n} </tex>
Обобщим для произвольного <tex>c</tex>
<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}} !!! </tex>
}}
