(12-30-2025, 10:29 AM)Georg J. aus D. schrieb: Für n = 2^46 habe ich 10^284,272647 Schafe berechnet. Meine obere Schranke liegt bei 10^422,445415 Schafen.
-> Antwort 5.
Wie kommst du auf diese "relativ kleine" obere Schranke ? Ich konnte den Wert nur grob nach oben abschätzen:
Ich habe versucht eine Vergleichsfolge (Majorante) zu bestimmen. Da bieten sich die geometrischen Folgen an.
Ich habe mir für jedes Intervall der oben aufgezählten Folgeglieder den Faktor q der geometrischen Folge berechnet die bei a_Zweierpotenz startet und bei der nächsten a_Zweierpotenz endet.
Beispiel: a_1 bis a_2 ==> q = 3 (trivial)
a_2 bis a_4 ==> q = Wurzel(15/3) = Wurzel(5) = ca. 2,23
a_4 bis a_8 ==> q = 4.Wurzel(111/15) = ca. 1,65
a_8 bis a_16 ==> q = 8.Wurzel(1215/111) = ca. 1,35
a_16 bis a_32 ==> q = 16.Wurzel(20415/1215) = ca. 1,193 (q*) für das Beispiel unten
a_32 bis a_64 ==> q = 32.Wurzel(551679/20415) = ca. 1,11
Es fällt auf, dass q immer kleiner wird (natürlich aber nie unter 1 sinken wird).
Wenn man jetzt z.B. a_64 mithilfe von einer geometrischen Folge g im letzten Intervall abschätzen will, dann nimmt man den q- Wert des vorherigen Intervalls und berechnet damit eine obere Schranke für die nächste Intervallgrenze.
Wenn man jetzt für die vielen alle anderen a_n den q Wert (ca. 1,11) des Intervall A_32 bis a_64 nimmt und mit a_64 als Startglied beginnt, erhält man eine obere Schranke S für a_2025^5.
S = g_2025^5 = a_64 * q^(2025^5-64)
Es gilt log S = log (a_64) + (2025^5-64)*log(q) = ca. 1,5235*10^15
==> S = 10^(1,5235*10^15)
S ist damit kleiner als (2025^5)^(2025^5) = ca. 10^(5,63*10^17)
Somit fällt auf jeden Fall Antwort 10 raus. Natürlich kann auch Antwort 1 nicht stimmen denn a_2025^5 ist garantiert größer als 2025^5.
Mein Abschätzung nach oben: s(2^n) <= s(2^(n-1)) * (1+2^n)
2025^5 < 2^54,92 --> C < s(2^55)
Mit dieser Abschätzung fallen die Antwortmöglichkeiten 6 bis 10 weg.
Eine brauchbare Abschätzung nach unten ist mir nicht gelungen. So habe ich alle Werte bis z. Zt. s(2^46) mit 64 Bit Floating Point gerechnet. (Das Programm läuft noch.)
Mit s(2^39) = 10^202,704073 fallen die Antwortmöglichkeiten 1 bis 4 weg.
(12-30-2025, 01:26 PM)Georg J. aus D. schrieb: Mein Abschätzung nach oben: s(2^n) <= s(2^(n-1)) * (1+2^n)
2025^5 < 2^54,92 --> C < s(2^55)
Mit dieser Abschätzung fallen die Antwortmöglichkeiten 6 bis 10 weg.
Eine brauchbare Abschätzung nach unten ist mir nicht gelungen. So habe ich alle Werte bis z. Zt. s(2^46) mit 64 Bit Floating Point gerechnet. (Das Programm läuft noch.)
Mit s(2^39) = 10^202,704073 fallen die Antwortmöglichkeiten 1 bis 4 weg.
Danke für den Hinweis. Deine Abschätzung ist deutlich feiner als meine etwas sehr grobe Abschätzung. Eine sinnvolle Abschätzung nach unten ist mir übrigens auch nicht gelungen.
Es gilt: K(g)=K(g-1)+2*K(g/2) für alle geraden g
Durch fortlaufendes Einsetzen bekommt man: K(2^n)=K(2^(n-1))+4*(K(2^(n-2)+1)+...+K(2^(n-1)))
Abschätzung nach oben (erster Summand bleibt weg, Klammer mit kleinstem Wert): K(2^n)>4*K(2^(n-2))*2^(n-2)=2^n*K(2^(n-2))>...>2^(n+(n-2)+...+2)*K(1)=2^(n(n+2)/4)
Wegen 2^54<2025^5<2^55 folgt: C>K(2^54)>2^(54*56/4)=2^756>10^227
Abschätzung nach unten (alle Summanden werden 5 mal addiert): K(2^n)<5*(K(2^(n-2)+1)+...+K(2^(n-1)))<5*2^(n-2)*K(2^(n-1))<...<5*2^((n-2)+(n-3)+...+0)*K(2)=15*2^((n-1)*(n-2)/2)
Also folgt: C<15*2^(54*53/2)<2^1435<10^432
Sei a die Größe des (2025^5)-Schaf-Kongas. Dann ist, wenn ich mich nicht vertan habe,
10^227 <= a <= 10^481
und damit Antwort 5 richtig.
Um darauf zu kommen, habe ich relativ wild abgeschätzt. Ich bin mal gespannt, ob es auch kürzer / eleganter geht. Und natürlich auch, ob ich mich irgendwo vertan habe.
Abschätzung nach unten (alle Summanden werden 5 mal addiert): K(2^n)<5*(K(2^(n-2)+1)+...+K(2^(n-1)))<5*2^(n-2)*K(2^(n-1))<...<5*2^((n-2)+(n-3)+...+0)*K(2)=15*2^((n-1)*(n-2)/2)
Also folgt: C<15*2^(54*53/2)<2^1435<10^432
Somit Antwort Nr. 5
Die andere Richtung kann ich nachvollziehen, aber was passiert hier bei den "<...<"? Wenn ich die Abschätzung K(2^n) < 5*2^(n-2)*K(2^(n-1)) wiederholt anwende, müsste dann nicht jedes mal auch noch ein Faktor 5 dazukommen?
Das hätte auch gut als Zusatzaufgabe auf einem meiner Übungsblätter in den ersten zwei Semestern im Mathestudium stehen können. Eine Lösung, die für mathematische Laien oder Zehntklässler verständlich ist, die vermutlich Logarithmen, Summen- und Produktzeichen und vollständige Induktion nicht kennen, habe ich leider nicht gefunden. Ich bin gespannt, wie die Musterlösung das macht.
---Herangehensweise---
Hier habe ich auch erstmal den Computer bemüht, um einschätzen zu können, wie schnell diese Folge wächst. Dafür habe ich die ersten 10 Millionen Folgenglieder berechnet und in einem halb und einem beidseitig logarithmischen Plot dargestellt. Polynomielles Wachstum würde im beidseitig logarithmischen Plot eine Gerade sein, exponentielles Wachstum im halb logarithmischen. Die eigentliche Kurve wuchs dann im loglog-Plot schneller als eine Gerade, aber im semilog-Plot deutlich langsamer, es handelt sich also (wie mein Bauchgefühl vorher schon sagte) um subexponentielles Wachstum, also schneller als polynomiell, langsamer als exponentiell. Ich habe dann versucht, den Loglog-Plot mit einer quadratischen Funktion anzunähern, und festgestellt, dass das sehr gut funktioniert. Wenn log(f(exp(x)) in etwa ax^2+bx+c ist, dann bedeutet das, f(x) ist etwa exp(a log(x)^2 + b log(x) + c). Mit den Parametern des Fits habe ich dann eine ganz gute Näherung gefunden, diese bei 2025^5 ausgewertet und kam auf ein Ergebnis, das klar im Bereich der Antwortmöglichkeit 5 liegt.
Das ist aber natürlich kein Beweis, die Abschätzung könnte ja auch bei größeren n völlig daneben liegen. Also habe ich mir, nachdem ich 5 angekreuzt hatte, den Hinweis mit den Zweierpotenzen angeschaut. Genauer gesagt habe ich mir erst einmal die ersten Werte für a_(2^n) angeschaut und wie diese wachsen. Ich wusste ja schon, dass f(2^n) in etwa exp(a n^2) sein wird für irgendein a, also wird der Quotient f(2^(n+1))/f(2^n) immer noch exponentiell wachsen, der Quotient aus zwei aufeinanderfolgenden Quotienten a_(2^(n+2))a_(2^n)/(a_(2^(n+1)))^2 sollte allerdings in etwa konstant sein, und tatsächlich schien dieser Wert sich langsam von unten an 2 anzunähern. Wenn a_(2^(n+1))/a_(2^n)) in jedem Schritt um etwa k wächst, hätte man a_(2^0) = a0, a_(2^1) = k a0, a_(2^2) = k * k^2 * a0, a_(2^n) = k^(n(n+1)/2) * a0, dies würde einem Wert von a = log2(k)/2 in a_n ~= 2^(a log2(n)^2 + b log2(n) + c) entsprechen. Da der reale Wert irgendwo über sqrt(2) anfängt und sich von unten an 2 annähert, erschienen mir log2(sqrt(2))/2 =1/4 und log2(2)/2 = 1/2 hier als sinnvolle Ansätze für eine untere und obere Schranke. Das Ergebnis meines Fits war übrigens etwa f(n) = 2^(0.45*log2(n)^2 - 0.73*log2(n) + 8.14), also sollten 1/4 und 1/2 als Schranken funktionieren, wobei letzteres eine engere Schranke sein sollte.
Immer noch kein Beweis. Dass Zweierpotenzen für die Rekursionsformel hilfreich sein könnten, liegt aber nahe, denn a_(2^n) = a_(2^n-1) + 2 a_(2^(n-1)). Will ich hier eine geschlossene Form bekommen, die nur Zweierpotenzen enthält, muss ich aber noch a_(2^n-1) loswerden, dies ist a_(2^n-2) + 2 a_(2^(n-1)). Das hat mich auf die Idee gebracht, die Rekursionsformel so oft anzuwenden, dass der erste Summand bei a_(2^(n-1)) ankommt.
---Eigentliche Lösung ab hier---
Wiederholtes Anwenden der Rekursionsformel liefert:
Man kann dies nun nach oben und unten abschätzen, indem man alle Terme in der Summe (2^(n-2)+1 bis 2^(n-1) sind 2^(n-1)-2^(n-2)=2^(n-2) Zahlen) durch jeweils den höchsten oder den niedrigsten Summanden ersetzt (bzw nach unten den nächstkleineren, um weiterhin nur Zweierpotenzen zu haben.)
Nach oben: a_(2^n) <= a_(2^(n-1)) + 4*2^(n-2)*a_(2^(n-1)) = a_(2^(n-1)) * (1 + 2^n)
Nach unten: a_(2^n) > a_(2^(n-1)) + 4*2^(n-2)*a_(2^(n-2)) = a_(2^(n-1)) + 2^n * a_(2^(n-2))
Für die obere Schranke habe ich dann auch eine simple geschlossene Form gefunden:
Aus wiederholtem Anwenden von a^(2^n) <= a_(2^(n-1)) * (1 + 2^n) <= a_(2^(n-1)) * 2^(n+1)
folgt a^(2^n) <= a_(2^(n-1)) * 2^(n+1) <= a_(2^(n-2)) * 2^n * 2^(n+1) <= ... <= a_(2^0) * (2^2 * ... * 2^(n+1)) = 2^((n+2)(n+1)/2 - 1) = 2^((n^2+3n)/2)
Damit habe ich auch wie oben gewünscht ein Polynom mit n^2/2 im Exponenten.
Für die untere Schranke habe ich per vollständiger Induktion gezeigt, dass a_(2^n) >= 2^((n^2+2n)/4) für alle n. (Wieso ich etwas mit n^2/4 im Exponenten haben wollte, habe ich oben erklärt, und den Term 2n/4 musste ich hinzufügen, damit der Induktionsschritt funktioniert.)
Sei dies gültig für a_(2^(n-2)) und a_(2^(n-1)). Dann:
a_(2^n) > a_(2^(n-1)) + 2^n*a_(2^(n-2))
>= 2^(((n-1)^2+2(n-1))/4) + 2^n * 2^(((n-2)^2+2(n-2))/4)
= 2^((n^2-1)/4) + 2^((n^2+2n)/4)
> 2^((n^2+2n)/4)
Als Induktionsstart ist a(2^0) = 1 = 2^((0^2+2*0)/4) und a(2^1) = 3 > 2^(3/4) = 2^((1^2+2*1)/4).
Damit weiß ich für beliebige n:
2^((n^2+2n)/4) < a_(2^n) < 2^((n^2+3n)/2)
log2(2025^5) = 5 log2(2025) ist etwa 54.9, also
2^((54^2+2*54)/4) < a_(2^54) < a_(2025^5) < a_(2^55) < 2^((55^2+3*55)/2)
log2(a_(2025^5)) ist also zwischen (54^2+2*54)/4 = 756 und (55^2+3*55)/2 = 1595
log2(10^202.5) = 202.5*log2(10) ist etwa 672, log2(2.025^2025) = 2025*log2(2.025) > 2025
Also folgt 10^202.5 < a_(2025^5) < 2.025^2025.
Mein Fit von oben liefert übrigens in etwa 2^1328 für a_(2025^5). Ich bin gespannt, ob die Musterlösung einen genauereren Wert hat.
