Jeden Pfennig zweimal umdrehen...? Rätsel ist gelöst

Logicals, Sudokus und andere Logikrätsel

Re: Jeden Pfennig zweimal umdrehen...?

Beitragvon Otmar » Donnerstag 26. September 2013, 23:42

Hallo Phoenix,
:super:
Mehr ->
ich denke, dass man deine Begründung so bereits als Lösung für Bob gelten lassen kann. Jedenfalls wenn man sich etwas eingespielt hat.

:tipp:
Mehr ->
Allerdings kann man die Argumentation noch einfacher führen und dann das Spiel sowohl theoretisch als auch praktisch dahingehend vereinfachen, dass man auf das Umklappen verzichten kann und nur noch schieben muss. Die Frage, was man dann schieben muss und in welche Stellung, möchte ich noch nicht beantworten. Natürlich verschiebt man nicht die zu Anfang auf dem Spielfeld liegenden Münzen.
Liebe Grüße, Otmar.
Benutzeravatar
Otmar
Schlaumeier
Schlaumeier
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 1618
Themen: 120
Registriert: Dienstag 10. Mai 2011, 22:10
Wohnort: München
Geschlecht: männlich

Re: Jeden Pfennig zweimal umdrehen...?

Beitragvon Otmar » Mittwoch 2. Oktober 2013, 16:32

Nachdem Neuling und Phoenix Lösungen für Anton und Bob eingestellt haben, ist es an der Zeit auch eine Lösung für den dritten Spieler zu finden. Dazu habe ich noch ein paar Tipps.

Vorüberlegung:

Mehr ->
Das Spielfeld besteht aus lauter gleichseitigen Dreiecken, die zwei möglichen Orientierungen haben. In meiner Skizze vom 16. September hatte ich das bereits hervorgehoben. Dort waren die Felder a, c, d, f, h, j und l, bei denen eine Ecke nach oben zeigt rot gefärbt und die Dreiecke b, e, g, i, k und m bei denen eine Ecke nach unten zeigt, grün gefärbt. Nun ist es so, dass bei jedem Zug eine Münze sowohl ihre Orientierung (Kopf oder Zahl oben) als auch die Farbe des Feldes (rot oder grün) ändert. Und jetzt kann man weiter denken und sagen, wenn eine Münze von der Startposition zur Zielposition ihre Orientierung ändern soll, muss diese Münze auch ihre Feldfarbe vom Start zum Ziel ändern. Liegt eine Münze hingegen beim Start schon richtig herum, dann muss sie auch in der Zielposition auf einem Feld gleicher Farbe wie beim Start zu liegen kommen. Anders gesagt, alle Münzen die anfangs schon mit Zahl nach oben liegen haben in der Endstellung die gleiche Feldfarbe wie am Start und alle Münzen, die anfangs mit Kopf nach oben liegen, müssen in der Endstellung genau auf der anderen Farbe wie beim Start liegen.


Bob kann die Zielstellung nicht erreichen, weil:
Mehr ->
die Münzen die anfangs auf b,e,g und k liegen ihre Farbe nicht ändern, also auf einem grünen Feld enden. Die anderen Münzen (zwei auf grün und sechs auf rot) müssen ihre Farbe ändern und benötigen in der Zielstellung also zwei rote und sechs grüne Felder. Bobs Zielstellung müsste also zwei rote und zehn grüne Felder haben, so dass alle Münzen mit Zahl nach oben liegen können. Da die Zielstellung aber nur sechs grüne Felder hat, spielt Bob immer noch vergeblich weiter.

Mit den Ergebnissen aus der Vorüberlegung lässt sich das Spiel vereinfachen.
Mehr ->
Denn man kann ja zu Anfang schon sagen, auf welcher Farbe eine bestimmte Münze in der Endstellung liegen muss. D.h. anstelle der Münzen könnte man sechs grüne und sechs rote Spielsteine verwenden und am Anfang auf jedes Startfeld Spielsteine in der Farbe legen, die der Farbe entspicht, die das Feld des Spielsteins in der Endstllung haben muss. D.h. liegt am Anfang Zahl oben, hat der Spielstein die Farbe des Startfeldes und liegt am Anfang Kopf oben, dann hat der Spielstein genau die andere Farbe als das Startfeld. Das Spiel wird jetzt so gespielt, dass die Steine nur noch ins freie Feld ziehen und man auf das Umklappen verzichten kann. Die Endstellung ist erreicht, wenn Feld f leer ist und auf jedem anderen Feld ein Spielstein in der Farbe des Feldes liegt.

