Eroberung Pekings

21.06.2022, 19:52

Huggy

Eroberung Pekings

Gegeben sei ein unendliches großes Schachbrett. Es ist durch die Große Mauer in zwei Hälften geteilt. Nördlich der großen Mauer leben die Chinesen mit ihrer Hauptstadt Peking (rotes Quadrat). Südlich der großen Mauer leben die Mongolen, die eine Armee zur Eroberung Pekings aufstellen. Die Armee besteht aus Spielsteinen. Jeder Stein besetzt ein Feld und auf einem Feld kann höchsten ein Stein stehen.

Nach dem Aufstellen der Armee zieht sie in den Krieg. Bei einem Zug überspringt ein Stein einen unmittelbar waagrecht oder senkrecht benachbarten Stein und kommt dadurch auf das Feld unmittelbar hinter dem übersprungenen Stein. Dieses Feld muss vor dem Zug leer sein. Der übersprungene Stein wird entfernt. Diagonale Züge sind nicht erlaubt.

[attach]55452[/attach]

Mit einer Armee von zwei Steinen kommt man nur ein Feld nach Norden (links im Bild). Mit vier Steinen kann man zwei Felder nach Norden kommen (in der Bildmitte). Die Züge sind:
1. f4-f6 2. h5-f5 3. f5-f7

Kann die mongolische Armee Peking erobern? Peking ist erobert, wenn ein Stein auf das Pekingfeld gelangt. Die mongolische Armee darf beliebig groß sein, auch unendlich groß. Sie darf beliebig südlich der großen Mauer aufgestellt werden.

22.06.2022, 11:26

HAL 9000

Auf diesen Beitrag antworten »

Nettes Spiel. Eine zufriedenstellende Lösung kann ich nicht anbieten, nur ein paar Gedanken:

Man kann von der Endstellung "Ein Stein in Peking" ausgehend rückwärts Zwischenstellungen konstruieren, die allesamt zum Sieg führen. Ein solcher Rückwärtsschritt besteht darin, dass ein Stein ersetzt wird durch zwei Steine im nächsten und übernächsten Feld in irgendeiner Richtung - dazu müssen diese Felder natürlich frei sein.

Ein solcher Rückwärtsschritt nach oben scheint wenig Sinn zu machen. Vorzugsweise wird man Schritte nach unten machen wollen, damit die obersten Reihen nach und nach geleert werden, aber das wird nicht immer möglich sein. D.h. es werden auch seitliche Schritte nötig sein, da an den Seiten womöglich mehr freier Platz nach unten vorhanden ist.

Soweit erstmal die Binsenweisheiten zu einer solchen Backward-Methodik. Die eigentliche Schwierigkeit ist, das in einen Algorithmus zu gießen, der nicht einfach nur im "unteren" Bereich endlos neue Steine erzeugt, sondern auch nachweisbar die oberen Reihen nach und nach abräumt. Augenzwinkern

24.06.2022, 16:30

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Man kann von der Endstellung "Ein Stein in Peking" ausgehend rückwärts Zwischenstellungen konstruieren, die allesamt zum Sieg führen. Ein solcher Rückwärtsschritt besteht darin, dass ein Stein ersetzt wird durch zwei Steine im nächsten und übernächsten Feld in irgendeiner Richtung - dazu müssen diese Felder natürlich frei sein.

Ja, man kann das vorwärts und rückwärts spielen. Ob vorwärts oder rückwärts, ein Go-Brett eignet sich gut zum Probieren.

Wenn man die obige Armee aus 4 Steinen, mit der man 2 Felder nach Norden kommt, um weitere 4 Steine (grau) ergänzt, kommt man schon 3 Felder nach Norden. Die Züge dürften klar sein.

[attach]55469[/attach]

Um 0, 1, 2, 3 Felder nach Norden zu kommen, braucht es also Armeen aus 1, 2, 4, 8 Steinen. Das legt eine Vermutung nahe. Aber wird sich die als richtig erweisen?

27.06.2022, 19:10

