Quelle/Source: Schmeh

Das Leiter-Kiste-Problem ist eine einfache mathematische Fragestellung, die erstaunlich schwer zu lösen ist. Und sie hat mit Kryptografie zu tun.

English version (translated with DeepL)

Im November habe ich über das Problem der gekreuzten Leitern gebloggt. Dieses mathematische Problem hat es in sich: Die Fragestellung sieht recht unspektakulär aus, doch die Lösung ist äußerst kompliziert.

Aus Sicht eines Kryptologen ist das Problem der gekreuzten Leitern interessant, weil man beim Lösen auf ein multivariates Gleichungssystem zweiten Grades stößt. Solche Gleichungssysteme bilden die Grundlage von so genannten multivariaten Krypto-Verfahren. Diese wiederum werden zur Post-Quanten-Kryptografie gezählt, da sie nicht mit einem Quanten-Computer geknackt werden können. Es gibt zwar multivariate Krypto-Verfahren, die sich zum Verschlüsseln nutzen lassen, doch praxisrelevant sind nur multivariate Signaturverfahren.

Beim Problem der gekreuzten Leitern besteht das multivariate Gleichungssystem aus drei Gleichungen, und es gibt drei Variablen. Für ein multivariates Krypto-Verfahren ist das nicht komplex genug. Dort hat man es eher mit 72 Gleichungen und 140 Variablen zu tun. Ein solches Gleichungssystem kann selbst der beste Computer innerhalb von Jahrmillionen nicht lösen.

Insgesamt gab es nach meinem Artikel über die gekreuzten Leitern 56 Leserkommentare, was nicht alle Tage vorkommt.

 

Die Übersichtsarbeit von Michael Schneider

Blog-Leser Michael Schneider hat zum Thema der gekreuzten Leitern eine ausführliche Abhandlung verfasst, die er mir dankenswerterweise zur Verfügung gestellt hat. Hier kann man sie herunterladen. Auf insgesamt 21 Seiten werden drei Lösungswege behandelt, darunter ein grafischer. Wirklich beeindruckend!

Quelle/Source: Michael Schneider

Michael Schneider hat Energie und Verfahrenstechnik sowie Bionik und Evolutionsstrategie an der TU Berlin studiert. 1976, in seinem ersten Jahr an der Universität, gründete er eine Firma, die Software für Ingenieur- und Architekturbüros schrieb. Nach Abschluss des Studiums hatte er 25 Jahre lang ein Ingenieurbüro. Heute ist er im Bereich der Großfinanzen aktiv, wo er sich mit seinem Geschäftsfreund Dr. Weisert um Spezial-Kapitalvermehrung (Privat Placement) im sehr hohen Bereich kümmert.

 

Das Leiter-Kiste-Problem

Außer dem Problem der gekreuzten Leitern gibt es noch weitere Leiterprobleme. Eines davon ist das Leiter-Kiste-Problem. Dieses kann man wie folgt beschreiben:

Eine würfelförmige Kiste mit einer Kantenlänge von einem Meter steht vor einer Wand. Eine 5 Meter lange Leiter lehnt an der Wand und berührt dabei die Kiste an einer Kante. Wie hoch reicht die Leiter?

Quelle/Source: Schmeh

In der Zeichnung ist x die gesuchte Variable. Wie man sich schnell klar macht, gibt es zwei Lösungen. Uns soll nur die größere interessieren.

Man kann nun folgendes Gleichungssystem aufstellen:

Die erste Gleichung ergibt sich aus dem Satz des Pythagoras. Gleichung 2 kann man aus der Tatsache herleiten, dass man es mit zwei ähnlichen Dreiecken zu tun hat. Die dritte Gleichung ist offensichtlich.

Man kann die Gleichungen wie folgt umformen:

Nun haben wir ein multivariates Gleichungssystem zweiten Grades. Wie bereits erwähnt werden solche Systeme in der Post-Quanten-Kryptografie verwendet, wenn auch mit deutlich mehr Variablen und Gleichungen.

