© Vira Raichenko, MATH+
Autor: Wouter Fokkema (4TU.AMI)
Aufgabe
Der Weihnachtsmann hat zu wenig Platz, um all seine Geschenke zu lagern! Glücklicherweise hat er einen alten Keller gefunden, der noch etwas Platz hat. Der Keller ist in Felder unterteilt. Eine Draufsicht des Kellers ist unten dargestellt. Der Weihnachtsmann möchte so viele Geschenke wie möglich in diesem Keller lagern.
Abbildung 1: Das Layout des Kellers des Weihnachtsmanns. Das Kreuz in der Mitte der untersten Reihe markiert den Eingang. Alle anderen Kreuze markieren Stellen, an denen die Decke undicht ist.
Allerdings gibt es einige Regeln:
- Ein Geschenk belegt genau 1 Feld.
- Es dürfen keine Geschenke am Eingang und an Stellen platziert werden, an denen die Decke undicht ist; diese Felder sind mit einem Kreuz markiert.
- 2 Geschenke dürfen nicht in horizontal oder vertikal benachbarten Feldern sein. (Das liegt daran, dass alle Geschenke ähnlich aussehen und Geschenke, die direkt nebeneinander liegen, leicht verwechselt werden können.)
- Am Eingang des Kellers beginnend muss es möglich sein, jedes Feld ohne ein Geschenk zu besuchen, indem man horizontal und vertikal durch Felder ohne Geschenke geht. Mit anderen Worten müssen die Felder ohne Geschenke (einschließlich der Felder mit einem Kreuz) einen Bereich von Feldern bilden, der orthogonal verbunden ist. (Dies ist wichtig, da die Geschenke regelmäßig inspiziert werden müssen. Daher wäre es zusätzliche Arbeit, sie zu bewegen.)
Santa benötigt deine Hilfe, um die maximale Anzahl der Geschenke zu bestimmen, die in den Keller passen. Was ist diese maximale Anzahl?
Antwortmöglichkeiten
- Elf Geschenke
- Zwölf Geschenke
- Dreizehn Geschenke
- Vierzehn Geschenke
- Fünfzehn Geschenke
- Sechzehn Geschenke
- Siebzehn Geschenke
- Achtzehn Geschenke
- Neunzehn Geschenke
- Zwanzig Geschenke