Rolf B: Mathematik für's Wochenende (und darüber hinaus...)

(Nachgetragene Infos auf Grund von Rückfragen in Kursivschrift)

Stellt euch eine Menge aus Punkten $$S = \{ P_1, P_2, P_3, ..., P_n\}$$ in der Ebene vor. Es sind mindestens 2, und endlich viele. Die einzige Einschränkung ist: Keine 3 dieser Punkte liegen gemeinsam auf einer Geraden.

Wählt euch einen dieser Punkte $$P_i$$ aus und legt eine (fast) beliebige Gerade hindurch. Die einzige Einschränkung ist, dass sie durch keinen der anderen Punkte geht. Es sind nur endlich viele andere Punkte, das schafft ihr!

Und nun beginnt diese Gerade in der Ebene um $$P_i$$ herum im Uhrzeigersinn zu rotieren. Irgendwann berührt sie einen anderen Punkt $$P_j$$ - blip! - und rastet dort ein. $$P_j$$ wird zum neuen Drehpunkt, und die Gerade dreht sich um ihn weiter, bis sie - blip! - einen $$P_k$$ berührt ($$i=k$$ ist nicht auszuschließen) und dieser die Rolle des Drehpunktes übernimmt. Und so weiter, und so weiter - blip - blip blip - blip - blibliblip - blip - blip...

Wer kann zeigen, dass man den Startpunkt und die Lage der Geraden so wählen kann, dass die Gerade im Verlauf ihrer Rotation jeden der Punkte aus $$S$$ unendlich oft als Drehpunkt hat (wenn man unendlich lange zuguckt, heißt das).

Rolf

