The Postal Owl

# 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$

Preview