Auch das Leiter-Kiste-Problem ist erstaunlich komplex, wenn man bedenkt, wie einfach es zu beschreiben ist.

Auf der Webseite “Mathematische Basteleien” findet man die Lösung des Problems. Demnach hat x den Wert 4,84 Meter. Natürlich kann man die Aufgabe auch mit anderen Parametern durchrechnen.

Falls jemand andere Lösungswege findet, würde mich das natürlich auch interessieren. Kommentare nehme ich gerne entgegen.


Further reading:
Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/

Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Kommentare (5)

  1. #1 Peyre
    21. Januar 2022

    Presh Talwalkar from the Youtube channel MindYourDecision shows an interesting solution to the general case based on geometry: https://youtu.be/CZKD7rffF0M

    by the way, he also have a geometric solution for the cross ladders problem: https://youtu.be/IaQwWINzjtA

  2. #2 Karl-Heinz
    Graz
    23. Januar 2022

    Auch das Leiter-Kiste-Problem ist erstaunlich komplex, wenn man bedenkt, wie einfach es zu beschreiben ist.

    Wie ich die Mathematiker kenne, haben einige von ihnen sicher ein Verfahren im Gepäck, mit dem sich diese spezielle Gleichung des Leiter-Kiste-Problem sehr schnell ohne Aufwand lösen lässt.

    Betrachtet man die Gleichung näher, so erkennt man, dass aus x y folgt und aus y z folgt. Ich schreibe die Gleichung 1 etwas um.
    Gleichung 1); f1(y,z)= y^2 + 2y + z^2 + 2z – 23 = 0.
    Ist x korrekt ergibt Gleichung f1(y,z) genau 0.
    Das vollständige Differential von Gleichung 1 ist:
    Δf1= (2y+2)*Δy + (2z+2)*Δz.
    Da sich mit y auch z verändert, bewegen wir uns für die Korrektur nur in Δy Richtung. Wir rechne jetzt
    Δf1= (2y+2)*Δy .
    Δy = Δf1/(2y+2)

    Beispiel: Startwert: x =5, damit ist y =4 und z=1/4
    f1(y=4,z=1/4) = 1,5625. Wir müssen also um -1,5625 korrigieren.
    Δy = Δf1/(2y+2)= -1,56257/(2*4+2)=-0,15625
    y_neu = y_alt + (-0,15625) = 3,84375.
    damit ergibt sich x = y_neu+1 = 4,84375.
    Will man x etwas genauer als auf zwei Stellen berechnen, muss man das Prozedere wiederholen. 😉

  3. #3 Klaus Schmeh
    23. Januar 2022

    @Karl-Heinz:
    Ein sehr eleganter Lösungsweg. Wenn ich das richtig verstehe, geht es hier um ein iterativ gelöstes System von Differenzialgleichungen. Darauf wäre ich nicht gekommen.

  4. #4 U. Hans
    Bielefeld
    30. Januar 2022

    Hallo !

    Ich habe mir mal die beiden Leiterhälften als komplexe Zeiger vorgestellt.
    Der Ursprung der komplexen Zahlenebene liegt am mittigen Berührungspunkt.

    Realanteil linker/oberer Zeiger :

    r1 * cos(a+pi) = -1

    Imaginäranteil rechter/unterer Zeiger :

    r2 * sin(a) = -1

    Länge beider Zeiger zusammen :

    r1 + r2 = 5

    Umformen und bei WolframAlpha eingeben :

    1/cos(a) – 1/sin(a) = 5

    Diesen Winkel ausgespukt :

    a≈ – 2.0 * 0.127426764118761 rad = 14.60203156202815977 °deg

    Kontrolle :

    x = 5m * cos(- 2.0 * 0.127426764118761) = 4.8385011606 m

    M.f.G.

  5. #5 Klaus Schmeh
    30. Januar 2022

    @U. Hans:
    Es geht also auch mit komplexen Zahlen. Wirklich erstaunlich, was dieses einfache Problem hergibt.