+- Foren / Forums (https://www.mathekalender.de/wp/forum)
+-- Forum: Lösungen / Solutions (https://www.mathekalender.de/wp/forum/forum-161.html)
+--- Forum: Aufgabe 12 / Challenge 12 (https://www.mathekalender.de/wp/forum/forum-197.html)
+--- Thema: Aufgabe 12 2024 (/thread-1172.html)
Seiten:
1
2
RE: Aufgabe 12 2024 - saltus - 12-22-2024
Wenn man Basilos Vorgehen etwas weiter treibt (siehe auch die englische Wikipedia zum Stern-Brocot-Baum),
sieht man, dass sich die Anzahl der Links- und Rechtsdrehungen fast ergibt,
wenn man nur jeweils (einmal mit dem ersten, das andere Mal mit dem zweiten beginnend)
jeden zweiten Koeffizienten des Kettenbruchs (engl. continued fraction) behält und die Summen bildet.
Genaueres entnehme man folgendem kurzen Julia-Programm:
Code:
using RealContinuedFractions
function lr(r::Rational)
v = contfrac(r).q
[sum(v[2:2:end]) - 1, sum(v[1:2:end])]
end
sum([22//7 87//32].|>lr)
# --> [11, 8]Fun-Fact am Rande: In jeder Tiefe des Baumes ist das Maximum der Zähler bzw. Nenner eine Fibonacci-Zahl.
RE: Aufgabe 12 2024 - maroc - 12-23-2024
Mir fällt auf, dass die Zahlenpaare der Teilungspunkte offenbar immer teilerfremd sind. Kann das bitte jemand beweisen?
RE: Aufgabe 12 2024 - st1974 - 12-23-2024
(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.
RE: Aufgabe 12 2024 - maroc - 12-27-2024
(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?
RE: Aufgabe 12 2024 - Vegaskid - 12-27-2024
Ein Processing Code mit dem der binäre Baum durchlaufen wird, bis die gewünschte Beschriftung erreicht wird:
int links=0;
int rechts=0;
int merkelinks;
int merkerechts;
void setup() {
size(screenWidth, screenHeight);
baum(0,1,1,0,0,22,7);
baum(0,1,1,0,0,87,32);
println("Linksdrehungen: ", merkelinks);
println("Rechtsdrehungen: ", merkerechts);
}
void draw() {
background(0,0,255);
}
void baum(int lo, int lu, int ro, int ru, int level, int b1, int b2){
if (level > 19) {
level=level-1;
return;
}
if ((ro==b1) && (ru==b2)){
//println("fertig");
//println("links: ",links-1," rechts: ",rechts);
merkelinks=merkelinks+links-1;
merkerechts=merkerechts+rechts;
level=level-1;
return;
}
//links
level=level+1;
links=links+1;
baum(lo,lu,lo+ro,lu+ru,level,b1,b2);
links=links-1;
rechts=rechts+1;
//rechts
baum(ro+lo,ru+lu,ro,ru,level,b1,b2);
rechts=rechts-1;
return;
}
RE: Aufgabe 12 2024 - st1974 - 12-27-2024
(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.