GraniceŚrednieZadanie nr 1127

Od ilu kubitów 2ⁿ przegania n¹⁰: najmniejsze n ≥ 2 spełniające 2ⁿ > n¹⁰

Porównywanie tempa wzrostu funkcji Analiza (calculus)Przygotowanie do Olimpiady Kwantowej

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}\).

+10 pkt za pierwsze rozwiązanie na koncie

Zapis: ułamki (3/4), pierwiastki (2sqrt(3)), pi/6.

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
  1. 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\).
  2. \(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\).
  3. \(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}\).)
  4. \(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}\).)
  5. 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.

Więcej zadań z granic →

Podobne zadania