© Friederike Hofmann, MATH+
Autoren: Hajo Broersma
Projekt: 4TU.AMI
Aufgabe
Um die Zeit an einem dunklen, regnerischen Tag vor Weihnachten zu vertreiben, nehmen die drei Zwerge Godric, Goliath und Gowan die Herausforderung an, die 18\times 18 Felder eines traditionellen Go-Bretts mit weißen und schwarzen Steinen auf eine künstlerische und optisch ansprechende Weise zu füllen. Um ihr Ziel zu erreichen, einigen sie sich darauf, die folgenden Grundbausteine für ihre Designs zu verwenden:
- Ziegel bestehen aus einer einfarbigen Kette, die genau eine Reihe breit ist. Diese Reihe ist von einem Rahmen der anderen Farbe umgeben. Die Notation k-Ziegel für k\ge 1 beschreibt einen Ziegel, dessen einfarbige Kette die Länge k hat.
- Kacheln bestehen aus einem einfarbigen Quadrat in der Mitte, das von einem Rahmen der anderen Farbe umgeben ist. Die Notation k-Kachel für \ge 1 beschreibt eine Kachel, deren mittleres einfarbiges Quadrat die Größe k\times k hat.
Beispielhaft sieht man einen weißen 1-Ziegel, einen weißen 2-Ziegel und einen schwarzen 4-Ziegel in Abbildung 1 links dargestellt. Entsprechend sind eine schwarze 1-Kachel, eine schwarze 2-Kachel und eine weiße 4-Kachel in Abbildung 1 rechts dargestellt.
1-Ziegel und 1-Kachel derselben Farbe sind also identisch.
Abbildung 1: Darstellung von Ziegeln und Kacheln. Links: Ein weißer 1-Ziegel, ein weißer 2-Ziegel und ein schwarzer 4-Ziegel. Rechts: Eine schwarze 1-Kachel, eine schwarze 2-Kachel und eine weiße 4-Kachel.
Die Herausforderung der drei Zwerge besteht darin, die Grundbausteine zu nutzen, um die 18\times 18 Felder eines traditionellen Go-Bretts mit weißen und schwarzen Steinen so zu füllen, dass:
- alle Felder bedeckt sind;
- die Gesamtanzahl der verwendeten weißen Steine gleich der Gesamtanzahl der verwendeten schwarzen Steine ist;
- Zwei verschiedene Grundbausteine mit gleicher Rahmenfarbe sich nicht berühren, sondern höchstens über Eck aneinander grenzen.
Abbildung 2 zeigt eine teilweise Abdeckung des Go-Bretts, die erlaubt ist (linke obere Ecke), und eine teilweise Abdeckung, die nicht erlaubt ist (rechte untere Ecke; die roten Punkte markieren einen Konflikt).
Abbildung 2: Eine erlaubte (oben links) und eine nicht erlaubte (unten rechts) Teilabdeckung
Die Zwerge versuchen nun, so viele Grundbausteine verschiedener Größen wie möglich zu verwenden. Die Anzahl der Grundbausteine verschiedener Größe bezeichnen sie als ästhetische Qualität. Die Farben werden für die Zählung ignoriert.
Als Beispiel: Die Teilabdeckung im oberen Teil von Abbildung 3 verwendet 1-Ziegel (1-Kacheln), 2-Ziegel, 2-Kacheln und keine weiteren Grundbausteine. Daher würde diese Teilabdeckung eines 7\times 14 Bretts eine Bewertung von 3 für die ästhetische Qualität erhalten.
Die drei Zwerge untersuchen verschiedene Strategien zur Gestaltung des Go-Bretts. Dabei gilt:
- Godric darf nur Ziegel verwenden.
- Goliath darf nur Kacheln verwenden
- Gowan darf eine Mischung aus beliebigen Ziegeln und Kacheln verwenden.
Jeder von ihnen versucht, die höchstmögliche Punktzahl für die ästhetische Qualität zu erreichen, wobei alle oben genannten Einschränkungen beachtet werden müssen.
Frage: Was sind die höchstmöglichen Punktzahlen von Godric, Goliath und Gowan?
Antwortmöglichkeiten
- Die höchsten Punktzahlen von Godric, Goliath und Gowan sind 3, 1 und 3.
- Die höchsten Punktzahlen von Godric, Goliath und Gowan sind 3, 1 und 4.
- Die höchsten Punktzahlen von Godric, Goliath und Gowan sind 3, 2 und 5.
- Die höchsten Punktzahlen von Godric, Goliath und Gowan sind 4, 1 und 4.
- Die höchsten Punktzahlen von Godric, Goliath und Gowan sind 4, 1 und 5.
- Die höchsten Punktzahlen von Godric, Goliath und Gowan sind 4, 2 und 6.
- Die höchsten Punktzahlen von Godric, Goliath und Gowan sind 5, 1 und 5.
- Die höchsten Punktzahlen von Godric, Goliath und Gowan sind 5, 2 und 5.
- Die höchsten Punktzahlen von Godric, Goliath und Gowan sind 5, 2 und 6.
- Keine der anderen Antwortmöglichkeiten ist richtig.