Viererfolge (basierend auf einer Wettbewerbsaufgabe) < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 19:03 Mi 04.08.2004 | | Autor: | SirJective |
Hallo zsamma,
mir geistert mal wieder diese Viererfolge im Kopf rum:
Gegeben seien vier ganze Zahlen [mm] $a_0, b_0, c_0, d_0$. [/mm] Für jede natürliche Zahl n definieren wir dann
[mm] $a_{n+1} [/mm] = [mm] |a_n [/mm] - [mm] b_n|$,
[/mm]
[mm] $b_{n+1} [/mm] = [mm] |b_n [/mm] - [mm] c_n|$,
[/mm]
[mm] $c_{n+1} [/mm] = [mm] |c_n [/mm] - [mm] d_n|$,
[/mm]
[mm] $d_{n+1} [/mm] = [mm] |d_n [/mm] - [mm] a_n|$.
[/mm]
Aufgabe ist es zu zeigen, dass egal mit welchen Werten man startet, es stets ein n gibt, so dass [mm] $a_n [/mm] = [mm] b_n [/mm] = [mm] c_n [/mm] = [mm] d_n [/mm] = 0$ ist.
Das war mal eine Wettbewerbsaufgabe, mir ist nur der Wettbewerb und der genaue Wortlaut der Aufgabe entfallen.
Durch Betrachtung der Dualdarstellung der Zahlen ist mir dieser Nachweis gelungen (jedenfalls hab ich eine gute Idee  ).
Nun ist es vielleicht möglich zu zeigen, dass man die Iteration so lang bekommt wie man will, sofern man mit geeigneten Startwerten beginnt. Ich hab durch viel "trial and error" die Iteration bis auf 53 Schritte hochgetrieben. (Dann hatte ich gestern Nacht keine Lust mehr.)
Also: Wer weiß etwas darüber, ob die Iterationslänge nach oben beschränkt ist?
Man kann dieses Verfahren aber auch ganz schmerzfrei auf beliebige reelle Zahlen erweitern. Und ich glaube mal irgendwo gelesen zu haben, dass auch dann jede dieser Folge irgendwann Null wird. Nun hab ich aber die Vermutung, dass es Tupel reeller Zahlen gibt, für welche diese Iteration niemals Null wird. Mindestens eine der vier Zahlen muss dazu irrational sein.
Probiert man willkürlich ein paar reelle Zahlen aus, endet die Folge recht schnell, aber man versuche sich an diesem Startwert:
[mm] $a_0 [/mm] = 0$,
[mm] $b_0 [/mm] = 1$,
[mm] $c_0 [/mm] = 2{,}83928675521$,
[mm] $d_0 [/mm] = 6{,}22226252311$.
Die Iteration endet erst nach 53 Schritten. Ich vermute aufgrund des Aussehens der Umgebung dieses Tupels, dass "in der Nähe" dieses Wertes ein Tupel ist, dessen Iteration niemals endet.
(Zum Aussehen der Umgebung: Ich hab diese Iteration mit festen Werten [mm] a_0=0 [/mm] und [mm] b_0=1 [/mm] in eines meiner (Pascal-)Fraktalprogramme eingebaut, und bin zu diesen Werten von [mm] c_0 [/mm] und [mm] d_0 [/mm] "hineingezoomt". Der Punkt [mm] c_0,d_0 [/mm] ist ein riesiger, sehr schmaler, Iterations-Berg in einer relativ flachen Landschaft. Noch näher komme ich leider aufgrund der Gleitkomma-Arithmetik nicht heran.)
Gruss,
SirJective
[mm] $\mathrm{PS}\label{Ich habe diese Frage in keinem weiteren Forum gestellt.}$: [/mm] Ich habe den Abschnitt zu Cross-Postings in unseren Regeln gelesen und verstanden.
|
|
| |
|
Jippie!
Hab letzte Nacht bis 3:30 am Computer gesessen und gerechnet.
Ich hab das was ich in dem Fraktalprogramm gemacht hab, in ein Java-Programm umgesetzt, das mir automatisch immer längere Zahlenkolonnen geliefert hat, bei denen die Iteration immer länger dauert (was sich nicht unwesentlich auf die Laufzeit ausgewirkt hat).
Dabei hab ich mich auf die "Stelle"
[mm] $a_0=0$,
[/mm]
[mm] $b_0=1$,
[/mm]
[mm] $c_0=1,543689012$
[/mm]
[mm] $d_0=1,839286755$
[/mm]
konzentriert, weil sie im Fraktalprogramm "runder" aussieht, der "Berg" ist nicht so in die Länge gezogen wie bei der Stelle 0, 1, 2,83, 6,22.
Mit den Zwischenergebnissen, die 100 Nachkommastellen hatten, hab ich Maple gefüttert, um irgendwelche Zusammenhänge zwischen den Zahlen zu finden.
Irgendwann fiel mir auf, dass Der Quotient [mm] c_0/d_0 [/mm] dieselben Nachkommastellen wie [mm] d_0 [/mm] hat. Damit konnte ich eine Gleichung aufstellen, die [mm] c_0 [/mm] durch [mm] d_0 [/mm] ausdrückt. Das reicht aber noch nicht, um [mm] d_0 [/mm] zu bestimmen.
Dann hab ich mir angeschaut, wo jeweils beim Iterationsschritt die Differenz negativ ist, also bei der Betragsbildung das Vorzeichen gewechselt wird. Siehe da, es ist höchst regelmäßig: Eine Periode der Länge 4, die aus den Vorzeichen (+,+,+,-) besteht, welche im Kreis wandern.
Schließlich hab ich nach vielen Idee, die nichts brachten, endlich nachgeschaut, wie sie die Quotienten der Folgeglieder verhalten: Sie sind konstant (1,83, 1,83, 1,83, 0,16), und zwar ebenso periodisch verschoben wie die Vorzeichenwechsel. Damit konnte ich endlich eine Gleichung aufstellen, mit der ich [mm] d_0 [/mm] einfangen konnte.
Ich hab jetzt eine "wundervolle Lösung", die ich aber hier noch nicht präsentieren möchte. 
Gruss,
SirJective
|
|
|
| |
|
Hallo Stefan,
> Ich würde dir ja gerne was dazu schreiben, wenn ich es
> verstehen würde. Leider: ![[bahnhof]](/images/smileys/bahnhof.gif "[bahnhof]") .
Das tut mir leid. :(
> Können wir erst mal bei den ganzen Zahlen bleiben? Wie
> sieht denn da dein Beweis aus? (Ich selber habe, allerdings
> auch nur mit sehr geringem Zeitaufwand (was nichts
> entschuldigen soll), keinen hinbekommen.)
Gern können wir uns erstmal den ganzen Zahlen widmen.
Wir definieren die Iterationsfunktion:
[mm] $f\colon \IZ^4 \to \IZ^4,\ (a,b,c,d)\mapsto(|a-b|,|b-c|,|c-d|,|d-a|)$
[/mm]
Wir überlegen uns, dass diese Funktion modulo 2 wohldefiniert ist, d.h. sie induziert eine Funktion
$f [mm] \mod 2\colon (\IZ/2\IZ)^4\to(\IZ/2\IZ)^4,\ (a,b,c,d)\mapsto(a+b,b+c,c+d,d+a)$
[/mm]
Dann prüfen wir alle 16 Tupel in [mm] $(\IZ/2\IZ)^4$ [/mm] und stellen fest, dass die Iteration modulo 2 stets nach höchstens 4 Schritten endet. Das heißt für die ursprünglichen Zahlen, dass nach höchstens 4 Iterationsschritten alle vier Zahlen durch 2 teilbar sind.
Dann überlegen wir uns, dass ein Kürzen oder Erweitern des Tupels nichts daran ändert, wie lange die Iteration dauern wird, da f homogen ist:
$f(la,lb,lc,ld) = l f(a,b,c,d)$
Ist $l [mm] \neq [/mm] 0$ und n eine natürliche Zahl, dann gilt also für die n-te Iterierte [mm] $f^{(n)}$:
[/mm]
[mm] $f^{(n)}(la,lb,lc,ld)=(0,0,0,0)$ \Leftrightarrow $f^{(n)}(a,b,c,d)=(0,0,0,0)$.
[/mm]
(Das gilt sogar für alle reellen [mm] $a,b,c,d,0\neq [/mm] l$, was für den reellen Fall gebraucht wird.)
Nach höchstens 4 Schritten können wir also unser Tupel mit 2 kürzen, und erhalten so ein Tupel mit kleinerem Betragsmaximum. Da die Anwendung von f den Maximalbetrag des Tupels nicht vergrößert, führt ein Induktionsbeweis über das Betragsmaximum der Tupel zum Ziel.
> Den Rest verstehe ich von hinten bis vorne nicht. (Die
> Numerik dahinter und die Anschauung (irgendwelche Berge
> ) interessiert mich allerdings auch nicht).
Die numerischen Spielchen sind auch für die Theorie nicht wichtig.
> Was mich aber interessieren würde: Gibt es denn jetzt
> (analytisch) eine reelle (Vierer-)Folge, die nicht
> abbricht? Wenn nein: Kann man beweisen, dass es keine gibt?
> Wenn ja: Wie lautet die (und wie zeigt man, dass sie nicht
> abbricht)?
Ja, es gibt ein Tupel reeller Zahlen, für das die Iteration nicht abbricht. Zum Beweis: Anderer Beitrag.
Gruss,
SirJective
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:43 Mo 16.08.2004 | | Autor: | Stefan |
Lieber Christian!
Vielen Dank für den schönen Beweis.
Da hätte ich noch lange drüber nachdenken müssen... Die Aufgabe gefällt mir.
Liebe Grüße
Stefan
|
|
|
| |
|
Auflösung:
Sei x die einzige reelle Nullstelle des Polynoms [mm] $x^3 [/mm] - [mm] x^2 [/mm] - x - 1$. Dann bricht die Iteration für das Tupel [mm] (1,x,x^2,x^3) [/mm] nicht ab.
Beweis:
Es ist x = 1,839..., also ist $x>1$, [mm] $x^2>x$, $x^3>x^2$, $x^3>1$. [/mm] Die Iteration liefert also das Tupel
$(x-1, [mm] x^2-x, x^3-x^2, x^3-1)$.
[/mm]
Aus allen drei Komponenten kann man den Faktor $x-1$ ausklammern, man erhält das Tupel
$(x-1) * (1, x, [mm] x^2, x^2+x+1)$,
[/mm]
dessen vierte Komponente [mm] $x^2+x+1=x^3$ [/mm] ist.
Damit besteht die Iteration darin, das Tupel durch die Zahl $x-1$ zu teilen. Dabei entsteht niemals das Nulltupel.
Dies ist bei weitem nicht die einzige Lösung: Jedes Vielfache dieses Tupels hat dieselbe Eigenschaft, es gibt aber auch Lösungstupel, die nicht Vielfache dieser Lösung sind, z.B. das von mir auf 300 Stellen angenäherte Tupel [mm] $(0,1,1-\frac{1}{x},x)$.
[/mm]
Gruss,
SirJective
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:55 Fr 06.08.2004 | | Autor: | Hanno |
Hi Christian!
Hm, meinst du nun reelle oder ganze Zahlen für [mm]a_0,b_0,c_0,d_0[/mm]? Reelle nehme ich an, dann musst du das noch kurz ändern in der Aufgabenstellung.
Pah, kaum mal ne woche nichts gemacht, schon fehlt einem jeglicher Ansatz ;)
Gruß,
Hsnno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:45 Fr 06.08.2004 | | Autor: | SirJective |
Hallo Hanno!
Ich glaube, dass die Aufgabe ursprünglich mit ganzen Zahlen gestellt war, und da endet die Iteration stets nach endlich vielen Schritten.
Dann hab ich aber die Aufgabe erweitert auf reelle Zahlen, und dann endet die Iteration nicht immer.
Und genau so hab ich das auch geschrieben, oder?
Gruss,
SirJective
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:53 Sa 07.08.2004 | | Autor: | Hanno |
Hi Christian.
Tut mir leid, da habe ich nicht gründlich genug gelesen.
Gruß,
Hanno
|
|
|
|
