GraniceŚrednieZadanie nr 1127
Od ilu kubitów 2ⁿ przegania n¹⁰: najmniejsze n ≥ 2 spełniające 2ⁿ > n¹⁰
Pełny opis stanu \(n\) kubitów wymaga \(2^n\) amplitud, a pewien algorytm wielomianowy wykonuje \(n^{10}\) operacji. Dla niewielkich \(n\ge2\) wielomian jest większy, ale funkcja wykładnicza w końcu go przegania.
Wyznacz najmniejszą liczbę całkowitą \(n\ge 2\), dla której \(2^n > n^{10}\).
Świetnie.
Jak rozwiązać to zadanie?
Potrzebujesz pomocy? Pokaż wskazówkę
Zlogarytmuj nierówność: \(2^n>n^{10}\iff g(n) = n - 10\log_2 n > 0\). Zbadaj monotoniczność \(g(x)\) pochodną, a potem sprawdź znak \(g\) w kilku punktach, porównując piąte potęgi zamiast liczyć logarytmy.
Chcesz poznać sposób? Rozwiązanie krok po kroku
- Nierówność \(2^n>n^{10}\) jest równoważna \(n>10\log_2 n\), czyli \(g(n)>0\) dla \(g(x) = x-10\log_2 x\), \(x\ge2\).
- \(g^{\prime}(x) = 1-\frac{10}{x\ln2}\), więc \(g\) maleje na \([2, x_0]\) i rośnie na \([x_0,\infty)\), gdzie \(x_0 = \frac{10}{\ln 2}\approx14{,}4\). Ponieważ \(g(2) = 2-10<0\), na przedziale \([2,x_0]\) funkcja jest ujemna, a dalej rośnie — jest więc dokładnie jedno miejsce, od którego \(g>0\).
- \(n=58\): \(g(58)<0\iff \log_2 58 > 5{,}8 \iff 58^5 > 2^{29}\). Rzeczywiście \(58^5 = 656\,356\,768 > 536\,870\,912 = 2^{29}\). (Bezpośrednio: \(2^{58}\approx2{,}88\cdot10^{17} < 58^{10}\approx4{,}31\cdot10^{17}\).)
- \(n=59\): \(g(59)>0\iff \log_2 59 < 5{,}9\iff 59^5 < 2^{29{,}5} = 2^{29}\sqrt2\). Mamy \(59^5 = 714\,924\,299\) oraz \(2^{29}\sqrt2\approx 759\,250\,125\), więc nierówność zachodzi. (Bezpośrednio: \(2^{59}\approx5{,}76\cdot10^{17} > 59^{10}\approx5{,}11\cdot10^{17}\).)
- Skoro \(g(58)<0\), a \(g\) na \([x_0,58]\) rośnie, to \(g<0\) dla wszystkich całkowitych \(2\le n\le58\). Najmniejsze szukane \(n\) to \(59\).
Odpowiedź: \(59\)
Czego warto się nauczyć?
Granice to pierwszy krok analizy: opisują, do czego zmierza wyrażenie. W zadaniach ćwiczysz ilorazy, granice specjalne i szacowanie.