Forum:  Spiel & Spaß
Thema: Lyfoe-Spiel
Themen-Übersicht
Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1510
Aus: Chile, Ulm
Themenstart: 2020-08-11 23:35

Für den Drehtorus ist es ja relativ leicht gewesen, ein polynomial-beschränktes Verfahren zu finden, das ihn ordnet.

Für das Lyfoe-Spiel hingegen scheint mir das deutlich schwerer zu sein; ich habe nach einem Tag herumprobieren nichts gefunden. Vielleicht existiert ja auch kein solches Verfahren.



Was mir auffällt: falls die Behälter im Spiel 3 Bälle enthalten, dann steht immer 1 leerer Behälter zur Verfügung. Falls die Behälter 4 Bälle enthalten, dann stehen (fast immer) 2 leere Behälter zur Verfügung. Kann es sein, dass in diesen Fällen die Bälle beliebig vermischt werden dürfen?

Und: die Anzahl der Farben bzw Behälter ist anscheinend stets irrelevant. Auch unbewiesen, oder?


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1510
Aus: Chile, Ulm
Beitrag No.1, vom Themenstarter, eingetragen 2020-08-12 16:04

2020-08-11 23:35 - Goswin im Themenstart schreibt:
Für den Drehtorus ist es ja relativ leicht gewesen, ein polynomial-beschränktes Verfahren zu finden, das ihn ordnet. Für das Lyfoe-Spiel hingegen scheint mir das deutlich schwerer zu sein.

Ich vereinfache die Aufgabe einmal etwas:

Für eine beliebige Stellung mit \(n\) Behältern plus einem leeren Behälter, finde in polynomialbeschränkter Zeit eine Zugfolge die
(1) zu einer Stellung mit ebenfalls einem leeren Behälter führt, und
(2) mindestens eine Kugel bewegt, die nicht auf einer gleichfarbigen Kugel liegt.

Wenn so eine Zugfolge existiert, dann existiert anscheinend auch ein polynomialbeschränktes Verfahren für die Gesamtlösung: es kann ja bei einer Behälterhöhe \(h\) nur maximal \((h\!-\!1)n\) Züge geben, die eine Kugel von einer ungleichfarbigen Kugel fortbewegen.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1510
Aus: Chile, Ulm
Beitrag No.2, vom Themenstarter, eingetragen 2020-08-13 18:35

2020-08-11 23:35 - Goswin im Themenstart schreibt:
Was mir auffällt: falls die Behälter im Spiel 3 Bälle enthalten, dann steht immer 1 leerer Behälter zur Verfügung. Falls die Behälter 4 Bälle enthalten, dann stehen (fast immer) 2 leere Behälter zur Verfügung. Kann es sein, dass in diesen Fällen die Bälle beliebig vermischt werden dürfen?

Nicht immer: Stellungen der Art
\[
\left[\matrix{1&1&1&\_ \\ 2&2&2&\_ \\ 3&3&3&\_ }\right], \qquad
\left[\matrix{1&1&1&2&2&2&\_ \\ 3&3&3&4&4&4&\_ \\ 5&5&5&6&6&6&\_ }\right], \qquad\ldots
\] sind nicht auflösbar.

Aber das waren bisher auch die einzigen, die ich für Behälterhöhe \(h=3\) mit 1 Leerbehälter finden konnte.
Und für Behälterhöhe \(h\in\{3,4\}\) mit 2 Leerbehältern kenne ich überhaupt kein Gegenbeispiel.




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=248997=7
Druckdatum: 2020-10-24 17:27