Phoenix hat schon eine "kleinste sinnvolle Spieleinheit" genannt. Wie kommt das? Wenn man ein freies Feld auf einem Randfeld (a,b,c,h,m,l,j,i,d) durch einen Zug erzeugt hat, dann bleiben nur zwei Möglichkeiten, dieses Randfeld mit einem Spielstein zu füllen. Eine der Möglichkeiten ist ein Rückzug, der zu einer vorher vorhandenen Spielstellung führt und somit zu einer um mindestens 2 Spielzüge zu langen Zugfolge beiträgt. Dieser Rückzug geht also nicht. Daher ist auf Randfeldern nur eine Möglichkeit des sinnvollen Weiterspielens gegeben. Bei freien Feldern e, g und k hat man für alle Züge zwei Möglichkeiten des Weiterziehens ohne Rückzug. Nehmen wir an, das freie Feld wandert von j nach k, dann kann es im nächsten Zug nach f oder l wandern. Wenn wir zur Vereinfachung die direkte Wanderung von k nach l verbieten und anstelle dessen das freie Feld von k nach f nach k und nach l wandern lassen, dann wird das Feld f nach jeweils 6 Zügen wieder frei und diese 6 Züge sind die von Phoenix genannte "kleinste sinnvolle Spieleinheit". Wir können nun jede Zugfolge durch solche kleinsten Spieleinheiten beschreiben.

Für spätere Verwendung gebe ich den sechs möglichen Spieleinheiten Namen:
"O ->" : verschiebt oben Spielsteine von g nach e von e nach a von a nach b von b nach c und von c nach g im Uhrzeigersinn.
"O <-" : verschiebt Steine oben gegen den Uhrzeigersinn und macht "O ->" rückgängig.
"L ->" bzw. "L <-" verschiebt Steine auf Feldern e, d, i, j und k im bzw. gegen den Uhrzeigersinn.
"R ->" bzw. "R <-" verschiebt Steine auf Feldern g, h, m, l,und k im bzw. gegen den Uhrzeigersinn.

Beim Zählen der Einzelzüge haben wir für jede Spieleinheit 6 Züge und falls die vorhergehende Spieleinheit passte können wir die beiden zusätzlichen Züge wieder abziehen. Zwei Züge werden gespart, wenn zwei aufeinanderfolgende Spieleinheiten den gleichen Urzeigersinn hatten und im entgegengesetzten Sinn angeordnet sind. Genauer gesagt, werden bei den Paaren:

{O->, L->}, {L->, R->} {R->, O->}
{L<-, R<-}, {R<-, L<-} {O<-, R<-}

je zwei Züge gespart.
Ich habe jetzt vereinfachend in folgender Tabelle gespielt:

Mehr ->
kjideabcghmlk Felder, 5 Stück je Spieleinheit. Feld k wird doppelt geschrieben.
1010101010101 Start für Anton: 1 steht für einen roten Spielstein, 0 für grünen Spielstein
11010 1 L<- (Pfleil ist in Richtung des großen Sprunges, hier der 1 von e nach k)
0 11010 R<-
01010 O->
0101010101010 Zielstellung (für alle drei Spieler gleich)

In Spalten in denen eine Spieleinheit keine Steine verschiebt habe ich nichts geschrieben.

Anton braucht hier drei Spieleinheiten wobei bei L<- gefolgt von R<- zwei Züge gespart werden. Also braucht Anton bei diesem Spiel 6*3-2 = 16 Züge.
Bei Chris sieht es so aus:
Mehr ->
kjideabcghmlk
0000001111110 Startstellung: 1 steht für einen roten Spielstein, 0 für grünen Spielstein
?
?
?
?
?
?
?
?
0101010101010 Zielstellung


Es werden 8 Spieleinheiten gebraucht und es gibt insgesamt 14 Möglichkeiten die Zielstellung mit 8 Spieleinheiten zu erreichen. Aber nur zwei davon liefern minimale Zugfolgen von 42 Zügen. Diese findet man leichter, wenn man versucht möglichst viele Züge im gleichen Uhrzeigersinn laufen zu lassen, weil so die Chancen zum Sparen von Zügen höher sind. Bei einer dieser beiden Lösungen gehen sogar alle Spieleinheiten im gleichen Uhrzeigersinn.
Vielleicht findet Chris mit diesen Tipps noch eine Lösung.
Liebe Grüße, Otmar.
Benutzeravatar
Otmar
Schlaumeier
Schlaumeier
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 1618
Themen: 120
Registriert: Dienstag 10. Mai 2011, 22:10
Wohnort: München
Geschlecht: männlich

Re: Jeden Pfennig zweimal umdrehen...?

Beitragvon MadMac » Dienstag 2. August 2016, 13:24

Mehr ->
Ich habe die Buchstabenfolge so umsortiert, dass ich nur einen Ring um das f betrachte. Es gibt im Prinzip in jeder Stellung nur sechs Zugfolgen von f nach f. Lediglich, wenn man im Uhrzeigersinn oder gegen den Uhrzeigersinn einen Zug in die nächste Ecke "fortsetzt", ergibt sich ein gewisses Optimierunsgpotential von dieser starren Regel, da man das Zurückflippen nach f und den Folgezug sparen kann. Im folgenden stelle ich alle Zwischenstellungen so dar, als hätte ich nach jedem 6er bzw. optimierten 4-er-Block nach F zurückgeflippt.

