(12-27-2024, 02:24 PM)maroc schrieb:(12-23-2024, 08:19 PM)st1974 schrieb:(12-23-2024, 06:44 PM)maroc schrieb: Mir fällt auf, dass die Zahlenpaare der Teilungspunkte offenbar immer teilerfremd sind. Kann das bitte jemand beweisen?
Man kann induktiv beweisen, dass für zwei benachbarte Brüche p/q und p'/q' immer gilt
p*q' - q*p' = +/- 1.
Daraus folgt automatisch, dass ggT(p,q) = ggT(p',q')=1.
Etwas verspätet meinen herzlichen Dank für die Beweisidee, die ich (obwohl mathematischer Laie) ausführen und nachvollziehen konnte! Zwei weitere Fragen, die mich im Anschluss an Aufgabe 12 umtreiben:
- Tritt jedes beliebige teilerfremde Zahlenpaar irgendwo als Teilungspunkt im Baum auf?
- Kann ein Zahlenpaar höchstens ein Mal oder auch mehrfach im Baum vertreten sein?
Ja, jedes beliebige teilerfremde Zahlenpaar ist im Baum enthalten. Einen Beweis kann ich jetzt zwar nicht aus dem Ärmel schütteln. Er hängt aber meines Wissens mit der Kettenbruchdarstellung rationaler Zahlen zusammen. Übrigens kann man den Baum zur Abzählung der nicht-negativen rationalen Zahlen benutzen und so beweisen, dass die Menge der rationalen Zahlen genauso mächtig ist wie die Menge der natürlichen Zahlen.
Jedes Zahlenpaar tritt auch genau einmal auf. Mehrfaches Auftreten ist ausgeschlossen, da die Brüche streng monoton aufsteigend sortiert sind.