|
Die neuen Roboterwichtel des Weihnachtsmannes haben eine sehr seltsame Programmiersprache: Jede Arbeitsanweisung besteht aus einer endlichen Abfolge der Buchstaben a, A, b, B, c und C. Zum Beispiel wäre "aaBcAbc" eine solche Arbeitsanweisung.
Ein Roboter wendet nun solange wie möglich folgende Regel, gegebenenfalls also mehrmals, an: Stehen ein Klein- und ein Großbuchstabe der selben Art (wie zum Beispiel a und A) nebeneinander (egal, wo in der Anweisung, und egal, in welcher Abfolge), so entfernt er beide aus der Anweisung. Auch hierzu ein Beispiel: Gibt man ihm die Anweisung "cBaAbbC", so streicht er zuerst aA und gelangt zu "cBbbC". Anschließend streicht er Bb und gelangt zu "cbC", welches sich nicht weiter verkürzt.
Der Emotionschip der Roboter findet jene Wörter toll, sie sich dabei komplett auslöschen, wie etwa das Wort "caAbBC", welches sich erst zu "cbBC", dann zu "cC" und schließlich komplett wegkürzt.
Der Weihnachtsmann möchte sie nun zur Verschnürung der Geschenke einsetzen. Damit sie dies korrekt tun, muss er eine Arbeitsanweisung X finden, die den folgenden vier Bedingungen gehorcht:
- Die Roboter finden X nicht toll, es kürzen sich also nicht alle Buchstaben weg.
- Entfernt man alle Vorkommen der Buchstaben a und A, so finden sie die Anweisung toll.
- Entfernt man alle Vorkommen der Buchstaben b und B, so finden sie die Anweisung toll.
- Entfernt man alle Vorkommen der Buchstaben c und C, so finden sie die Anweisung toll.
Ein Beispielanweisung, dass die ersten drei Bedingungen aber nicht die vierte erfüllt: "abAB" (In der Tat: streicht man alle a's und A's weg, so verbleibt die tolle Anweisung "bB"; streicht man alle b's und B's, so wird "abAB" zu "aA").
Eure Aufgabe ist es nun, ihm eine solche Arbeitsanweisung zu verraten. Eine Begründung oder Herleitung ist nicht verlangt.
Zusatzaufgabe zum Nachdenken (die Lösung dieser Zusatzfrage gibt keinerlei Punkte oder ähnliches): Gibt es solche Anweisungen auch für beliebig viele Buchstaben (d, D, e, E, ...)? Es soll sich also bei Entfernen aller Buchstaben des selben Typs immer ein tolles Wort ergeben.
| Lösung |
Eine gültige Lösung wäre zum Beispiel "abABcbaBAC" (wie man direkt nachprüft), es gibt aber einige weitere.
Die Frage hat, wie der Titel schon angedeutet hatte, mit Schlaufen und Schleifen zu tun. Genauer ist es die algebraische Variante der folgenden Frage:
Kann man ein Bild (das heißt: ein Gewicht an einer Schlaufe) an 2 (3, 4, ...) Nägeln derartig aufhängen, dass gilt:
- Das Bild fällt anfangs nicht herunter.
- Sobald man irgendeinen beliebigen Nagel aus der Wand herauszieht, stürzt es zu Boden.
Es soll also nicht nur herunterfallen, wenn man einen bestimmten Nagel zieht, sondern egal welchen man zieht.
Man deutet die Buchstaben dann so: a = lege die Schur im Uhrzeigersinn um den ersten Nagel. A = lege die Schur gegen den Uhrzeigersinn um den ersten Nagel. b = lege die Schur im Uhrzeigersinn um den zweiten Nagel. B = lege die Schur gegen den Uhrzeigersinn um den zweiten Nagel. u.s.w. Hier ein Bild von "abAB", wer mag möge sich selbst vergewissern, dass das rote Gewicht herunterfällt, sobald man auch nur irgendeinen der grauen Nägel entfernt. Zum Nachbauen empfohlen ;-)  Mit drei Nägeln gäbe es dann obiges "abABcbaBAC", welches zu Zeichnen aber schon recht mühselig ist. Eine Lösung für vier oder mehr Nägel möchte ich noch nicht sofort verraten, existiert aber.
Lösung ausblenden |
|
|
