Intuitiv habe ich schnell eine Anordnung mit 21 Wasserfeldern und 28 Tannenbäumen gefunden. Dass es nicht besser geht, konnte ich am Abgabetag aber nur durch stundenlange Brute Force mit dem Computer verifizieren, die (bis vielleicht auf Symmetrie) alle Lösungen mit höchstens 21 Wasserfeldern generieren sollte und dabei tausende mit 21 und keine einzige mit weniger gefunden hat. (Dass es so viele optimale Lösungen gibt, passt dazu, dass es einfach ist, eine von ihnen intuitiv zu finden.)
Natürlich ist Brute Force eine gültige Beweismethode, die auch schon bei bekannten Problemen der Mathematik benutzt wurde, aber da mich das hier dem Verständnis des Problems keine Schritt weitergebracht hat, wollte ich mich damit nicht zufrieden geben.
Nach einigen Tagen intensiver Arbeit habe ich endlich auch per Hand einen Beweis gefunden.
In meinen Notizen sind Wasserfelder blau und Felder mit Tannenbäumen rot, da ich den Kontrast stärker finde als zwischen blau und grün. Vielleicht wurden die Bäume passend zum Gewand des Weihnachtsmannes geschmückt.
Sei eine gültige Anordnung so definiert, dass alle blauen Felder orthogonal miteinander verbunden sind, alle roten Felder orthogonal an mindestens ein blaues Feld grenzen und das mittlere Feld blau ist.
Dann lässt sich jede gültige Anordnung mit n blauen Feldern in eine gültige Anordnung mit höchstens n blauen Feldern überführen, die genau vier blaue Felder am Rand hat (es wird für die Gültigkeit generell mindestens ein blauer Nachbar für jedes der vier Eckfelder benötigt.)
Das kann man erreichen, indem man Schritt für Schritt alle blauen Randfelder außer den vier Pflichtfeldern auf Felder im Inneren verschiebt, ohne dabei die Gültigkeit zu verletzen (um das sicherzustellen, können abhängig von der gegebenen Anordnung gleichzeitig auch weitere blaue Felder verschoben werden, aber nie vom Inneren an den Rand.)
Ich habe dabei für jede gültige Anordnung mit überschüssigen Randfeldern solche Verschiebungen gefunden, wobei erst die blauen Eckfelder entfernt werden, dann doppelte blaue Nachbarn der Ecken, dann "dritte Randfelder" (solche in den dritten und fünften Zeilen und Spalten) und schließlich die mittleren Randfelder (in der vierten Zeile und Spalte.)
Wenn man überprüfen möchte, dass die Verschiebungen die Gültigkeit nicht verletzen, ist es nützlich, sich zu überlegen, dass der einzige Schaden, den eine Verschiebung bei einer zuvor gültigen Anordnung anrichten kann, ist, dass das verschobene Feld an seinem ursprünglichen Ort eine wichtige Funktion für seine benachbarten Felder erfüllt hat (als einziger blauer Nachbar für ein benachbartes rotes Feld und/oder als einzige Verbindung zwischen mehreren benachbarten blauen Feldern), die nun nicht mehr erfüllt wird. Wenn alle diese Funktionen nach der Verschiebung weiterhin erfüllt werden, sei es durch das verschobene Feld an seinem neuen Ort oder durch andere Felder, ist die Gültigkeit weiter gegeben. So erkennt man zum Beispiel, dass ein blaues Feld in der Ecke gefahrlos diagonal ins Innere geschoben werden kann, da es dabei den Einfluss auf seine zwei vorherigen Nachbarn behält. Ähnliches gilt auch an anderen Stellen, wenn ein blaues Feld nur für zwei nicht gegenüberliegende Nachbarfelder relevant ist.
Alle nötigen Verschiebungsmuster habe ich in einem Bild gesammelt:
![[Bild: V8C9gtd.png]](https://imgur.com/V8C9gtd.png)
Das bedeutet, wenn m die Mindestanzahl an blauen Feldern für eine gültige Anordnung ist, dann gibt es eine gültige Anordnung, die genau 4 blaue Randfelder hat und mit m blauen Feldern auskommt.
Wenn man nun versucht, eine gültige Anordnung mit nur 4 blauen Randfeldern zu konstruieren, wird schnell klar, dass dafür 21 blaue Felder notwendig (und ausreichend) sind - es werden direkt 17 blaue Felder erzwungen und dann bleiben 5 getrennte Gebiete, die man mit mindestens 4 blauen Feldern verbinden muss (und kann.)
![[Bild: blC4Ihq.png]](https://imgur.com/blC4Ihq.png)
Damit ist das optimale Ergebnis also: 21 Wasserfelder und 28 Tannenbäume.
Dieser Beweis ist mir von allen Aufgaben am Schwersten gefallen, auch wenn die richtige Antwort leicht zu erraten war. Ich bin auf einfachere Beweise gespannt, die ohne so viele Fallunterscheidungen auskommen.
