LogicWeekly » Archiv » Schleifen und Schlaufen

Logic-Weekly.de [Alles zeigen]

 
Rätsel [Alles zeigen]

 
Die Schulen [Alles zeigen]

 
Schleifen und Schlaufen
Adventskalender 2010 » Logik » Mathematik » Knobeln

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
Hier klicken um Lösung anzuzeigen

Rätselinfos
Schwierigkeitsstufe:
(35 von 100)
Eingestellt von:
Harrer Daniel (LMU München (Mathematisches Institut))  


Impressum Rätselsoftware: LogicWeekly Version 2.4 entwickelt von Christian Spitschka (© 2004-2018) Forensoftware: Burning Board, entwickelt von WoltLab GmbH