Das Kumite-Problem

Gelegentlich findet man Probleme im realen Leben, die man mithilfe von Algorithmen lösen kann. Ich habe ein solches gefunden: Das Kumite-Problem. Nach einer kurzen Problembeschreibung werde ich Lösungen anbieten und skizzieren, weshalb der Algorithmus korrekt ist. Sollte jemand Fehler finden oder Fragen haben: Ich bin für Feedback aller Art offen.

Trainiert man Kumite (Partnerkampf) in einer größeren Gruppe, möchte man mit allen kämpfen. Um dieses zu ermöglichen und dabei genügend Komfort zu bieten, ist ein einfacher Algorithmus notwendig, der kaum oder keine Einmischungen von außen benötigt. Bisher wurde es meist so gehandhabt, dass jeder sich um eine Position gegen den Uhrzeigersinn weiterbewegt, wie folgendes Beispiel illustriert, wobei eine Ziffer einem Kämpfer entspricht:

Die untereinander stehenden Ziffern kämpfen jeweils miteinander, wobei die Reihenfolge der Partner irrelevant ist, d.h. x vs. y ist äquivalent zu y vs. x. Bei genauerm Hinsehen bemerkt man, dass z.B. die 1 nie mit der 4 kämpft und dies nach dem Algorithmus nie tun wird, da man nach viermaligem Ausführen bei den ursprünglichen Paarungen endet. Ein anderer Fall tritt ein, wenn die Gruppe aus einer ungeraden Anzahl von Kämpfern besteht. Sei n, die Anzahl der Gruppenmitglieder, gleich 5, dann ergibt sich folgender Ablauf.

Nach fünfmaligen Ausführen des Algorithmus gelangt man zu den ursprünglichen Begegnungen, wobei jeder mit jedem gekämpft hat. Überträgt man diesen Fall auf diejenigen Fälle, in denen n gerade ist, ändert man den Algorithmus leicht ab: Ein einziger Kämpfer, der sich in einer Ecke der Anordnung befindet, bleibt immer auf seiner Position, er befindet sich an der sog. Fixposition. Im Fall für ungerade n entspricht dieser Kämpfer dem nicht-existierenden Kämpfer, womit sich beide Fälle auf einen Fall reduzieren lassen. Nachfolgend nochmal das Beispiel für n = 4 und der Annahme, dass sich die Fixposition unten rechts befindet, mit dem modifizierten Algorithmus:

Offensichtlich hat jeder mit jedem gekämpft und nach drei Schritten erhält man die ursprüngliche Anordnung.

Um ein Gefühl dafür zu geben, weshalb der Algorithmus korrekt ist, werde ich den Beweis skizzieren. Es ist dabei irrelevant, in welcher Ecke sich die Fixposition befindet, da man jede Anordnung in andere Anordnungen umformen kann, in denen sich die Fixposition an einer anderen Stelle befindet.
Der Begriff "Schritt" wird mit der Ausführung des Algorithmus gleichgesetzt, d.h. zwei Schritte entspricht drei Anordnungen (Ursprungsanordnung und den beiden Ergebnissen der Ausführung).
Außerdem ist es wesentlich, dass man nach n-1 Schritten zur ursprünglichen Anordnung gelangt. Dass dies stimmt, lässt sich leicht überprüfen: Jeder Kämpfer, der nicht auf der Fixposition steht, legt n-2-mal genau eine Position und einmal genau zwei Positionen (beim Überspringen der Fixposition) zurück, dadurch bewegt sich jeder dieser Kämpfer um genau n Schritte und steht nach n-1-maligem Ausführen auf seiner ursprünglichen Position. Der Kämpfer auf der Fixposition bleibt lt. Definition immer auf seiner Position, womit obige Aussage bewiesen wäre.
Da man nach n-1 Schritten zur Ursprungsanordnung gelangt, genügt es zu zeigen, dass innerhalb von n-1 Schritten keine Paarung mehrfach gewählt wurde. Denn würde eine Paarung mehrfach auftauchen, könnte ein Partner nicht alle anderen Partner gewählt haben, da es n-1 andere Kämpfer gibt und man bei jedem Schritt nur einen Partner wählen kann. Beim Kämpfer auf der Fixposition ist dies offensichtlich, denn jeder Kämpfer betritt jedes Feld (bis auf die Fixposition) genau einmal. Dass dieser Fall nicht für die restlichen Kämpfer eintritt, lässt sich indirekt beweisen: Angenommen, es gibt eine Paarung, die sich innerhalb von n-1 Schritten wiederholt. Da sich die Reihenfolge der (sich bewegenden) Kämpfer nicht ändert, müssen die Partner die Seiten wechseln, sodass derjenige, der beim ersten Treffen in der oberen Reihe stand, nun in der unteren steht und vice versa. Da sich die Fixposition auf einer Ecke befindet, legt genau ein Partner einen Schritt mehr zurück als der andere. Dieser Schritt wird erst ausgeglichen, wenn der zurückliegende Partner auch diese Ecke überspringt. Dies passiert allerdings erst nach n Schritten, also nach n-maligem Ausführen des Algorithmus. Damit ist die Annahme widerlegt und die Behauptung bewiesen. Übrigens folgt aus dieser Argumentation die Bedingung, dass sich eine Fixposition auf einer Ecke befinden muss. Ein Gegenbeispiel lässt sich sehr leicht konstruieren (n=6 und Fixposition 2):

Die Begenung 1 gegen 4 taucht in diesem Beispiel zweimal auf.

Kommentare