8 Rettet die Geschenke!

© Zyanya Santuario, MATH+

Autor: Lukas Protz (MATH+)

Aufgabe

Als der Sicherheits-Elf bemerkte, was passiert war, war er entsetzt. Der Grinch hatte es geschafft, sich in den Tresorraum zu schleichen, in dem alle Weihnachtsgeschenke aufbewahrt werden. Nicht nur das – er hatte den Code zum Öffnen des Tresors geknackt, ihn verändert und so umprogrammiert, dass alles im Inneren zerstört wird, falls zu oft ein falscher Code eingegeben wird.

Der Sicherheits-Elf flehte den Grinch an, ihm den richtigen Code zu geben, doch der Grinch antwortete, bösartig lachend: „Schnapp dir 100 Elfen und bring sie zum Tresor. Wir werden ein kleines Spiel spielen und vielleicht könnt ihr eure Geschenke noch retten.”
Sofort folgte der Sicherheits-Elf den Anweisungen des Grinch und kehrte mit 100 Elfen zum Tresor zurück.

„Die Regeln sind folgende:”, sagt der Grinch. „Der Code für den Tresor besteht aus 100 verschiedenen Zeichen, die sich nicht wiederholen. Insgesamt gibt es 199 Zeichen, aus denen ihr auswählen könnt.”
Er zeigt auf ein Bedienfeld mit 199 Knöpfen, von denen jeder mit genau einem Zeichen beschriftet ist. „Außerdem gibt es einen Bildschirm, der den zuvor eingegebenen Code anzeigt. Er markiert Zeichen, die an der richtigen Position stehen grün, und Zeichen, die im Code vorkommen, aber an der falschen Stelle stehen blau.
Jeder von euch hat nur einen einzigen Versuch, den Tresor zu öffnen. Außerdem dürft ihr während des Spiels in keiner Weise miteinander kommunizieren. Um das Ganze noch etwas schwieriger zu machen, werde ich dafür sorgen, dass nur der Elf, der gerade an der Reihe ist, den Bildschirm sehen kann.
Während seines Zuges zeigt der Bildschirm lediglich die eingegebenen Zeichen an – ganz ohne Hinweise darauf, ob sie richtig oder falsch sind. Erst wenn alle 100 Zeichen eingegeben wurden und der Elf zurücktritt, wertet der Tresor den Versuch aus und der Bildschirm hebt die entsprechenden Zeichen hervor – sichtbar für den nächsten Elfen. Sobald der richtige Code eingegeben wird, öffnet sich der Tresor.
Wenn keiner von euch den richtigen Code eingibt, werden alle Geschenke automatisch zerstört. Ihr habt 10 Elfen-Minuten (die Standard-Zeiteinheit am Nordpol), um euch eine Strategie zu überlegen.”

Nach einigen Minuten des angestrengten Nachdenkens kommt ein Elf auf eine Idee: „Lasst uns eine Liste aller Zeichen machen. Der erste von uns probiert die ersten 100 Zeichen auf der Liste aus und bei jedem weiteren Versuch machen wir Folgendes:
Wenn ein Zeichen grün markiert wird, bleibt es an derselben Position.
Wenn ein Zeichen blau markiert wird, wird es an die nächste freie Position rechts davon im Code gesetzt. Dabei ist eine freie Position eine Position, an der bisher kein grün markiertes Zeichen steht.
Es kann passieren, dass ein blau markiertes Zeichen am Ende des Codes keine freie Position rechts von sich hat. In diesem Fall wird das Zeichen an die erste freie Position im Code gesetzt, von links beginnend.
Die übrigen Positionen werden mit den nächsten unbenutzten Zeichen aus der Liste gefüllt. Jedes dieser Zeichen kommt an die erste noch freie Position, wieder von links nach rechts.”

Da ihnen die Zeit davonläuft, einigen sich die Elfen auf diese Strategie und beginnen mit dem Spiel.

Hoffentlich können die Elfen ihre Geschenke retten! Sei m die minimale Anzahl an Elfen, die nötig wären, um sicherzustellen, dass die Elfen den Code mit ihrer Strategie knacken.
Welche Ziffer steht an der Einerstelle von m?

Antwortmöglichkeiten

1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 0