matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Hochschulmathe
  Status Uni-Analysis
    Status Reelle Analysis
    Status UKomplx
    Status Uni-Kompl. Analysis
    Status Differentialgl.
    Status Maß/Integrat-Theorie
    Status Funktionalanalysis
    Status Transformationen
    Status UAnaSon
  Status Uni-Lin. Algebra
    Status Abbildungen
    Status ULinAGS
    Status Matrizen
    Status Determinanten
    Status Eigenwerte
    Status Skalarprodukte
    Status Moduln/Vektorraum
    Status Sonstiges
  Status Algebra+Zahlentheo.
    Status Algebra
    Status Zahlentheorie
  Status Diskrete Mathematik
    Status Diskrete Optimierung
    Status Graphentheorie
    Status Operations Research
    Status Relationen
  Status Fachdidaktik
  Status Finanz+Versicherung
    Status Uni-Finanzmathematik
    Status Uni-Versicherungsmat
  Status Logik+Mengenlehre
    Status Logik
    Status Mengenlehre
  Status Numerik
    Status Lin. Gleich.-systeme
    Status Nichtlineare Gleich.
    Status Interpol.+Approx.
    Status Integr.+Differenz.
    Status Eigenwertprobleme
    Status DGL
  Status Uni-Stochastik
    Status Kombinatorik
    Status math. Statistik
    Status Statistik (Anwend.)
    Status stoch. Analysis
    Status stoch. Prozesse
    Status Wahrscheinlichkeitstheorie
  Status Topologie+Geometrie
  Status Uni-Sonstiges

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenUni-SonstigesViererfolge (basierend auf einer Wettbewerbsaufgabe)
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Uni-Sonstiges" - Viererfolge (basierend auf einer Wettbewerbsaufgabe)
Viererfolge (basierend auf einer Wettbewerbsaufgabe) < Sonstiges < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Viererfolge (basierend auf einer Wettbewerbsaufgabe): Übungsaufgabe
Status: (Übungsaufgabe) Übungsaufgabe Status 
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. ;-)


        
Bezug
Viererfolge (basierend auf einer Wettbewerbsaufgabe): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:56 Do 05.08.2004
Autor: SirJective

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


Bezug
                
Bezug
Viererfolge (basierend auf einer Wettbewerbsaufgabe): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:43 Fr 13.08.2004
Autor: Stefan

Lieber Christian!

Ich würde dir ja gerne was dazu schreiben, wenn ich es verstehen würde. Leider:  [bahnhof].

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

Den Rest verstehe ich von hinten bis vorne nicht. (Die Numerik dahinter und die Anschauung (irgendwelche Berge ;-)) interessiert mich allerdings auch nicht).

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)?

Liebe Grüße
Stefan

Bezug
                        
Bezug
Viererfolge (basierend auf einer Wettbewerbsaufgabe): Antwort
Status: (Antwort) fertig Status 
Datum: 22:41 Fr 13.08.2004
Autor: SirJective

Hallo Stefan,

> Ich würde dir ja gerne was dazu schreiben, wenn ich es
> verstehen würde. Leider:  [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


Bezug
                                
Bezug
Viererfolge (basierend auf einer Wettbewerbsaufgabe): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                
Bezug
Viererfolge (basierend auf einer Wettbewerbsaufgabe): Antwort
Status: (Antwort) fertig Status 
Datum: 22:52 Fr 13.08.2004
Autor: SirJective

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


Bezug
        
Bezug
Viererfolge (basierend auf einer Wettbewerbsaufgabe): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                
Bezug
Viererfolge (basierend auf einer Wettbewerbsaufgabe): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                        
Bezug
Viererfolge (basierend auf einer Wettbewerbsaufgabe): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 08:53 Sa 07.08.2004
Autor: Hanno

Hi Christian.
Tut mir leid, da habe ich nicht gründlich genug gelesen.

Gruß,
Hanno

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.unimatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]