Streichhölzer

Freizeit & Hobby Rätsel
#1

Hallo zusammen!
Meine Tochter hat ein Rätsel gefunden, auf dessen Lösung wir einfach nicht kommen. Vielleicht könnt Ihr ja netterweise helfen…
Es ist wie folgt:

Es handelt sich um 9 Streichhölzer.
Ich spiele abwechselnd gegen den Computer und ziehe zuerst.
Ich darf 1, 2 oder 3 Hölzer wegnehmen.
Der Computer verfährt dabei wie folgt:
Ziehe ich 1, nimmt er 3.
Ziehe ich 2, so nimmt er ebenfalls 2.
Ziehe ich 3, dann nimmt er 1.
Wer das letzte Hölzchen nehmen muss, verliert.

Wie gesagt, bisher haben wir es leider nicht geschafft, am Ende als Gewinner dazustehen…
Wer kann helfen? Ein herzliches DANKE schon einmal im voraus!!!

Gruß, Hicki

#2

Hi,
nimm 1 --> Pc nimmt 3 = 4
Rest 5
nimm 1/2/3 PC nimmt 3/2/1
Rest immer 1 = Verloren

nimm 2 --> Pc nimmt 2 = 4
Rest 5
weiter wie oben

nimm 3 --> Pc nimmt 1 =4
Rest 5
weiter wie oben

Befürchte Du musst dem PC den ersten Zug lassen, dann kannst du gewinnen.

.

#3

Hallo,
vielen Dank für deine Mühe.
Ja, das dachten wir auch schon, dass es nur geht, wenn der Computer den ersten Zug hat. Leider MUSS ich beginnen…
Laut Internetseite, auf der sich das Rätsel befindet, war A. Einstein der Letzte (oder sogar Einzige), der die Lösung heraus fand. Sollte es also doch eine Möglichkeit geben??? Oder nur ein Fake, um die Leute immer mal wieder anzulocken?

Jedenfalls vielen Dank für deine Antwort.
Gruß, Hicki

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#4

Hi…

Befürchte Du musst dem PC den ersten Zug lassen, dann kannst
du gewinnen.

Ja, das dachten wir auch schon, dass es nur geht, wenn der
Computer den ersten Zug hat. Leider MUSS ich beginnen…
Laut Internetseite, auf der sich das Rätsel befindet, war A.
Einstein der Letzte (oder sogar Einzige), der die Lösung
heraus fand. Sollte es also doch eine Möglichkeit geben???

Nein. Der arme Einstein wird hier misbraucht, um Leute zu verarschen. Wenn der zweite Spieler das gegebene System verwendet, gewinnt er immer.

genumi

#5

Gemeiner Link
Hallo Hicki,

jetzt bin ich mal so gemein, dir einen Link auf ein ähnliches Streichholzspiel zu geben, welches du nie gewinnen wirst. Und auch sonst kaum einer hier aus dem Forum. Aber das Spiel ist gewinnbar! http://193.170.245.144/~schule/kanguru/spiele/nimspi…

Es handelt sich um eine Variante des NIM-Spiels. Die Regeln sind sehr einfach - die Gewinnstrategie hingegen nicht.

Viel Spass beim Knobeln,
Schorsch

#6

Hallo Hicki,
wie Genumi schon schreibt, hilft bei einem so einfachen Rätsel und einer so klaren Lösung Genialität auch nicht weiter.
Dieses Rätsel habe ich im Vorschulalter vor 45 jahren schon gelöst. :wink:
So genial muß man dafür also nicht sein.
cu Rainer

#7

Hallo Schorsch,
das ist doch mal ne Aufgabe! Ich habe gerade drei Runden verloren. :wink:
Wenn die Wirkung der Biere heute nachläßt, mache ich mir mal Gedanken über die Strategie. Du meist ja, ich könnte das Rätsel nicht lösen, … dann versuche ich mal, das Gegenteil zu beweisen. :wink:
Bis die Tage,
cu Rainer :wink:

#8

