+- Foren / Forums (https://www.mathekalender.de/wp/forum)
+-- Forum: Lösungen / Solutions (https://www.mathekalender.de/wp/forum/forum-161.html)
+--- Forum: Aufgabe 20 / Challenge 20 (https://www.mathekalender.de/wp/forum/forum-221.html)
+--- Thema: 20 Lösung / Solution (/thread-1642.html)
Seiten:
1
2
RE: 20 Lösung / Solution - WolfgangR - 12-30-2025
(12-30-2025, 04:38 PM)hg1 schrieb:(12-30-2025, 03:50 PM)WolfgangR schrieb: [...]
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?
Stimmt, habe ich übersehen. Es kommt noch ein Faktor 5^53 zu meiner Grenze dazu, dann haben wir insgesamt C<10^470.
RE: 20 Lösung / Solution - hg1 - 12-30-2025
Ich habe versucht die Wachstumsrate der Folge zu untersuchen. Die exakte Zahl c(n) der Schafe erfüllt
c(x) - c(x-1) = 2 c(x/2) (x/2 aufgerundet)
Die Folge
- wächst schneller als ein Polynom x^k (denn da wäre die linke Seite von der Ordnung O(x^(k-1)) < die rechte Seite O(x^k))
- wächst langsamer als exponentiell b^x (denn da wäre die linke Seite O(b^x) > die rechte Seite O(b^(x/2)))
Also irgendetwas zwischen polynomiell und exponentiell.
Mein Ansatz: Wenn die asymptotische Wachstumsrate durch eine (stetige, glatte) Funktion f beschrieben werden kann, dann sollte sie (wegen der obigen Gleichung für c) die Differentialgleichung
f'(x) = 2 f(x/2)
erfüllen. Das ist keine gewöhnliche Differentialgleichung wegen der unterschiedlichen Argumente x und x/2, aber bei vorgegebem Anfangswert z.B. f(0) = 1 sollte sie trotzdem eine eindeutige Lösung haben.
Eine geschlossene Lösung konnte ich leider nicht finden (Aber z.B. kommt man mit f(x) = 2^(1/2 log2(x)^2) relativ nah ran, dann ist f'(x) / 2f(x/2) = const. * log2(x), das wächst also ein wenig schneller)
Dafür kann man relativ gut die Funktion approximativ auswerten und mit den exakten Werten vergleichen und tatsächlich scheint f(n)/c(n) gegen eine Konstante (ca 1.255) zu konvergieren und somit f(n)/1.255 eine sehr gute Näherung für c(n) für "große" n.
Hier ist eine Tabelle:
Code:
k f(k)/1.255 c(k)
(approx.) (exakt)
-----------------------------
2^1 10^0.923 10^0.477
2^2 10^1.488 10^1.176
2^3 10^2.240 10^2.045
2^4 10^3.197 10^3.085
2^5 10^4.372 10^4.310
2^6 10^5.776 10^5.742
2^7 10^7.417 10^7.398
2^8 10^9.302 10^9.291
2^9 10^11.436 10^11.430
2^10 10^13.825 10^13.821
2^11 10^16.472 10^16.470
2^12 10^19.382 10^19.380
2^13 10^22.555 10^22.555
2^14 10^25.996 10^25.996
2^15 10^29.706 10^29.706
2^16 10^33.687 10^33.687
2^17 10^37.942 10^37.942
2^18 10^42.471 10^42.471
2^19 10^47.276 10^47.276
2^20 10^52.359 10^52.359
2^21 10^57.720 10^57.720
2^22 10^63.360 10^63.360
2^23 10^69.281 10^69.281
2^24 10^75.483 10^75.483
2^25 10^81.967 10^81.967
2^26 10^88.734 10^88.734
2^27 10^95.785 10^95.785
2^28 10^103.119 10^103.119
2^29 10^110.739
2^30 10^118.644
2^31 10^126.834
2^32 10^135.312
2^33 10^144.075
2^34 10^153.127
2^35 10^162.465
2^36 10^172.092
2^37 10^182.007
2^38 10^192.211
2^39 10^202.704 10^202.704073 (von Georg J. aus D.)
2^40 10^213.486
2^41 10^224.558
2^42 10^235.920
2^43 10^247.573
2^44 10^259.515
2^45 10^271.748
2^46 10^284.273 10^284.272647 (von Georg J. aus D.)
2^47 10^297.088
2^48 10^310.195
2^49 10^323.593
2^50 10^337.283
2^51 10^351.265
2^52 10^365.540
2^53 10^380.106
2^54 10^394.965
2025^5 10^408.970
2^55 10^410.117
2^56 10^425.561
2^57 10^441.299
2^58 10^457.329
2^59 10^473.653
2^60 10^490.270 Code:
C ≈ 10^408.970RE: 20 Lösung / Solution - Georg J. aus D. - 12-30-2025
(12-30-2025, 06:20 PM)hg1 schrieb: Eine geschlossene Lösung konnte ich leider nicht finden (Aber z.B. kommt man mit f(x) = 2^(1/2 log2(x)^2) relativ nah ran, dann ist f'(x) / 2f(x/2) = const. * log2(x), das wächst also ein wenig schneller)
Dafür kann man relativ gut die Funktion approximativ auswerten und mit den exakten Werten vergleichen und tatsächlich scheint f(n)/c(n) gegen eine Konstante (ca 1.255) zu konvergieren und somit f(n)/1.255 eine sehr gute Näherung für c(n) für "große" n.
Ich kann leider deine Tabellenwerte nicht nachvollziehen.
f(2^4)/1,255 = 2^(1/2 * 4^2)/1,255 = 2^8/1,255 = 256/1,255 = 203,984... = 10^2,309... und nicht 10^3,197...
Wo steckt der Fehler?
RE: 20 Lösung / Solution - hg1 - 12-30-2025
(12-30-2025, 08:50 PM)Georg J. aus D. schrieb:Ah, da habe ich mich wohl etwas missverständlich ausgedrückt. Die Funktion f, die ich in der Tabelle ausgewertet habe, ist die tatsächliche Lösung der Differentialgleichung, für die ich ja wie gesagt keine geschlossene Formel habe.(12-30-2025, 06:20 PM)hg1 schrieb: Eine geschlossene Lösung konnte ich leider nicht finden (Aber z.B. kommt man mit f(x) = 2^(1/2 log2(x)^2) relativ nah ran, dann ist f'(x) / 2f(x/2) = const. * log2(x), das wächst also ein wenig schneller)
Dafür kann man relativ gut die Funktion approximativ auswerten und mit den exakten Werten vergleichen und tatsächlich scheint f(n)/c(n) gegen eine Konstante (ca 1.255) zu konvergieren und somit f(n)/1.255 eine sehr gute Näherung für c(n) für "große" n.
Ich kann leider deine Tabellenwerte nicht nachvollziehen.
f(2^4)/1,255 = 2^(1/2 * 4^2)/1,255 = 2^8/1,255 = 256/1,255 = 203,984... = 10^2,309... und nicht 10^3,197...
Wo steckt der Fehler?
Aber zumindest lässt sich eine Darstellung als unendliche Potenzreihe finden:
Da habe ich als Ansatz eine Potenzreihe f(x) = sum_{k>=0} a_k x^k genommen, und durch Ausrechnen von f'(x) und 2f(x/2) und anschließendem Koeffizientenvergleich folgt
a_0 = 1
a_1 = 2
a_{k+1}/a_k = 1/((k+1)*2^(k-1)) für alle k >= 1
explizit ausgedrückt: a_k = 1/(k! 2^(k(k-3)/2))
Wegen des Faktors 2^(k^2 / 2) wächst der Nenner extrem schnell, sodass die Summandenterme selbst für "große" x sehr schnell sehr klein werden (selbst für x = 2025^5 genügen etwas über 100 Terme vollkommen). Daher ist die numerische Berechnung von f gar kein Problem.
RE: 20 Lösung / Solution - Georg J. aus D. - 12-30-2025
Danke. Jetzt kann ich die Werte nachvollziehen.