Daß ohne die Randbedingung die maximale Punktzahl P=17 ist, hat @hroptatyr ja schon gezeigt. Genau genommen ist das nicht richtig. denn wenn alle Mannschaften die gleiche Punktzahl haben (alle Spiele unentschieden → P=17) gibt es weder einen Ersten noch einen Letzten der Liste. Also lässt man nur einen Einzigen gegen einen anderen gewinnen, dann gibt es einen Ersten mit P=19 und einen Letzten mit P=16. Alle anderen haben P=17.
Um das Ergebnis mit der Randbedinung herauszufinden gibt es meinen Überlegungen nach keinen Algorithmus,mitdem esgleich auszurechnen wäre. Aber es gibt eine Prozedur, mit der man sich sukzessive an ein Resultat herantapsen kann. Diese Prozedur lösst sich auch einfach programmieren, aber der Aufwand ist größer, als es zu Fuß zu machen. Man muß die geeignete Ausgangstabelle wählen.
Die Ausgangstabelle mit „alle unentschieden“ (und dann sukzessive die P für den Letzten zu vermindern) erweist sich als zu kompliziert.
Ich habe folgende Ausgangtabelle gewählt:
Hier sind die P für alle Spiele aller Mnnschaften in einer Matrix angeordnet. Und zwar für die Ausgangssituation „alle Spiele werden gewonnen, es gibt kein unentschieden“, also für die maximale Punktzahl 459. Der Erste (Zeile 1) hat dann P = 17 · 3 = 51 Punkte, der Letzte (Zeile 18) hat als Einziger kein Spiel gewonnen, also P = 0. Die Punktsumme steht in der letzten Spalte der Matrix.
Zu einem Spiel Spieler A gegen Spieler B gehört dann das Punkepaar [Zeile A, Spalte B] und die Transponierte [Zeile B, Spalte A]. Also z.B.
Spieler 18 ↔ Spieler 1: [Zeile 18, Spalte 1] → P(18) = 0 und [Zeile 1, Spalte 18] → P(1) = 3…
Verändert man nun in [18, 1] P = 0 in P = 1, dann wird zugleich [1, 18] von P = 3 zu P = 1 (entsprehend Spiel ist unentschieden). Und die Punkesumme Σ in der letzten Spalte wird für Spieler 18 um 1 erhöht und für Spieler 1 um 2 vermindert.
Oder z.B.
Spieler 15 ↔ Spieler 3: [Zeile 15, Spalte 3] → P(15) = 0 und [Zeile 3, Spalte 15] → P(3) = 3
Verändert man nun in [15, 3] P = 0 in P = 1, dann wird zugleich [3, 15] von P = 3 zu P = 1 (entsprehend Spiel ist unentschieden). Und die Punkesumme Σ in der letzten Spalte wird für Spiler 15 um 1 erhöht und für Spieler 3 um 2 vermindert.
Die folgende Beschreibung der Prozedur liest sich leider etwas kompliziert, ist aber de facto ganz simpel. Man mius nur darauf achten, daß jedes [A,B] = 0 → 1 ein [B,A] = 3 → 1 zur Folge hat.
In der obigen Matrix fängt man nun an mit
[18, 1] = 0 → 1 … Σ(18) = 0 → 1 und zugleich [1, 18] = 3 → 1 … Σ(1) = 51 → 49
[18, 2] = 0 → 1 … Σ(18) = 1 → 2 und zugleich [2, 18] = 3 → 1 … Σ(2) = 48 → 46
[18, 3] = 0 → 1 … Σ(18) = 2 → 3 und zugleich [3, 18] = 3 → 1 … Σ(3) = 45 → 43
Da jetzt aber Σ(18)=3 genausso groß ist wie Σ(17)= 3, muß Σ(3) um 1 erhäht werden. Das geschieht, indem [17,1] = 0 → 1 und zugleich [1,17] = 3 → 1 und Σ(1) = 49 → 47.
Und so weiter. Mit zunehmender Punktzahl von 18 erhöhen sich so sukzessive bei jedem Schritt die Σ in der letzten Spalte jeweils um 1 von unten nach oben und zugleich vermindern sich die Σ von oben nach unten bei jedem Schritt um 2.
Die Prozedur ist zu Ende, wenn es nicht mehr möglich ist, die Σ einer Zeile von der darunterstehenden Σ unterschiedlich zu machen. Mein Ergebnis sieht man in folgender Matrix:
Die maximale Punktezahl des Letzten ist demnach P = 12.
Zu der Rangfolge
37 36 33 32 31 2 8 27 24 23 20 19 18 17 16 15 14 13 12 gibt es noch diese
37 34 35 32 31 2 8 27 24 23 20 19 17 18 16 15 14 13 12als Variante.
Aber bei P = 12 für den Letzten ist definitiv Schluss.
Gruß
Metapher
Sorry, daß die Scans ein wenig krumm geworden sind