Santa Claus — modified 2022-10-11 22:57 (85 days ago) — edit — reply
# První úloha
a. $\binom{2n}{n-1}$
b. $\binom{2n}{n}$
c. $\binom{2n}{10}$
d. $n!$
e. $n^{\sqrt{n}}$
f. $n^{15}$
g. $(\log n)^n$
h. $\log(n^n)$
i. $2^n$
Navrhuji takovéto pořadí: $c < f < h < e <i < a < b < g < d$.
1. $c < f$
$\binom{2n}{10} \underset{\text{z přednášky}}{<} (2n)^{10} = const \cdot n^{10} < n^{15}$
2. $f < h$
$h$ si přepíšeme jako $\log(n^n) = n \log(n) = 2^{\log(n \log n )}$
Exponenciála roste rychleji než polynom.
3. $h < e$
$e$ si přepíšeme jako $n^{\sqrt{n}} = 2^{\sqrt{n} \log(n)} > 2^{\log(n \log n )}$
Odmocnina roste rychleji než logaritmus.
4. $e < i$
$2^{\sqrt{n} \log(n)} < 2^n$
Lineární funkce roste rychleji než odmocnina.
5. $i < a$
Pro využití odhadu výraz upravíme $\binom{2n}{n-1} = \frac{(2n!)}{(n-1)!(n+1)!} = \binom{2n}{n}\frac{n}{n+1}$
Použijeme spodní odhad z přednášky $\binom{2n}{n-1} > 2^{2n} \frac{n}{(n+1)(2\sqrt{n})} > 2^n$
Důležitý člen je exponenciála, u $a$ je exponent dvakrát větší.
6. $a < b$
Z přednášky nebo taky podle bodu 5. (tj. $\binom{2n}{n-1} = \binom{2n}{n}\frac{n}{n+1}$)
7. $a < g$
$\binom{2n}{n} < \frac{2^{2n} }{\sqrt{2n}} < 2^{n \log \log n} =(\log n)^2$
Opět nás zajímá pouze exponenciála, n se zkrátí a dvojku přeroste vnořený logaritmus.
8. $g < d$
$2^{n \log \log n} < 2^{{\frac{n}2} \log n }= 2^{\log n^{\frac{n}2} }= n^{\frac{n}2} < n!$
Exponenciála - zajímá nás logaritmus, dvojku přeroste. Navíc logaritmus přeroste vnořený logaritmus.
# Druhá úloha
Ukažte, že pro každé přirozené číslo m platí, že součin prvočísel z intervalu $[m + 1, 2m]$ je nejvýše $\binom{2m}{m}$
$\binom{2m}{m} = \frac{(2m)!}{(m!)^2}$
Pro každé $p$ prvočíslo z intervalu platí, že je součástí rozkladu čitatele, ale už ne jmenovatele.
Uvážme prvočíselný rozklad celého čísla $\binom{2m}{m}$, musí obsahovat všechna prvočísla z intervalu, protože je ve zlomku nezkrátíme. $\square$