Eine der Aufgaben, bei denen es einfach ist, die richtige Lösung zu erraten, aber sehr schwierig, deren Richtigkeit zu beweisen.
Ich bin damals mit sehr viel Mühe auf einen formalen Beweis gekommen, dass 100 der Worst Case ist. Leider ist es nicht einfach, meine Notizen jetzt noch nachzuvollziehen und (hoffentlich verständlich) zusammenzufassen... Ich hoffe, das ergibt Sinn.
So weit ich mich an das Verfahren erinnere, rotieren alle im Code vorkommenden Zeichen zyklisch eins weiter durch den Code, bis sie ihren Platz gefunden haben, wobei bereits eingenommene Plätze übersprungen werden, während alle nicht vorkommenden Zeichen eliminiert werden. Ich habe deshalb den Code als Kreis betrachtet, bei dem die Enden zusammengefügt wurden und das letzte Zeichen auch "links" (gegen den Uhrzeigersinn) neben dem ersten steht.
Da es 99 falsche Zeichen gibt und 99 Chancen (jeweils nach den ersten 99 Runden), diese zu eliminieren, können in Runde 100 auf jeden Fall keine falschen Zeichen mehr vorhanden sein, sondern falls die versuchte Lösung dann immer noch falsch ist, ist sie eine Permutation der korrekten Lösung.
Angenommen, nach 100 Versuchen sind nicht alle Zeichen am richtigen Platz. Dann gibt es mindestens einen Zyklus aus n>1 Zeichen, die nach 100 Versuchen jeweils auf dem eigentlichen Platz des vorherigen Zeichens im Zyklus sind. Ich habe die Zeichen a_k genannt und deren korrekte Plätze p_k, für alle Zeichen im Zyklus ist also jeweils a_(k+1) auf dem Platz p_k (modulo n, also a_1 ist auf p_n).
Keine der Zeichen a_k sind schon in Runde 1 reingekommen, denn die ersten 100 Zeichen haben im Lauf der 100 Runden, wenn sie nicht schon vorher den korrekten Platz gefunden haben, alle 100 möglichen Plätze durchprobiert, sind also am Ende sicher am korrekten Platz.
Wenn a_k in Runde 2 reingekommen ist, dann hat es 99 mögliche Plätze durchprobiert, und da es am Ende falsch liegt, muss der richtige Platz p_k der einzige sein, auf dem a_k in den 99 Runden nie war - der Platz gleich links von dem, an dem a_k eingestiegen ist bzw gleich rechts von dem, an dem a_k geendet ist. Am Ende ist a_k auf p_(k-1), es ist also p_k - p_(k-1) = 1. (Modulo 100, also wenn z.B. p_k der erste Platz ist und p_k der hundertste, dann ist p_k - p_(k-1) für mich auch 1 und nicht -99, da ich den Code als Kreis betrachte.)
Nach dem gleichen Prinzip muss, wenn a_k in Runde 3 reingekommen ist, p_k einer der zwei Plätze (gleich rechts vom Endpunkt p_(k-1)) sein, die a_k in den 98 Runden verpasst hat, also p_k - p_(k-1) <= 2.
Generell: Wenn a_k in Runde r_k reingekommen ist, dann ist p_k - p_(k-1) <= r_k - 1.
Das gilt für alle n Zeichen im Zyklus, also gibt es n Ungleichungen
p_2 - p_1 <= r_2 - 1
...
p_1 - p_n <= r_1 - 1
Was passiert nun, wenn man alle dieser Ungleichungen addiert?
Eigentlich müssten sich dabei alle p_i und - p_i auf der linken Seite jeweils wegkürzen. Wegen meiner zyklischen Definition von p_k - p_(k-1) ist das aber nicht der Fall. p_k - p_(k-1) beschreibt ja, wie viele Schritte ich von p_(k-1) nach rechts gehen muss, um zu p_k zu kommen. Ich fange hier in der Summe also bei p_1 an, gehe p_2 - p_1 Schritte nach rechts zu p_2, dann nochmal p_3 - p_2 Schritte nach rechts zu p_3 (bei n>2), ..., und gehe am Ende nochmal p_1 - p_n Schritte von p_n nach rechts und komme wieder bei p_1 an. Das heißt, ich bin mindestens einmal im Kreis gelaufen, die Summe der linken Seite ist also ein positives Vielfaches von 100 (und damit mindestens 100.)
Damit gilt sum_(k=1)^n (r_k - 1) >= 100.
Aber was ist r_k bzw. r_k - 1 für ein gegebenes Zeichen a_k? Wenn a_k in Runde 2 reinkommt, dann heißt das, in dem Slot im Gesamtzyklus, den a_k in Runde 2 einnimmt, war vorher ein anderes Zeichen, das im Code nicht vorkam und eliminiert wurde. Wenn a_k erst in Runde 3 reinkommt, dann wurde im Slot von a_k vorher in Runde 2 ein Zeichen eliminiert, aber damit ein falsches Zeichen in Runde 2 überhaupt existiert hat, muss dieses auch erst in Runde 2 reingekommen sein für ein anderes Zeichen, das in Runde 1 eliminiert wurde, usw.
Wenn also a_k in Runde r_k reinkommt, dann waren vorher genau r_k-1 falsche (eliminierte) Zeichen im Slot im Gesamtzyklus, in den a_k eingesetzt wird und den es ab da bis zum Ende behält (auch wenn alle Slots jede Runde um eins weiter im Code rotieren), der sich also von den Slots aller anderen in Runde 100 vorkommenden Zeichen unterscheidet.
Die Summe sum_(k=1)^n (r_k - 1) ist also gerade die Anzahl der falschen Zeichen, die insgesamt zuvor in den Slots der Zeichen im "Zyklus der falschen Plätze" waren und eliminiert wurde. Wenn die Antwort nach Runde 100 immer noch falsch ist, wenn also so ein Zyklus existiert, dann muss diese Anzahl mindestens 100 sein. Es gibt aber insgesamt nur 99 falsche Zeichen und damit hat man den Widerspruch, der zeigt, dass das alles nicht sein kann und die Antwort spätestens nach Runde 100 richtig sein muss.
