Solohalma und Conway's Soldiers

Im ersten Zirkel des Schuljahres am 04.09.2014 haben wir uns mit einem Spiel beschäftigt, das den meisten als Solohalma oder Solitär oder Steckhalma bekannt ist, und einem Problem auf einem unendlich ausgedehnten Gitter, welches sich an dieses Spiel anlehnt und als Conway's Soldiers bekannt ist.

Solohalma

Zur Erwärmung galt es, einige einfache Konstellationen so aufzulösen, dass ein einziger Stein übrigbleibt. Dazu stand die Frage im Raum, bei welchen dieser Konstellationen der letzte Stein in der Mitte landen kann. Ausgehend von einer geeigneten Färbung haben wir herausgefunden, dass beim kompletten Spiel nur fünf Felder für den letzten Stein möglich sind und die eventuelle Zusatzbedingung, dass der letzte Stein in der Mitte landen soll, in Wirklichkeit keine Zusatzbedingung ist (vorausgesetzt, der fehlende Stein zu Beginn ist der mittlere).

Conway's Soldiers

Im zweiten Teil haben wir uns mit dem Spiel Conway's Soldiers beschäftigt. Durch Experimentieren galt es herauszufinden, wie weit man in den leeren Bereich eindringen kann und wie viele Steine mindestens nötig sind, um 1, 2, 3, ... Reihen tief einzudringen. Vermutet wurden als nötige Mindeststeinanzahl die Zweierpotenzen, was falsch ist.

Noch ungelöste Aufgabe: Finde eine Zugfolge mit 20 Steinen, die einen Stein 4 Reihen tief in das leere Gebiet führt. Zeige, dass weniger als 20 Steine nicht ausreichen.

Die Vermutung, dass man beliebig weit in das leere Gebiet eindringen kann, wurde durch zahlreiche Fehlversuche geschwächt. Tatsächlich gilt der folgende überraschende

Satz: Es ist unmöglich, mehr als 4 Reihen tief in das leere Gebiet einzudringen.

Mit der Idee der Bewertung der Felder mit Potenzen $x^n$ haben wir einen Beweis gestartet. Als geeignet hat sich für $x$ das Reziproke des goldenen Schnitts erwiesen. So lassen sich die Änderungen der Gesamtbewertung während des Spiels verfolgen: diese wird nie größer. Für den Gesamtwert der belegten Felder mussten geometrische Reihen berechnet werden.

Nachtrag

Im aktuellen Aufgabenblatt soll dieses Problem etwas weiter gesponnen werden. Zum einen geht es um die Verallgemeinerung des Satzes in $n$ Dimensionen, zum anderen um die Frage, ob man für $x$ im Beweis auch andere Zahlen verwenden kann.

Desweiteren hat Schlrak während der Experimentierphase einen recht langsam arbeitenden) Algorithmus vorgeschlagen, der allem Anschein nach Steine in beliebige Tiefen befördert. Aufgrund des letzten Satzes muss das falsch sein. Eine korrekte Beschreibung und Implementation des Algorithmus finden wir hoffentlich bald hier, dann sehen wir vielleicht, was er wirklich tut.

Zurück: MSG-12ab