Hallo,
der Trick besteht darin den Gegner eine Anzahl von Hölzern n aufzubürden, die mit Rest 1 durch 4 teilbar ist (n mod 4=1). Dann kann man mit einem perfekten Spiel immer gewinnen. Alle anderen Reste sind Gewinnpositionen und der Gegner der n mod 4=1 Hölzer hat ist durch die Einschränkung 1,2 oder 3 Hölzer zu ziehen genötigt mich wieder in eine Gewinnposition zu bringen (von der ich ihn wiederrum auf m mod 4=1 Hölzer drücken kann).
Fange ich z.B. mit 100 Hölzern an, habe ich automatisch gewonnen, sind es dagegen 101 habe ich zwangsläufig verloren. Bei 9 Hölzern hast Du als derjenige, der den ersten Zug macht, also zwangsläufig verloren, wenn der Gegner keine Fehler macht.

Gruss
Enno

#9

Vielen Dank für eure Antworten!Gruß,Hicki (owT)

.

#10

Hallo Horsch !

Die Gewinnstrategie der Version auf der von dir gezeigten Seite ist ebenfalls altbekannt und nicht so schwer.
Nur lassen die einen ebenfalls in einer Verliererposition starten, so dass natürlich der Computer immer gewinnt :frowning: .

mfg
Christof

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#11

Hallo Christof,
wenn das NIM-Spiel im angegebenen Link immer in einer Verliererposition starten würde, hätte ich den Computer wohl kaum besiegen können (als Belohnung kommt dann der Schriftzug „SPITZE!!“)… Für jemanden, der das Spiel zum ersten mal sieht, ist es alles andere als trivial, eine Gewinnstrategie zu finden, so dass es sich der Programmierer durchaus leisten konnte, als Anfangsposition eine Zufallsstellung vorzugeben.
Viele Grüße
Jens

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#12

Hallo Hristoph,

Die Gewinnstrategie der Version auf der von dir gezeigten
Seite ist ebenfalls altbekannt und nicht so schwer.
Nur lassen die einen ebenfalls in einer Verliererposition
starten, so dass natürlich der Computer immer gewinnt :frowning: .

wie Jens aus Viersen bereits schrieb, ist die Aufgabenstellung in diesem Fall nicht so trivial. Tatsächlich fängst du mit hoher Wahrscheinlichkeit (nicht errechnet, aber sicher über 70%) in einer Gewinnstellung an. Dass exklusiv zu odern altbekannt sei - damit gebe ich dir recht. Ist halt eine Grundrechenart.

Jetzt noch eine exklusive Frage an dich: Wie sieht die Strategie aus, wenn derjenige, der das letzte Hölzchen nimmt, nicht der Gewinner, sondern der Verlierer ist? Genau das macht den besonderen Reiz des NIM-Spiels aus!

Gruss,
Schorsch

#13

Hallo,

Aber das Spiel ist gewinnbar!

Kann es sein, daß das Spiel zwar gewinnbar ist, aber die Startposition nicht immer so aussieht, daß man gewinnen kann?

Gelegentlich gewinne ich, aber eine mathematische Grundlage konnte ich nicht finden. Bisher habe ich nur für eine der angebotenen ‚Startaufstellungen‘ (durch Vertauschen der Reihen ergeben sich dann 9. :wink:) eine Lösung. (X,7,5)
Die sieht allerdings nur so aus, daß ich weiß, was ich tun muß, der mathematische Hintergrund bleibt mir verborgen. Vermutlich komme ich auch deshalb nicht weiter. Ich probier noch ein wenig. :wink:
cu Rainer

#14

noch Gemeinerer Link
Und so funktioniert das, wenn man gewinnen will:

http://www.csm.astate.edu/secret.html

TwingO

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#15

Hi Schorsch,