--
sumpsi - posui - obstruxi
  1. Es sind nur endlich viele

    Zum Verständnis. Das bezieht sich auf die Punkte durch die die Geraden nicht gehen dürfen, aber nicht auf die Anzahl der möglichen Geraden?

    1. Hallo encoder,

      ja, richtig. Es bezieht sich auf die Anzahl der Punkte in der Punktewolke - also letztlich auf die Lagen, die die Gerade als Startposition NICHT haben darf.

      Das steht da, damit mir keiner damit kommt, dass man bei einer Wolke aus massig Punkten nachher die Gerade gar nicht mehr unterbekommt. Das mag passieren können, wenn man mit dem dicken Edding zeichnet. Aber das tut ein Mathematiker ja nicht.

      Rolf

      --
      sumpsi - posui - obstruxi
  2. Und nun beginnt diese Gerade im Uhrzeigersinn zu rotieren.

    Gemeint ist: um den Drehpunkt $$P_i$$ (oder?)

    1. Hallo ottogal,

      genau.

      Rolf

      --
      sumpsi - posui - obstruxi
  3. Hallo,

    niemand interessiert? Oder niemand mit einer Idee?

    Zugegeben, ich hatte auch keine. Dabei ist es tatsächlich einfach, wenn man die Lösung sieht. Wie so oft…

    Ein Tipp: Man sollte zuerst den Sonderfall "Ungerade Punktezahl" betrachten. Und man muss die Gerade so legen, dass sich bestimmte Eigenschaften der Gesamtkonstruktion beim Wechsel des Drehpunktes nicht verändern (oder auf mathematisch: es gilt, eine Invariante zu finden)

    Bei gerader Punktezahl pendelt das Szenario zwischen zwei Invarianten hin und her, deswegen ist dieser Fall etwas umständlicher.

    Rolf

    --
    sumpsi - posui - obstruxi
    1. Hallo Rolf,

      niemand interessiert?

      für mich fehlt dieser Aufgabe der "Biss". Sie ist nicht nur sehr komplziert (ich habe nicht einmal die Aufgabenstellung wirklich verstanden), sondern aus meiner Sicht auch bar jeder sinnvollen Anwendungsmöglichkeit.

      Dabei ist es tatsächlich einfach, wenn man die Lösung sieht. Wie so oft…

      Das kenne ich auch aus der Berufspraxis. Man hat eine Elektronikbaugruppe und geht damit in die EMV-Prüfung. Da passieren dann auf einmal merkwürdige Dinge, die nicht passieren sollten.
      Also fängt der Hardware-Ingenieur an zu grübeln, er misst hier, misst da, kommt dem Problem nicht so richtig auf die Schliche. Systematische Fehlersuche ist in dem Bereich auch sehr schwierig. Irgendwann hat man dann eine kleine Modifikation, bei der das Problem "zufällig" nicht mehr auftritt. Ist das reproduzierbar? Tatsächlich. Was ist nun anders?
      Und dann fällt es einem wie Schuppen aus den Haaren (unsere Hardwareentwickler sind alle jung genug, dass sie noch reichlich Haare haben), und man klatscht sich an die Stirn: Ach, daran lag es! Ja klar, jetzt verstehe ich es auch!

      Einen schönen Tag noch
       Martin

      --
      Мир для України.
    2. Hallo Rolf,

      ich finde die Aufgabe sehr interessant. Leider hatte ich nicht viel Zeit, mich da hineinzudenken. Einige wenige Ansätze liefen bald in eine Sackgasse.

      Deswegen freut mich dein Tipp. Auf die Idee, nach einer Invarianten zu suchen, wäre ich nicht gekommen.

      Lass mal die Sache ruhig noch eine Weile offen...

      Dank und Gruß
      ottogal

  4. Hallo,

    Wer kann zeigen, dass man den Startpunkt und die Lage der Geraden so wählen kann, dass die Gerade im Verlauf ihrer Rotation jeden der Punkte aus $$S$$ unendlich oft als Drehpunkt hat (wenn man unendlich lange zuguckt, heißt das).

    Mein Bauch fühlt sich so an, als ob es schwieriger bis unmöglich sei, einen Startpunkt zu finden, bei dem das nicht der Fall wäre...

    Aber ich hab keinen Plan wie ich das geomathrisch angehen soll...

    Gruß
    Kalk

  5. Wer kann zeigen, dass man den Startpunkt und die Lage der Geraden so wählen kann, dass die Gerade im Verlauf ihrer Rotation jeden der Punkte aus $$S$$ unendlich oft als Drehpunkt hat (wenn man unendlich lange zuguckt, heißt das).

    Rolf

    Entweder habe ich die Aufgabe falsch verstanden, oder sie ist trivial und man kann sehr leicht das Gegenteil zeigen. Ich schätze die Aufgaben hier und deren Qualität sehr und gehe deshalb von ersterem aus.

    1. Hallo Friedel,

      wenn die Punkte auf den Ecken eines konvexen Polygons liegen, wird das Problem von jeder Geraden gelöst. In allen anderen Fällen findest Du Geraden, die nur die konvexe Hülle der Punktewolke ablaufen und damit nicht alle Punkte erreichen.

      Die Frage ist aber nicht, ob es mit jeder Geraden funktioniert. D.h. das eine Gegenbeispiel nützt nichts. Gesucht ist ein Prinzip, wie Du die Gerade in jeder Punktewolke (die die Grundvoraussetzung der Aufgabenstellung erfüllt) so platzieren kannst, dass sie bei ihrer Rotation jeden Punkt der Punktewolke erreicht. Es genügt also, dass es mindestens eine gibt, bei der es funktioniert.

      Es wäre übrigens ein Missverständnis, wenn Du bei Punkten A,B,C,D,E voraussetzen würdest, dass die Gerade jeden Punkt genau einmal berührt (also beispielsweise A, B, C, D, E und wieder von vorn). Eine Berührabfolge A,B,C,A,C,D,A,D,E,A,E,B, - und wieder von vorn - ist durchaus erlaubt. Ich meine, dass diese Abfolge entsteht, wenn Du B,C,D,E als Quadrat anordnest, A in die Mitte setzt (Edit: nicht genau in die Mitte, wegen der Randbedingungen) und die Gerade initial durch A gehen lässt.

      Ein streng formaler Beweis ist auch vermutlich zu viel verlangt. Die Begründung, die mir vorliegt, ist ebenfalls nicht streng formal. Ich kann euch aber im Zweifelsfall eine Person nennen, die mit dieser Aufgabe konfrontiert war und die volle Punktezahl bekommen hat…

      Rolf

      --
      sumpsi - posui - obstruxi
      1. wenn die Punkte auf den Ecken eines konvexen Polygons liegen, wird das Problem von jeder Geraden gelöst. In allen anderen Fällen findest Du Geraden, die nur die konvexe Hülle der Punktewolke ablaufen und damit nicht alle Punkte erreichen.

        Das habe ich auch schnell gefunden.

        Die Frage ist aber nicht, ob es mit jeder Geraden funktioniert. D.h. das eine Gegenbeispiel nützt nichts. Gesucht ist ein Prinzip, wie Du die Gerade in jeder Punktewolke (die die Grundvoraussetzung der Aufgabenstellung erfüllt) so platzieren kannst, dass sie bei ihrer Rotation jeden Punkt der Punktewolke erreicht. Es genügt also, dass es mindestens eine gibt, bei der es funktioniert.

        Genau.

        Es wäre übrigens ein Missverständnis, wenn Du bei Punkten A,B,C,D,E voraussetzen würdest, dass die Gerade jeden Punkt genau einmal berührt (also beispielsweise A, B, C, D, E und wieder von vorn). Eine Berührabfolge A,B,C,A,C,D,A,D,E,A,E,B, - und wieder von vorn - ist durchaus erlaubt. Ich meine, dass diese Abfolge entsteht, wenn Du B,C,D,E als Quadrat anordnest, A in die Mitte setzt und die Gerade initial durch A gehen lässt.

        Meine Vermutung ist, dass diese Berührabfolge jedenfalls in eine periodische Schleife münden müsste, wenn die Aussage wahr sein soll.
        Aber wie das beweisen...?

      2. … Ich meine, dass diese Abfolge entsteht, wenn Du B,C,D,E als Quadrat anordnest, A in die Mitte setzt und die Gerade initial durch A gehen lässt. …

        Danke, jetzt ist die Aufgabe klar. Das Beispiel passt allerdings nicht. Da die Anordnung nicht der Aufgabe entspricht und es 2 Gruppen von je 3 Punkten auf einer geraden gibt, lässt sich der Algorithmus nicht anwenden.

        Ich denke, dass ich den Lösungsweg kenne. Aber die Beschreibung ist nicht so einfach, wie der Lösungsweg.

        1. Hallo Friedel,

          Da die Anordnung nicht der Aufgabe entspricht

          jaaa, okay. Nicht genau in die Mitte. Nicht auf eine der Diagonalen. Aber so in
          etwa mittelmäßig (center-ish, modern english formuliert)

          Ich denke, dass ich den Lösungsweg kenne. Aber die Beschreibung ist nicht so einfach, wie der Lösungsweg.

          Dann skizzier ihn doch erstmal und schick es per PN.

          Rolf

          --
          sumpsi - posui - obstruxi
          1. Ich denke, dass ich den Lösungsweg kenne. Aber die Beschreibung ist nicht so einfach, wie der Lösungsweg.

            Dann skizzier ihn doch erstmal und schick es per PN.

            Rolf

            Dass ich den Text um 12:12 Uhr durchgestrichen habe, bedeutet, dass ich da schon nicht mehr dachte, dass ich den Lösungsweg kenne. Außerdem ist es imho noch viel schwieriger, eine Gerade zu skizzieren, die abwechselnd um mehrere Punkte rotiert, als sie zu beschreiben …

  6. Hallo,

    außer von Ottogal hatte ich bisher keine privaten Einsendungen. Ich nehme daher an, dass alle anderen die Lösung schon erbingelt haben - oder aufgegeben 😉

    Damit wäret ihr - und auch ich - in guter Gesellschaft, denn diese Aufgabe war Teil der Internationalen Mathematik Olymipade 2011. Die IMO findet an 2 Tagen statt, mit je 3 Aufgaben. Diese hier war Aufgabe 2 - d.h. "mittlere Schwierigkeit" von Tag 1. Aber während Aufgabe 3 von 51 Teilnehmer*innen korrekt gelöst wurde (7/7 Punkte), schafften das bei Aufgabe 2 nur 22.

    Unter ihnen Lisa Sauermann, die 2011 als Einzige in allen Aufgaben 7 Punkte bekam. Es gibt von ihr eine Ausarbeitung zur Lösung der Aufgabe, aber niemand erklärt diese "Windmühle" so schön wie Grant Sanderson in seinem Mathe-Kanal 3Blue1Brown: The unexpectedly hard windmill question.

    Wenn ihr noch grübeln wollt - ihr könnt in das Video hineinschauen, die Lösung kommt nicht sofort.

    Rolf

    --
    sumpsi - posui - obstruxi