Wie geht man in solch einer Aufgabe vor, ist das Kombinatorik? (Bitte nicht die Lösung direkt verraten, sondern sagen wie man da vorgeht)?(Uni-Mathematik)?

Erstmal das geht hier um Kombinatorik oder?
So sieht das Spiel aus:

Das ist die Spielanleitung:

Und nun verstehe ich nicht, wie soll man hier rechnen? 12 Uhr ist auf dem Spiel da vorne, wo der Pfeil am Anfang zeigt.

Hat jemand eine Idee bzw. ein Mathecrack?

Die Aufgabe ist von einem Informatikkurs, über künstliche Intelligenz

Answer 1

[ralphdieter]

Mit Kombinatorik kommst Du hier nicht weiter. Was Du brauchst, ist eine zündende Idee und die Fähigkeit, diese mathematisch exakt zu formulieren.

Bei beidem hilft Dir die Graphentheorie: Die möglichen Spielstellungen sind Knoten, und jeder erlaubte Zug ist eine gerichtete Kante. Die Kunst besteht vor allem darin, die Knoten und Kanten geschickt zu benennen, um die Spielregeln möglichst einfach abbilden zu können.

Zum Aufwärmen hier ein naiver Ansatz: Ein Knoten wird durch zwei Strings (für innen und außen) der Länge n beschrieben, die nur aus '−' (leer), '+' (rot) und '↓' (Pfeil) bestehen. Beschreibe formal verschiedene Eigenschaften eines Knotens k, zum Beispiel:

• k ist ein Startknoten ⇔ k = ("+++···↓+++···", "↓−−−···–")
• k ist ein Endknoten ⇔ ...
• k ist eine Sackgasse ⇔ ...
• Anzahl der Steine: s(k) := Σᵢ (k_innen[i]=='+') + Σᵢ (k_außen[i]=='+')
• Position von '↓' innen: p(k) := ...

Zusätzlich musst Du die Kanten (=erlaubte Züge) formal beschreiben:

• k₁→k₂ : ???

Mit der gewählten Darstellung ist das zwar schwierig zu formalisieren, aber das ist für die Aufgabe gar nicht nötig. Behalte nur im Kopf, dass jede Kante einen Knoten k₁ in einen k₂ überführt. Dabei werden bestimmte Eigenschaften von k₁ beibehalten, andere ändern sich vorhersehbar.

Aus der Hoffnung auf eine „göttlichen Eingebung“ wird so die gezielte Suche nach einer Knoten-Eigenschaft, die den Beweis von Proposition 1 ermöglicht. Und da etwas über die Position des inneren Pfeils gesagt wird, lohnt es sich, die Folge p(k₁), p(k₂) ... für eine Lösung k₁→k₂→··· genauer zu untersuchen.