Lösbarkeit des Neun-Punkte-Problems
(Un-) Lösbarkeit nachweisen
Um Aussagen über die (Un-) Lösbarkeit eines Problems zu ermöglichen, muss man in der Regel genaue Vereinbarungen über die erlaubten Operationen treffen.
Wir haben gesehen, dass das Neun-Punkte-Problem lösbar ist, wenn man Streckenzüge zulässt, die das vorgegebene Punktegitter verlassen.
Wir verschärfen jetzt die Anforderungen an die erlaubten Operationen und betrachten im Folgenden ausschließlich Streckenzüge mit den folgenden Eigenschaften:
Der Streckenzug besteht aus aneinandergefügten Strecken, deren Anfangs- und Endpunkte jeweils Punkte (ohne Ausdehnung) des vorgegebenen Punktegitters sind. Mittelpunkte der Strecken können dabei ebenfalls Punkte des vorgegebenen Punktegitters sein. Wir nennen solche Streckenzüge "gitterbasiert".
Die Abbildung zeigt zwei gitterbasierte Streckenzüge bestehend jeweils aus vier Strecken,
(ADG)(GHI)(IFC)(CE)
und
(AE)(EC)(CFI)(ID).
Das zu klärende Problem lautet jetzt: Gibt es einen gitterbasierten Streckenzug mit 4 Teilstrecken, der alle 9 Punkte des vorgegebenen Punktegitters umfasst?
Wir können jetzt wie folgt argumentieren: Wenn alle 9 Punkte in einem gitterbasierten Streckenzug vorkommen sollen, dann muss dieser Streckenzug aus 4 Teilstrecken bestehen, die alle jeweils 3 Punkte des Gitters erfassen (beachte, dass es 3 Nahtstellen geben muss und 4*3-3 = 9). Es gibt insgesamt 8 Strecken mit 3 Gitterpunkten: (ADG), (BEH), (CFI), (ABC), (DEF), (GHI), (AEI), (CEG). Jetzt kann man (mit etwas Fleiß) alle Fälle durchspielen. Dabei zeigt sich, dass man einen Streckenzug mit 3 aneinanderhängenden Strecken (mit jeweils 3 Gitterpunkten) nicht mit einer der vorgegebenen 8 Strecken fortsetzen kann.
Bemerkungen zur Vorgehensweise
Der Nachweis, dass das Problem unlösbar ist, kann nur dann argumentativ erfolgen, wenn die zur Lösung einsetzbaren Mittel präzisiert werden. Im Fall des Neun-Punkte-Problems wurde hierzu zunächst der Begriff "gitterbasierter Streckenzug" geklärt. Mit Hilfe dieses Begriffes konnte dann die Unlösbarkeit bzgl. der vorgenommenen Präzisierung begründet werden.