hab noch keine vollstaendige Loesung fuer die neue Variante (bei der derjenige verliert, der das letzte Streichholz nimmt) gefunden, allerdings habe ich bereits eine Teilmenge an Verlustpositionen identifiziert (interessanterweise ist ein betraechtiger Anteil an Positionen verlustig fuer beide NIM-Spiel-Varianten.

Die Loesung in dem von TwingO angegebenen Link ist viel eleganter als meine eigene Loesung, zumal sich meine Loesung nur auf den Spezialfall mit 3 Streichholzreihen anwenden laesst.

Die Wahrscheinlichkeit einer anfaenglichen Verluststellung nimmt uebrigens exponentiell mit 2^(-n) ab, wobei 2^n die maximale Zahl an Streichhoelzern einer Reihe ist. Dies sieht man, wenn man die Loesung von TwingOs Link anschaut. Die Anzahl an Verluststellungen berechnet sich naemlich zu:
Nv=Summe_{k=0}^{n}(n ueber k)*3^k
=Summe_{k=0}^{n}(n ueber k)*3^k*1^(n-k)
=(3+1)^n
=2^(2*n)
Die Anzahl an Positionen ist
N=(2^n)^3
=2^(3*n),
so dass fuer die Wahrscheinlickeit einer Verluststellung am Anfang folgt:
W=Nv/N=2^(2*n)/2^(3*n)=1/2^n.

Viele Gruesse
Jens

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#16

Hallo Jens,

hab noch keine vollstaendige Loesung fuer die neue Variante
(bei der derjenige verliert, der das letzte Streichholz nimmt)
gefunden, allerdings habe ich bereits eine Teilmenge an
Verlustpositionen identifiziert (interessanterweise ist ein
betraechtiger Anteil an Positionen verlustig fuer beide
NIM-Spiel-Varianten.

wenn du die von Twingo angegebene Lösung genauer betrachtest, wirst du feststellen, dass die Gewinnstrategie in beiden Fällen tatsächlich identisch ist: Du kontrollierst das Spiel, solange du eine XOR-Stellung erzwingen kannst. Lediglich im Abschluss variieren beide Varianten minimal.

Die Loesung in dem von TwingO angegebenen Link ist viel
eleganter als meine eigene Loesung, zumal sich meine Loesung
nur auf den Spezialfall mit 3 Streichholzreihen anwenden
laesst.

Für diejenigen, die mit XOR [*1] nichts anfangen können: Der Windows-Taschenrechner (wissenschaftliche Anzeige) übernimmt die Berechnung für euch. Unter Linux macht’s calctool.

Die Wahrscheinlichkeit einer anfaenglichen Verluststellung
nimmt uebrigens exponentiell mit 2^(-n) ab, wobei 2^n die
maximale Zahl an Streichhoelzern einer Reihe ist. Dies sieht
man, wenn man die Loesung von TwingOs Link anschaut. Die
Anzahl an Verluststellungen berechnet sich naemlich zu:
Nv=Summe_{k=0}^{n}(n ueber k)*3^k
=Summe_{k=0}^{n}(n ueber k)*3^k*1^(n-k)
[…]

Um Gottes Willen, ich hab Urlaub, da wird mir das vieeel zu kompliziert. Ich würd’s einfacher ausdrücken: Jede Kombination, die nicht ursprünglich eine XOR-Kombination darstellt, ist eine Gewinnkombination für denjenigen, der das Spiel beginnt. Da es zu zwei Zahlen immer nur ein mögliches XOR-Ergebnis gibt, aber unendlich viele nicht-XORs, geht die Gewinnwahrscheinlichkeit gegen Unendlich.

Da aber in der Praxis die Anzahl der Hölzer begrenzt ist, und das Programm bei fixer Kombination a|b ca. fünf verschiedene c in der Ausgangsstellung erlaubt, liegt die Wahrscheinlichkeit bei etwa 80%.

Gruss,
Schorsch

[1] XOR - exklusives Oder:
Eine Aussage A ist dann wahr, wenn genau eine Teilaussage wahr ist (a|b->A) bzw. dann, wenn die Anzahl der wahren Teilaussagen ungerade ist (a|b|…|n->A)

A xor B =:
wahr xor wahr = falsch
wahr xor falsch = wahr
falsch xor wahr = wahr
falsch xor falsch = falsch

Bezügl. des üblicherweise verwendeten Dezimalsystems sind die Ergebnisse verwirrend. 7 xor 8 = 15, 1 xor 6 = 7, 2 xor 9 = 11… Datt is doch ne normale Addition!!! Ne, eben nicht, denn 6 xor 5 = 3, 6 xor 7 = 1, 11 xor 12 = 7…

Da lässt sich scheinbar kein Zusammenhang erkennen. Dieser ergibt sich erst, wenn die Zahlen binär dargestellt werden:
11(10) xor 12(10) = 1011(2) xor 1100(2) = 0111(2) = 7(10)
2(10) xor 9(10) = 0010(2) xor 1001(2) = b1011(2) = 11(10)

#17

Hallo jns4sen !

Du hast recht. Ich habe nur ein Spiel angeschaut, und das hat zufällig mit einer Verliererposition begonnen. Ich hatte dann angenommen, dass es immer so anfängt, ohne einfach ein zweites Spiel zu probieren.
Mea culpa.

Schöne Grüsse
Christof

Hallo Christof,
wenn das NIM-Spiel im angegebenen Link immer in einer
Verliererposition starten würde, hätte ich den Computer wohl
kaum besiegen können (als Belohnung kommt dann der Schriftzug
„SPITZE!!“)… Für jemanden, der das Spiel zum ersten mal
sieht, ist es alles andere als trivial, eine Gewinnstrategie
zu finden, so dass es sich der Programmierer durchaus leisten
konnte, als Anfangsposition eine Zufallsstellung vorzugeben.
Viele Grüße
Jens

#18

Hallo Hicki,

jetzt bin ich mal so gemein, dir einen Link auf ein ähnliches
Streichholzspiel zu geben, welches du nie gewinnen wirst. Und
auch sonst kaum einer hier aus dem Forum. Aber das Spiel ist
gewinnbar!

Hallo Schorsch, ich hab mir hier die ganze XOR-Geschichte durchgezogen, aber anscheinend bin ich zu blöd dazu.
Aber:
ImhO kann ein Spiel, das mit drei Reihen läuft und jeder kann soviel nehmen, wie er will, mitsamt XOR und Trallala nur von dem, der nicht beginnt, gewonnen werden. Der zweite Spieler - hier der Computer - ist immer in der Lage, es so zu drehen, daß Du zum Schluß als Verlierer dastehst.

Bescheidene Grüße, Fritz

#19

Hi Fritz,

das Spiel mit 3 Reihen kann wohl von dem gewonnen werden, der anfaengt. Der Beweis hierfuer ist extrem einfach. Beweis durch Widerspruch:
Angenommen, es ist wahr, dass derjenige, der anfaengt, immer nur verliert. Dann faengt Spieler A also an und macht irgendeinen Zug. Anschliessend haben wir irgendeine neue Spielposition vorliegen. Diese irgendeine Spielposition koennte nun aber auch als Anfangsposition dienen. Nach Voraussetzung kann diese dann aber nicht gewonnen werden. Folglich hat auch Spieler B eine Verlustposition vorliegen. Da das Spiel aber nach endlich vielen Zuegen zu Ende geht (es muss ja immer mindestens ein Streichholz gezogen werden), und der Ausgang des Spiels immer eindeutig ist (entweder verliert A, dann gewinnt B oder es verliert B, dann gewinnt A), haben wir also einen Widerspruch. Die Voraussetzung muss also falsch sein.

Wenn dir der Beweis zu suspekt sein sollte, dann machen wir doch mal ein Spiel. Die Ausgangsposition sei (2, 5, 8). Ich fange an. Mein Zug lautet: Ich nehme 1 Streichholz vom letzten Stapel, also hast du jetzt die Position (2, 5, 7). Ich warte auf deinen Zug…

Viele Gruesse
Jens

PS: Wie ich weiter unten zeigte, nimmt die Wahrscheinlichkeit, anfangs eine Verlustposition vorzufinden, mit 1/2^n ab, wenn 2^n die Anzahl der maximal zulaessigen Streichhoelzer pro Reihe ist.

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

1 Like
#20

Nehme vom Stapel_1 1 Holz (1,5,7)

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]