Die Schnecke auf dem Gummiband

Benutzeravatar
glowhand
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 23. Okt 2008 22:23
Wohnort: Darmstadt

Die Schnecke auf dem Gummiband

Beitrag von glowhand » 11. Nov 2008 23:11

Also... vielleicht hat jemand die Aufgabe bereits gelöst und kann Lösungsansätze geben.
Ich habe das Problem mal in PHP umgesetzt. Das Ergebnis kann man sich hier ansehen:
http://jetzweb.de/spicken/schnecke.php
Scheint alles hinzuhauen, das Ergebnis erscheint mir jedoch irgendwie falsch :wink:
Aufgabe G15 (Knobelaufgabe: Harmonische Reihe)
Sei B ein 10 Meter langes Gummiband, das beliebig weit ausdehnbar ist und das sich bei Deh-
nung gleichm¨ aßig ausdehnt. Das linke Ende des Gummibandes heiße L, das rechte Ende R. Eine
Schnecke beginnt bei L auf dem Gummiband in Richtung R mit der Geschwindigkeit von einem
Meter pro Stunde zu kriechen. Jedoch wird nach jeder Stunde das Gummiband um 10 Meter
gedehnt. Dabei geschieht das Dehnen unmittelbar und verbraucht keine Zeit.
Erreicht die Schnecke den Punkt R?
Tipp: Die harmonische Reihe divergiert gegen ∞.

Christoph-D
Computerversteher
Computerversteher
Beiträge: 325
Registriert: 11. Dez 2005 13:14
Wohnort: Darmstadt

Re: Die Schnecke auf dem Gummiband

Beitrag von Christoph-D » 12. Nov 2008 00:28

Das Problem ist, dass diese Rechnungen numerisch sehr schlecht zu lösen sind, Rundungsfehler dominieren wahrscheinlich schon nach ein paar Iterationen. Wenn ich mich nicht vertan habe, ist die Rekursionsformel für den "Weg in Aussicht" \(a_{n+1} = (a_n - 1)(1 + 1/n)\) mit \(a_0 = 10\).

Ich hab das mal in Haskell hingeschrieben, die Sprache bietet nämlich rationale Zahlen mit beliebiger Genauigkeit an, und rekursive Definitionen lassen sich außerdem sehr elegant schreiben:

Code: Alles auswählen

import Data.Ratio -- Rationale Zahlen, a % b ist ein Bruch mit a im Zähler und b im Nenner.
a 0 = 10
a n = (a (n - 1) - 1) * (1 + 1 % n)
main = print $ map (fromRational . a) [0..500] -- Gibt a(0) bis a(500) aus. Für die Ausgabe werden die Zahlen in Fließkommazahlen konvertiert.
Wenn man sich die Ausgabe anschaut, scheint das zu divergieren. Vermutlich muss man die rekursive Definition erstmal in eine mehr oder weniger geschlossene Form überführen, irgendeine Reihe oder so, um dann mathematisch sicher zu argumentieren (ein Programm das eine endliche Zahl Folgenglieder berechnet ist ja noch kein Beweis. :) ).

Edit: Das divergiert nicht, in Übereinstimmung mit der "Anschauung", dass die Schnecke mindestens 1 m/h zurücklegt, aber der zusätzliche Weg, den sie durch das Dehnen erhält, letztendlich schnell genug sinkt. Meine Ergebnisse stimmen mit deinen genau überein:

Code: Alles auswählen

import Data.Ratio -- Effizientere Lösung als die von oben.
next p n = (p - 1) * (1 + 1 % n)
a = scanl next 10 [1..]
main = print $ map fromRational $ take 12368 a
gibt als letzte Zahlen 0.46811665308623956, -0.5319263551895681 aus, genau wie dein Programm. Ob man das als "Beweis" akzeptiert, ist ein umstrittenes Thema. In FGdI 3 wär die Antwort ganz klar "ja", aber sicher nicht in Mathe 1. ;)
"I believe in the fundamental interconnectedness of all things." (Dirk Gently)

ap
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 6. Dez 2007 14:28

Re: Die Schnecke auf dem Gummiband

Beitrag von ap » 13. Nov 2008 14:05

Ja, die Schnecke erreicht tatsächlich das Gummibandende. Eigentlich haben wir aber an einen richtigen Beweis gedacht und nicht an ein Programm ;-)
Hier ein paar Ideen:
rekursiv ist die Länge des Gummibandes gegeben durch:
\(l_{n+1}=l_n+10\)
und die Strecke der Schnecke ist gegeben durch:
\(s_{n+1}=(s_n+1)\cdot\frac{l_{l+1}}{l_n}\) mit \(l_0=10\) und \(s_0=0\)
Die expliziten Formeln lauten:
\(l_n=(n+1)\cdot 10\)
\(s_n=(n+1) \cdot \sum_{k=1}^n \frac{1}{k}\)
Die Gültigkeit dieser Formeln muss noch bewiesen werden (z.B. per Induktion).
Mit Hilfe dieser Formeln kann dann
\(\lim\limits_{n \to \infty} s_n - l_n\)
berechnet werden. Dabei hilft es zu wissen, dass die harmonische Reihe divergiert.

Antworten

Zurück zu „Archiv“