Huggy

Auf diesen Beitrag antworten »

Um 4 Felder nach Norden zu kommen, braucht man schon 20 Steine. Hier eine der Aufstellungen:

[attach]55481[/attach]

Es gibt noch eine zweite Aufstellung, die sich von dieser aber nur wenig unterscheidet. Jetzt ist Peking ganz nah. Schaffen die Mongolen noch den letzten Schritt?

29.06.2022, 13:18

Huggy

Auf diesen Beitrag antworten »

Peking kann nicht erobert werden!

Nach einigen vergeblichen Versuchen wird man das vermuten. Aber wie beweist man es? Der Beweis ist nicht kompliziert. Er beruht aber auf einer raffinierten Methode, auf die man erst mal kommen muss. Meine Bewunderung gilt dem Erfinder der Methode.

Vorab sei festgestellt, wenn Peking erobert werden könnte, dann ginge das auch mit einer endlichen Armee. Denn wenn ein Stein im Zug $\begin{eqnarray*} n \end{eqnarray*}$ Peking erreichen würde, wären daran nur die Steine, die gesprungen haben und die, die übersprungen wurden, beteiligt gewesen. Das sind maximal $\begin{eqnarray*} 2n \end{eqnarray*}$ Steine. Alle anderen Steine hätte man weglassen können.

Zum Beweis wird jedem Feld ein Wert zugewiesen:

[attach]55500[/attach]

$\begin{eqnarray*} \varphi = \frac {\sqrt 5-1} 2 \approx 0.618034 \end{eqnarray*}$

ist die vom Goldenen Schnitt her bekannte Konstante, die der Gleichung

$\begin{eqnarray*} (*) \quad \varphi^2+\varphi=1 \end{eqnarray*}$

genügt. Peking hat den Wert $\begin{eqnarray*} \varphi^0=1 \end{eqnarray*}$ . Der Wert einer Stellung wird definiert als die Summe aller Werte der Felder, auf denen sich ein Stein befindet. Wird Peking erreicht, ist der Stellungswert daher $\begin{eqnarray*} \geq 1 \end{eqnarray*}$ .

Zwei benachbarte Felder habe überall die Werte $\begin{eqnarray*} \varphi^{n+1} \end{eqnarray*}$ und $\begin{eqnarray*} \varphi^n \end{eqnarray*}$ . Die Summe der beiden Werte ist wegen (*):

$\begin{eqnarray*} \varphi^{n+1}+\varphi^n=\varphi^{n-1}(\varphi^2+\varphi)=\varphi^{n-1} \end{eqnarray*}$

Sitzen zwei Steine auf diesen Feldern und überspringt einer den anderen, so kommt der springende Stein auf ein Feld mit Wert $\begin{eqnarray*} \varphi^{n-1} \end{eqnarray*}$ oder $\begin{eqnarray*} \varphi^{n+2} \end{eqnarray*}$ . In dem ersten Fall ist der Wert der Stellung durch den Zug gleich geblieben. Im zweiten Fall ist er wegn $\begin{eqnarray*} \varphi < 1 \end{eqnarray*}$ kleiner geworden. Der Wert einer Stellung kann durch Züge nie größer werden.

Mittels der Formel für die geometrische Reihe und (*) zeigt man leicht, dass die Summe aller Feldwerte unterhalb der großen Mauer exakt $\begin{eqnarray*} 1 \end{eqnarray*}$ ist. Eine endliche Armee hat daher in der Ausgangsstellung einen Wert $\begin{eqnarray*} <1 \end{eqnarray*}$ . Da der Wert durch Züge nicht größer werden kann, kann Peking nicht erreicht werden.

Dieses Problem ist aus

E. R. Berlekamp, J. H. Conway, R. K. Guy
Gewinnen
Strategien für mathematische Spiele
Band 4

Der wegen seiner vielen Bücher bekannte englische Mathematiker Ian Stewart hat es vor langer Zeit auch mal in "Spektrum der Wissenschaft" aufgegriffen.

