Aufgabe 12 2024

[saltus]

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]

Dabei ist contfrac( r).q der Vektor der der Koeffizienten der (regulären) Kettenbruchdarstellung der rationalen Zahl r, der nicht auf 1 endet.

Fun-Fact  am Rande: In jeder Tiefe des Baumes ist das Maximum der Zähler bzw. Nenner eine Fibonacci-Zahl.

[maroc]

Mir fällt auf, dass die Zahlenpaare der Teilungspunkte offenbar immer teilerfremd sind. Kann das bitte jemand beweisen?

Dieser Beitrag wurde zuletzt bearbeitet: 12-23-2024, 06:44 PM von maroc.

[st1974]

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.

[maroc]

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?
  

[Vegaskid]

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;
}

[st1974]

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.