Zeige: Es ist nicht möglich, einen Springer auf einem 4 × 4-Schachbrett so zu ziehen, dass jedes Feld genau einmal besucht wird.?
Hey ich verzweifle gerade wirklich an dieser Beweisaufgabe,es handelt sich dabei nicht um das klassische Springerproblem und wir befinden uns im Rahmen der Graphentheorie,wenn ihr aber andere Beweise (vllt kombinatorischer Art oder so) habt immer her damit, weil ich komm wirklich nicht darauf und verboten ist es ja nicht,etwas auf andere Art zu beweisen, als es erwartet wird.
5 Antworten
Der Beweis ist simpel - ähnlich dem des Königsberger Brückenproblems (Leonard Euler 1736).
https://de.wikipedia.org/wiki/K%C3%B6nigsberger_Br%C3%BCckenproblem
Male ein 4x4 Schachbrett auf und schreibe in jedes Feld die Anzahl der Felder hinein, die man mit einem einzelnen Springerzug von diesem Feld aus erreichen kann:
2 3 3 2
3 2 2 3
3 2 2 3
2 3 3 2
Damit ein Springer alle Felder in einer Folge von Zügen genau einmal erreichen kann, müssen alle Felder eine gerade Anzahl enthalten - bis auf zwei (Start und Ende).
Hier aber haben wir 8 Felder mit einer ungeraden Zahl.
Eine schöne Woche noch. :-)
Ich bin ein mathematischer Volldepp, aber diese Begründung kann ich verstehen. Danke! :-)
inwiefern nicht geführt,kannst du etwas konkreter werden?
Ok! Stimmt es eigentlich, dass der Springer nur mit einer geraden Anzahl von Zügen wieder zum Anfangspunkt zurückkehren kann, mit einer ungeraden Anzahl, egal wieviele es sind, dies nicht möglich ist?
Das ändert zwar an deiner Argumentation nichts, aber von den mittleren 2 Feldern kann man jeweils 4 Felder erreichen, nicht 2.
Dieser Beweis ist falsch. Er gilt für einen Eulerpfad, verlangt ist jedoch ein Hamiltonpfad - der Vergleich mit dem Königsberger Brückenproblem ist daher ungeeignet. Beim Königsberger Brückenproblem muss jede Kante einmal besucht werden, hier hingegen muss jeder Knoten einmal besucht werden.
Hier ein Gegenbeispiel für deinen Beweis:
Ein Graph mit 4 Knoten. Jeder Knoten ist mit jedem anderen Knoten verbunden. Das heißt, alle Knoten haben 3 adjazente Knoten. Offensichtlich existiert aber ein Hamiltonpfad.
Ahh jetzt seh ichs du hast recht,ich hatte auch diesen Denkfehler. Gelten für HamiltonPFADE denn diesselben Kriterien wie für Hamiltonkreise ? Und welches Kriterium würde sich dann hier anbieten deiner Meinung nach ?
Wikipedia: Im Gegensatz zum leicht lösbaren Eulerkreisproblem, bei dem alle Kanten genau einmal durchlaufen werden, ist das Hamiltonkreisproblem NP-vollständig.
Das heißt im Klartext: Es gibt kein einfach anwendbares Kriterium, man muss sich den Graphen also im Detail anschauen oder sämtliche Möglichkeiten durchprobieren. Das gilt für Hamiltonkreise genauso wie für Hamiltonpfade.
Ok das heißt diese Aufgabe lässt sich wirklich nur durch viel Text/durchprobieren lösen,wie in deiner und ein paar anderen Antworten. Als ich diese Antwort hier sah hab ich mich wohl zu früh gefreut :D
PS: in unserer Vorlesung hieß es es ist WAHRSCHEINLICH NP-vollständig, wollte ich nur mal anmerken :D
Nehmen wir an, die Felder sind - wie beim Schach üblich - mit A1-D4 beschriftet.
Man kann das Feld in 4 "Systeme" unterteilen, die jeweils fortlaufend zyklisch Durchlaufen werden.
System 1 sind die Felder A1-C2-D4-B3 (enthält 2 Ecken)
System 2 sind die Felder C1-A2-B4-D3 (enthält keine Ecken)
System 3 sind die Felder D1-B2-A4-C3 (enthält 2 Ecken)
System 4 sind die Felder B1-A3-C4-D2 (enthält keine Ecken)
Man sieht, das man von System 1 nicht direkt in System 3 wechseln kann (und umgekehrt) und dass man von System 2 nicht direkt in System 4 wechseln kann (und umgekehrt). Man muss also, um von einem System mit Ecke in das andere System mit Ecke zu kommen, mindestens ein Feld eines Systems ohne Ecke besuchen. Analoges gilt für den Wechsel von System 2 zu 4 (oder umgekehrt)
Des Weiteren sieht man: die "Ecksysteme" kann man von anderen Systemen nur über die mittleren Felder betreten oder verlassen.
Wenn man ein Ecksystem über ein Mittelfeld betritt (z.B. System 1 über Feld C2), so MUSS dieses System abgeschlossen werden, befor man ein anderes System betritt, ansonsten kann es auch später nicht mehr abgeschlossen werden. Warum? Weil die beiden Ecken (in diesem Fall) A1 und B4 nur über die Felder C2 oder B3 betreten oder verlassen werden können!
Wenn ich also auf C2 stehe, kann ich eine der Ecken also nur dann betreten (und wieder verlassen!!), wenn B3 zuvor noch nicht betreten wurde! Sobald ich aber (zB) C2-A1-B3 gezogen habe, MUSS ich auf D4 ziehen, da dieses Feld sonst später nicht mehr erreichbar ist! Ziehe ich aber nach D4, so komme ich von dort nicht mehr weg, da C2 und B3 schon betreten wurde. Das bedeutet: so ein Eckfeld, müsste das letzte in der Zugfolge sein, damit die Aufgabe gelöst werden könnte.
Da es aber 2 Systeme mit Ecken gibt, und davon mindestens eines "in der Mitte der Zugfolge" betreten werden muss (wegen des Zwanges von einem geraden System in ein ungerades zu wechseln und umgekehrt), landet man entweder immer in einer Ecke, aus der man nicht mehr herauskommt, bevor alle Felder besucht sind, oder man verbaut sich die Möglichkeit, diese Ecke noch zu besuchen.
Beweis durch Unmöglichkeit des Versuchs alle Felder genau einmal zu erreichen.
Es muss immer eine Ecke geben, in der und in der gegenüberliegenden Ecke du nicht angefangen hast.
In diese Ecke kannst du nur von 2 Feldern rein und raus. Würdest du nicht gleich in die gegenüberliegende Ecke springen, so würdest du die gegenüberliegende Ecke niemals erreichen, da beide Ecken die selben Eingangs und Ausgangsfelder haben.
Dein Versuch muss also in einer Ecke enden.
Folglich musst du auch in einer Ecke anfangen, da du sonst zwingend 2 mal in einer Ecke enden musst.
Daraus resultiert eine zwingende Reihenfolge der Sprünge, die aber dazu führt, dass du nicht Erfolg hast.
Damit ist bewiesen, dass es keine Möglichkeit gibt, alle Felder abzuspringen.
-----
Macht etwas Arbeit aber auf 2 Seiten in 20 Minuten zu schaffen.
Tipp: Stelle das 4x4 Schachbrett als Graphen dar. Die Felder sind die Knoten des Graphen. Zwei Knoten sind mit einer Kante verbunden, wenn der Springer in 1 Zug vom einen Feld zum anderen gelangen kann. Nun musst du nur noch beweisen, dass es keinen Hamiltonpfad in diesem Graph gibt. Ein Hamiltonpfad ist ein Pfad in einem Graphen, der jeden Knoten genau 1 mal erreicht. Verwechsle dies nicht mit dem Hamiltonkreis, für den zusätzlich gelten muss, dass Start- und Endknoten verbunden sein müssen.
Mehr Infos und Ideen für einen Beweis findest du im Wikipedia-Artikel Hamiltonkreisproblem.
Egal ob 3x3, 4x4 usw. Es geht nur mit einem Zusatzfeld auf einer verlängerten Seite. Der Springer bewegt sich asymetrisch, also muss auch das Spielfeld asymetrisch sein, damit es geht.
Das ist falsch: auf einem (symetrischen!) 8x8 Feld z.B. geht das natürlich. Hier lassen sich sogar Start-und Zielfeld (solange sie unterschiedliche Farben haben) frei wählen!
Da lässt sich doch super leicht ein Gegenbeispiel konstruieren, baue eine Reihe mit Feldern, die sich der Reihe nach abspringen lässt. Und 2 mal kommt sich die Reihe so nahe, dass du einen andern weg hast. Dann hast du 4 Felder mit 3 Möglichkeiten aber eine lösung. Ich halte den Beweis hier für nicht geführt.