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