04 Geschenkeversand

© Till Hausdorf, MATH+

Autor*in: Clara Stegehuis (Universiteit Twente)
Projekt: European Women in Mathematics – The Netherlands (EWM-NL)

Aufgabe

Ada Lovelace war eine der ersten Informatikerinnen und ist eine alte Freundin des Weihnachtsmanns. Sie war auch eine der Ersten, die erkannte, dass Computer nicht nur schwierige Gleichungen lösen und Zahlen approximieren können, sondern auch zur Implementierung von Algorithmen verwendet werden können. Nun braucht der Weihnachtsmann Adas Hilfe, um einen Algorithmus für die folgende schwierige Aufgabe zu entwickeln.

Der Weihnachtsmann verpackt und verschickt Geschenke, die in einer endlichen Reihe in seinem Lagerraum liegen. Die Geschenke können nur verschickt werden, wenn sie ordentlich verpackt sind (P). Bei einigen Geschenken ist jedoch das Verpackungsmaterial beschädigt (D).

Wenn der Weihnachtsmann ein ordentlich verpacktes Geschenk verschickt, ändern die benachbarten Geschenke ihren Status:

• P→D: Wenn das Geschenk ordentlich verpackt war, schafft es der Weihnachtsmann – tollpatschig, wie er nun einmal ist – dies zu beschädigen.
• D→P: Wenn das Geschenk beschädigt war, dann reparieren es die Weihnachtswichtel, die dem Weihnachtsmann immer zur Seite stehen, sodass es anschließend wieder ordentlich verpackt ist.

Die Geschenke werden eines nach dem anderen verschickt. Sobald ein Geschenk verschickt wurde, hinterlässt es eine Lücke in der Reihe, wodurch zwei kürzere Reihen entstehen. Die Geschenke, die rechts und links der Lücke liegen, werden nicht als nebeneinanderliegend betrachtet. Die ersten beiden Sendungen des gestrigen Tages sind unten abgebildet:

Die Anfangsreihe im Beispiel besteht aus sieben Geschenken. Im ersten Schritt wird das 4. Geschenk (in rot) gesendet. Daher ändert sich der Status der beiden benachbarten Pakete (in blau) von D nach P bzw. P nach D. Im zweiten Schritt wird das 3. Paket (wieder in rot) versendet. Da es nur einen Nachbarn (wieder in blau) hat, wird nur der Status dieses Nachbarn von P nach D geändert.

Der Weihnachtsmann möchte natürlich alle Pakete einer beliebigen Reihe verschicken, d. h. er möchte, dass der obige Prozess für eine beliebige Reihe von Geschenken mit einer leeren Reihe endet. Obwohl der Weihnachtsmann die Reihenfolge, in der er die Geschenke verschickt, frei wählen kann, bleibt er manchmal nur auf beschädigten Geschenken sitzen (die er nicht verschicken kann). Der Weihnachtsmann glaubt, dass seine Freundin Ada Lovelace in der Lage ist, einen Algorithmus zu entwickeln, der sein Versandproblem löst.

Für welche Anfangsreihen von Geschenken gibt es einen Versandalgorithmus, der mit einer leeren Reihe endet?

Antwortmöglichkeiten:

1. Für jede Anfangsreihe von Geschenken, die mindestens ein ordentlich verpacktes Geschenk enthält.
2. Für jede Anfangsreihe von Geschenken, die mindestens ein ordentlich verpacktes Geschenk enthält, und bei der ordentlich verpackte Geschenke nur neben beschädigten liegen.
3. Für jede Anfangsreihe von Geschenken, die mindestens ein ordentlich verpacktes Geschenk enthält, und bei der beschädigte Geschenke nur neben ordentlich verpackten liegen.
4. Für jede Anfangsreihe von Geschenken mit einer ungeraden Anzahl von ordentlich verpackten Geschenken.
5. Für jede Anfangsreihe von Geschenken, die mindestens ein ordentlich verpacktes Geschenk sowie eine ungerade Anzahl beschädigter Geschenke enthält.
6. Für jede Anfangsreihe von Geschenken mit einer ungeraden Anzahl von Geschenken und mindestens einem ordentlich verpackten Geschenk.
7. Für jede Anfangsreihe von Geschenken mit einer geraden Anzahl von ordentlich verpackten Geschenken.
8. Für jede Anfangsreihe von Geschenken mit mindestens drei nebeneinanderliegenden, ordentlich verpackten Geschenken.
9. Für jede Anfangsreihe von Geschenken mit ordentlich verpackten Geschenken an beiden Enden dieser Reihe.
10. Für jede Anfangsreihe von Geschenken, die mindestens ein ordentlich verpacktes Geschenk enthält und bei der mindestens drei beschädigte Geschenke nebeneinander liegen.

Sonntagsbonus: Für diese Aufgabe gibt es eine Zeitgutschrift von 24 Stunden.

Projektbezug:

EWM-NL ist der nationale Verband der Frauen, die im Bereich Mathematik in den Niederlanden arbeiten. EWM-NL wurde 2013 gegründet und hat mehrere hundert Mitglieder aus dem akademischen Bereich, der Industrie und der Gesellschaft im Allgemeinen. EWM-NL organisiert mehrere Veranstaltungen pro Jahr, die in der Regel allen offen stehen, bietet Stipendien zur Karriereförderung an und unterhält ein Mentorennetzwerk.