29.06.2022, 19:27

Conny_1729

Auf diesen Beitrag antworten »

Das ist ja wirklich eine geniale Methode!!!
Aus welchem Jahrgang "Spektrum der Wissenschaft" stammt denn das Rätsel? Könnte ja sein, dass ich das Heft noch habe.

Andere Fragestellung zu diesem Problem:
Gehen wir einmal davon aus, dass es sich nun um ein 3-dimensionales Raumgitter handelt. Müsste die Stadt sich dann 3 Zeilen höher bewegen, um wieder in Sicherheit zu sein???

Gruß
Conny

29.06.2022, 19:42

HAL 9000

Auf diesen Beitrag antworten »

An eine Bewertungsfunktion abhängig vom $\begin{eqnarray*} L^1 \end{eqnarray*}$ -Abstand zum Ziel hatte ich auch schon gedacht. Allerdings nicht an die und auch in dem gegenteiligen Willen, tatsächlich einen Algorithmus zu finden - so kann man sich täuschen. Augenzwinkern

Zitat:

Original von Huggy
Denn wenn ein Stein im Zug $\begin{eqnarray*} n \end{eqnarray*}$ Peking erreichen würde, wären daran nur die Steine, die gesprungen haben und die, die übersprungen wurden, beteiligt gewesen. Das sind maximal $\begin{eqnarray*} 2n \end{eqnarray*}$ Steine.

Eigentlich doch eher GENAU $\begin{eqnarray*} n+1 \end{eqnarray*}$ , oder? verwirrt

30.06.2022, 07:53

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von Conny_1729
Aus welchem Jahrgang "Spektrum der Wissenschaft" stammt denn das Rätsel?

Heft 3/95

Zitat:

Gehen wir einmal davon aus, dass es sich nun um ein 3-dimensionales Raumgitter handelt. Müsste die Stadt sich dann 3 Zeilen höher bewegen, um wieder in Sicherheit zu sein???

Ja. Das ergibt sich aus der bisherigen Bewertungsfunktion. Es bliebe noch zu zeigen, dass man tatsächlich 5, 6 und 7 Schritte voran kommen kann. 5 ist kein Problem. Für 6 und 7 reicht mein 3D-Vorstellunsvermögen nicht aus. Man müsste sich einige gläserne Go-Bretter besorgen und daraus ein 3D-Brett basteln. Oder man lässt sich vom Computer helfen. Vielleicht hat HAL da schon ausreichend Vorarbeit geleistet.

Zitat:

Original von HAL 9000

Zitat:

Eigentlich doch eher GENAU $\begin{eqnarray*} n+1 \end{eqnarray*}$ , oder? verwirrt

Stimmt natürlich, wenn zum Schluss nur noch der Stein auf Peking da ist. Sonst können es auch mehr sein.

30.06.2022, 14:10

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
Vielleicht hat HAL da schon ausreichend Vorarbeit geleistet.

Nein, so tief habe ich mich nicht reingekniet. Alles nur Gehirn und ein bisschen (digitales) Kästchenpapier, und leider auch alles für die Katz. Augenzwinkern

30.06.2022, 18:38

Conny_1729

Auf diesen Beitrag antworten »

Vielen Dank für den Tipp!!!
Ich habe das Heft 3/95 (Spektrum der Wissenschaft) bei mir gefunden. Ein sehr amüsant geschriebener Artikel. Jetzt bin ich auch etwas schlauer, was es mit dieser sogenannten "Pagodenfunktion" auf sich hat, die man bei Brettspielen anwenden kann.

Demzufolge kann man sich nun weitere Spielsteinkonfigurationen überlegen, die theoretisch niemals erreicht werden können. Wenn ich das hoffentlich alles richtig verstanden habe, dann gilt das auch für jene Beispiele in meiner Anlage, da die Summe der rot umrandeten Felder immer größer oder gleich eins ist.

Gruß
Conny
.

Neue Frage »

Antworten »

Eroberung Pekings

Verwandte Themen