Schöne Probleme der Informatik?

[Meniskusschaden]

Eine interessante Aufgabe ist auch das sogenannte Problem der stabilen Heirat.

n Frauen und n Männer stellen jeweils eine Liste der von ihnen bevorzugten Partner auf, wobei der absolute Wunschpartner ganz oben steht, dann der nächste usw..

Aus diesen Listen müssen jetzt n Ehepaare gebildet werden. Wenn dabei mindestens ein Mann und eine Frau nicht miteinander verheiratet sind, obwohl beide auf der Liste des jeweils anderen auf einer höheren Position stehen als der tatsächliche Ehepartner, ist die Lösung instabil.