18 Lösung / Solution

[Estela]

Teilt hier gerne eure Lösung zu Aufgabe 18 

---

Feel free to share your solution to challenge 18 

[Abraxas]

Ich komme durch Probieren auf maximal 28 Tannenbäume, also Lösung 8. Es gibt mehrere Möglichkeiten, wie sie platziert werden können, darunter auch die eine, die man nicht so gerne posten möchte…

[st1974]

Mein Optimum ist Antwort 8: 28 Tannenbäume.
Zugegeben, ich habe keinen Beweis für die Optimalität. Ich bin stattdessen mit einem Brute-Force-Algorithmus alle Möglichkeiten durchgegangen, bei denen ich jedoch eine Symmetrieachse voraussetzen musste.

[MatheJuergen]

Ich bin auf insgesamt 28 Bäume gekommen. Am Beispiel 5 X 5 sieht man sehr schön, dass man die Ecken eigentlich gar nicht beachten muss, denn man könnte den jeweiligen Baum einfach auf das "den Baum versorgende" Wasserfeld setzen, wodurch sich die Anzahl der Bäume nicht verändert. Oder anders gesprochen, will man die Ecken besetzen muss man ein Feld für Wasser "opfern" das man auch mit einem Baum bepflanzen könnte.    
Dann hab ich eine Weile gezeichnet und mich langsam auf 28 gesteigert, mehr habe ich allerdings nicht untergebracht. 

[Tim.S]

Mein Optimum ist Antwort 8: 28 Tannenbäume.
Zugegeben, ich habe keinen Beweis für die Optimalität. Ich bin stattdessen mit einem Brute-Force-Algorithmus alle Möglichkeiten durchgegangen, bei denen ich jedoch eine Symmetrieachse voraussetzen musste.

Ich habe es auch mit einem Brute-Force Algorithmus gelöst, allerdings habe ich keine Symmetrieachse vorrausgesetzt. Auch meine Lösung ist 28 also Antwort 8.

[Raaadi]

Nach nur 2^48 möglichen Belegungen mit Bs und Ws steht spätestens die Antwort fest. ChatGPT wollte diese für mich nicht alle auflisten / auswerten, also bin ich durch manuelles hin und her auch auf 28 gekommen. Am „ordentlichsten“ finde ich dabei: 

BBBBBBB 
wwwwwww
BBBwBBB
BwwwwwB
BBBwBBB 
wwwwwww
BBBBBBB

[PhiSigma]

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:


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.)


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.

[ThH]

Auf die elegante Lösung bin ich auch gespannt. Ich denke auch, dass mindestens 21 Wasserfelder benötigt werden.
Das Skelett einer Beweisskizze, dem ich letztendlich vertraut habe, sieht sehr sehr grob in etwa folgendermaßen aus:

- In der Nähe jeder Ecke braucht es mindestens zwei Wasserfelder (In Schach-Notation für die linke untere Ecke etwa auf A2 und B2)
- In der Mitte jeder Kante, aber nicht direkt am Rand muss ein Wasserfeld sein, z.B. auf D2
- Die Aufgabenstellung erfordert in der Mitte des Raumes ein Wasserfeld
Das sind nun mindestens 13 Wasserfelder in 9 nicht-zusammenhängenden Komponenten.

Es scheint mir (wäre auch noch weiter auszuarbeiten), dass jedes weitere Wasserfeld nur zwei dieser Komponenten verbinden kann,
also die Zahl der Komponenten nur um eins vermindert. Somit sind weitere acht Wasserfelder nötig; macht zusammen 21.

Witzig finde ich, dass man einen Baum mehr pflanzen könnte, wenn man das Wasserbecken aus der Mitte heraus verschieben dürfte.

Für diesen  Fall, ohne erzwungene Wasserfelder und beliebig große Rechtecke gibt es in einem Preprint von 2021
(Connected domination in grid graphs von Masahisa Goto und Koji M. Kobayashi, Theorem 1.1) eine allgemeine Formel, 
die für den 7x7-Raum tatsächlich 20 Wasserfelder als Minimum liefert.

Von denen, die mit Brute-Force bessere Lösungen ausgeschlossen haben, würde mich interessieren, was für Algorithmen (Back-tracking,...?), wie viele Möglichkeiten
in welcher Zeit abgesucht haben, und wie viele optimale Lösungen (nach Symmetrie aufgeschlüsselt) es gibt.

[PhiSigma]

Ich habe Schritt für Schritt eine Zeile hinzugefügt und dabei immer die Möglichkeiten aussortiert, die nicht mehr gültig sein können (d.h. selbst wenn man unten eine Zeile nur mit Wasser hinzufügt, ist das Wasser unzusammenhängend und/oder nicht alle Felder sind bewässert) oder nicht mehr unter 21 Wasserfelder benutzen können (da die ersten (und damit auch die letzten) 2 bzw. 3 Zeilen mindestens 5 bzw. 8 Wasserfelder brauchen, dürfen die ersten 5 bzw. 4 Zeilen maximal 16 bzw. 13 Wasserfelder enthalten.) Wie lange es gedauert hat, weiß ich nicht mehr, aber ich würde mal schätzen, die reine Rechenzeit, nachdem der Code gestimmt hat, dürfte so etwa eine halbe Stunde gewesen sein.
Dabei komme ich auf 37216 Lösungen mit 21 Wasserfeldern und 800 mit 20. Wenn ich nur die betrachte, die ein Wasserfeld in der Mitte haben, bleiben 7088 mit 21 Wasserfeldern übrig und keine mit 20. Wenn man Symmetrien herausfiltert, bleiben 904 von 7088 Lösungen übrig, davon sind 869 asymmetrisch, 16 sind einfach achsensymmetrisch, 17 sind rotationssymmetrisch, eine ist doppelt achsensymmetrisch und eine ist um 90° rotationssymmetrisch.
Hier ein Bild von allen* Lösungen, nach Symmetrie geordnet, sodass die symmetrischen Lösungen in der untersten Zeile sind:

* 41*22=902 ging beinahe auf, also habe ich die letzten zwei Lösungen weggelassen, da ich die doppelt achsensymmetrische Lösung schon im vorherigen Beitrag als Beispiel-Lösung gezeigt habe und die um 90° rotationssymmetrische Lösung eventuell rechtliche Probleme verursachen könnte.

[mbert]

Mein Algorithmus hat in einer Stunde 790714001 normalisierte Konfigurationen mit 28 Bäumen ermittelt. Davon sind 904 gültig. Die Wasserwege werden ausgehend von der Mitte schrittweise erweitert. In jeder Iteration wird ein Wasserfeld an alle möglichen Positionen aller Vorgänger angefügt und das Ergebnis normalisiert in eine Hashtabelle eingetragen.