Das „Krawattenrätsel” ist ein mathematisches Problem, das bisher noch niemand gelöst hat, das grundsätzlich aber durchaus als lösbar angesehen wird.

Kurz gesagt wird eine optimale Lösung für folgendes Sortierproblem gesucht:

n Fächer stehen in einer Reihe, das i-te Fach enthält zwei Bälle, die beide mit der Zahl n+1−i beschriftet sind. Ein Zug besteht darin, dass Sie zwei Bälle aus benachbarten Fächern vertauschen. Wie viele Züge sind nötig, bis jeder Ball in dem Fach liegt, das seine Nummer trägt?

Gesucht ist die exakte minimal erforderliche Anzahl von Tauschvorgängen in Abhängigkeit von n und ein Beweis dafür.

Weitere Informationen zur Einsendung gibt es auf der Homepage des Spektrum-Verlages.

Wir wünschen viel Spaß beim Knobeln.

(fm)

Zur Übersicht