A:
m = eabc ghmlkf edijkf
ml = 16
sol =
e a b c g h m l k j i d
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1

C:
m = ghmlkf eabcgf eabc ghml kjidef kjid eabcgf kjidef
ml = 42
sol =
e a b c g h m l k j i d
1 0 0 1 0 1 0 1 1 0 1 0
1 0 0 1 0 1 0 0 0 0 1 0
1 1 0 1 1 1 0 0 0 0 1 0
0 1 0 0 1 1 0 0 0 0 1 0
0 1 0 0 0 1 1 1 1 0 1 0
1 1 0 0 0 1 1 1 1 0 1 1
1 1 0 0 0 1 1 1 1 0 0 0
0 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1


B ist nicht lösbar. Das erscheint auch nicht ganz unwahrscheinlich, dass es unmögliche Stellungen gibt. Bei manueller Untersuchung lassen sich flott verschiedenste symmetrische Stellungen finden. Insgesamt scheint es 924 lösbare Stellungen zu geben im Gegensatz zu 2972 möglichen (wenn jeweils kein Stein auf f liegt).



Gruß,
MadMac
MadMac
Denksportler
Denksportler
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 180
Themen: 6
Registriert: Freitag 8. Juli 2016, 14:09
Geschlecht: männlich

Re: Jeden Pfennig zweimal umdrehen...?

Beitragvon Otmar » Dienstag 2. August 2016, 23:45

Hallo MadMac, deine Lösung ist richtig. :daumen:

Ich hatte das Rätsel fast vergessen und erst nach dem Lesen der Tipps ist mir wieder eingefallen, dass es noch eine nette zu Fuß Lösung gibt, wenn man den Spielablauf vereinfacht. Werde das bei Gelegenheit selbst nochmal durchspielen und bin gespannt, ob ich die beiden Lösungen für Chris finden kann. Lösungen für Anton und Bob sind ja mit Erklärung schon unter den Spoilern zu finden.
Liebe Grüße, Otmar.
Benutzeravatar
Otmar
Schlaumeier
Schlaumeier
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 1618
Themen: 120
Registriert: Dienstag 10. Mai 2011, 22:10
Wohnort: München
Geschlecht: männlich

Re: Jeden Pfennig zweimal umdrehen...?

Beitragvon MadMac » Mittwoch 3. August 2016, 09:25

Ich finde, dass dieses Rätsel ohne Programmieren schwer zu lösen ist - jedenfalls die optimale Lösung ist schwer zu finden, auch mit Vorüberlegungen und mit Tricks. Die Mächtigkeit des Entscheidungsbaumes wächst sehr schnell.

Machbar wird es dennoch wenn man

Mehr ->
die Züge, wie schon zuvor vorgeschlagen, zu Zugfolgen zusammenfasst, die je 5 Münzen bewegen und bei f beginnen und enden, und die Optimierungen erst später vornimmt.


und wenn man weiß, dass ...

Mehr ->
von der Startstellung Antons alle möglichen Stellungen nach bereits nach 8 dierser Zugfolgen erreicht werden können,


und das ausnutzt und ...
bzw. auf gut Glück ...

Mehr ->
die Lösung beginnend von Cs Startstellung und gleichzeitig rückwärts von der Zielstellung aus sucht. In dem Falle trifft man sich in der Mitte, und die maximale Mächtigkeit jedes Baumes umfasst 242 (Rückwärts-Baum) Möglichkeiten (bzw. eine ähnliche, aber möglicherweise abweichende Anzahl im Vorwärts-Baum).


Gruß,
MadMac
MadMac
Denksportler
Denksportler
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 180
Themen: 6
Registriert: Freitag 8. Juli 2016, 14:09
Geschlecht: männlich

Re: Jeden Pfennig zweimal umdrehen...?

Beitragvon Otmar » Mittwoch 3. August 2016, 21:11

@MadMac
Mehr ->
MadMac hat geschrieben:Ich finde, dass dieses Rätsel ohne Programmieren schwer zu lösen ist - jedenfalls die optimale Lösung ist schwer zu finden, auch mit Vorüberlegungen und mit Tricks. Die Mächtigkeit des Entscheidungsbaumes wächst sehr schnell.

Es kommt auf die Art der Vereinfachung an. Und soweit ich gesehen habe, bist du noch nicht soweit vorangekommen, dass eine "einfache" Lösung ohne Rechner in greifbarer Nähe ist. Beispielsweise ist der Beweis, dass Bob nicht fertig werden kann, sehr einfach ohne Rechner zu erbringen. Da muss auch nichts probiert werden.
Liebe Grüße, Otmar.
Benutzeravatar
Otmar
Schlaumeier
Schlaumeier
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 1618
Themen: 120
Registriert: Dienstag 10. Mai 2011, 22:10
Wohnort: München
Geschlecht: männlich

Vorherige

Zurück zu Logikrätsel

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron