Ein Würfelspiel der anderen Art...

Neue Frage »

Mystic Auf diesen Beitrag antworten »
Ein Würfelspiel der anderen Art...
Ich weiß nicht, ob es dieses Rätsel hier schon mal gab, ich finde es jedenfalls ganz nett... Alice und Bob haben beide je 6 Würfeln einer Farbe, z.B. rot für Alice und blau für Bob... Alice und Bob werfen gleichzeitig ihre 6 Würfeln und sie sehen auch beide nicht nur die eigenen Würfel, sondern auch die des anderen, d.h., alles ist offen...

Alice wählt nun aus ihren 6 Würfeln eine k-elementige Teilmenge für ein selbstgewähltes k in {1,2,..,6}, bildet die Augensumme a und gibt diese Bob bekannt... Bob seinerseits bildet für ein selbstgewähltes l in {1,2,...,6} eine l-elementige Teilmenge seiner 6 Würfel und davon die Augensumme b.... Gelingt es ihm seine Würfel so auszuwählen, das b = a ist, so hat er gewonnen, andernfallls Alice...

Die Frage ist nun, wer hat bei diesem Würfelspiel (natürlich bei beiderseits optimalem Spiel in Abghängigkeit von den gefallenen Würfeln) die höheren Gewinnchancen, Alice oder Bob, und wie hoch sind diese?
AD Auf diesen Beitrag antworten »

Es ist wenig überraschend, dass Alice die besseren Siegchancen hat - wenn ich mich nicht verprogrammiert ... ähh, verrechnet habe, dann müssten es so ca. 81.5% sein. Augenzwinkern
Shortstop Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Es ist wenig überraschend, dass Alice die besseren Siegchancen hat - wenn ich mich nicht verprogrammiert ... ähh, verrechnet habe, dann müssten es so ca. 81.5% sein. Augenzwinkern


Wie hast du das Problem so schnell in ein Programm fassen können?
AD Auf diesen Beitrag antworten »

Wahrscheinlich ZU schnell - es ist wohl noch ein Fehler drin - ich arbeite dran. Augenzwinkern
Shortstop Auf diesen Beitrag antworten »

Ich wäre dir für einen kleinen Einblick dankbar, wenn du soweit bist. =)
AD Auf diesen Beitrag antworten »

Einfach BruteForce (auch wenn Mystic sicherlich eine intelligentere Lösung im Sinn hat):

Für jede der Wurffolgen wird die Menge der möglichen Teilsummen vorberechnet (technisch gesehen passt das als Bitmaske in eine 64Bit-Zahl). Und dann wird einfach gezählt, für wieviele der Paare die Bedingung erfüllt ist.

Rechenzeit ca. 10 Sekunden - Programmierzeit etwas länger. Big Laugh
 
 
Mystic Auf diesen Beitrag antworten »

Hm, kann dein Programm auch explizit eine Wurfelfolge für Alice und Bob ausgeben und dazu eine Augensumme a, welche bei bei entsprechender Auswahl von Würfeln durch Alice auch wirklich erzielbar ist, die aber andererseits Bob durch keine Auswahl seiner Würfel erhalten kann?
AD Auf diesen Beitrag antworten »

Prinzipiell schon, aber dazu müsste ich noch das Interface für eine solche Abfrage nachrüsten.
Mystic Auf diesen Beitrag antworten »

Naja, wenn deine Angaben für die Gewinnchancen von Alice sich als richtig herausstellen, müsste sich so ein Beispiel auch leicht von Hand finden lassen...
Louis1991 Auf diesen Beitrag antworten »

Also mal paar Gedankenansätze:

Alice gewinnt immer, wenn ihre Augensumme größer ist als die von Bob (also fast zu 50%)

Alice gewinnt immer, falls ihr kleinstes Würfelergebnis kleiner ist als das kleinste von Bob.

Alice gewinnt immer, wenn sie mindestens eine Ungerade Augenzahl und Bob nur gerade augenzahlen hat.

Ja... gibt bestimmt noch mehr Möglichkeiten, und allein das oben ist mir jetzt zu viel zum Denken. Bin ein wenig im Stress, und Kombinatorik ist leider nicht mein Mustergebiet unglücklich
AD Auf diesen Beitrag antworten »

@Mystic

Ich kann dir nicht folgen - Beispiel???

Wie du willst, obwohl ich den Sinn dahinter ernstlich anzweifle: Na z.B. Alice sechsmal die 6, und sie wählt auch alle die aus, während Bob irgendeine andere Wurffolge hat. Offenbar kann Bob dann die 36 nicht erreichen.
Mystic Auf diesen Beitrag antworten »

Ja, ich habe mich da furchtbar vertan, sorry... unglücklich

Die Gechichte geht eigentlich so, dass Alice durch eine entsprechende Auswahl ihrer Würfel Bob den Sieg zukommen lassen will (aus welchen Gründen auch immer)... Eigentlich geht es darum, ob dies immer möglich ist...

Aber es macht ja auch die ursprüngliche Aufgabe durchaus Sinn, wenngleich ich die erst selber rechnen muss... geschockt
AD Auf diesen Beitrag antworten »

Ja, irgend sowas hatte ich mir schon gedacht, wegen der Wirrheit deiner Einwürfe.
AD Auf diesen Beitrag antworten »

Ok, mal zu deinem anderen Spiel, wo Alice unbedingt Bob gewinnen lassen will - und dies auch schafft. In dem Kontext

Zitat:
Original von Arthur Dent
Für jede der Wurffolgen wird die Menge der möglichen Teilsummen vorberechnet (technisch gesehen passt das als Bitmaske in eine 64Bit-Zahl).

heißt das dann einfach, dass für alle gilt. Per BruteForce wieder kein Problem, das nachzuweisen - aber du bist sicher auf den Dreh aus, dass man es auch einfacher sieht.

Jedenfalls scheint essentiell zu sein, dass es 6 Würfe sind. Bei 5 Würfen und in der Konstellation

Alice 5,5,5,5,5
Bob 6,6,6,6,6

kann Alice jedenfalls Bob nicht gewinnen lassen...
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
[....]heißt das dann einfach, dass für alle gilt. Per BruteForce wieder kein Problem, das nachzuweisen - aber du bist sicher auf den Dreh aus, dass man es auch einfacher sieht.

Ja, dieses Ergebnis stimmt zunächst einmal... Freude

Wie du richtig vermutest, kann man das auch rein durch Überlegung zeigen, wobei in dem Beweis, den ich kenne, das Schubfachprinzip eine wichtige Rolle spielt... Ich sag dazu vorläufig nicht mehr dazu, vielleicht willst ja du oder jemand anderer sich noch daran versuchen...

Zitat:
Original von Arthur Dent
Jedenfalls scheint essentiell zu sein, dass es 6 Würfe sind. Bei 5 Würfen und in der Konstellation

Alice 5,5,5,5,5
Bob 6,6,6,6,6

kann Alice jedenfalls Bob nicht gewinnen lassen...

Ja richtig, wenn man "verallgemeinerte Würfel" mit n Flächen und den Augenzahlen 1,2,..,n betrachtet, dann funktioniert das mit weniger als je n Würfeln (oder n Würfen mit nur einem Würfel, was ja keinen Unterschied macht) nicht mehr...
AD Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
wobei in dem Beweis, den ich kenne, das Schubfachprinzip eine wichtige Rolle spielt...

Das hatte ich schon vermutet, weil ich eine Reihe ähnlicher Probleme kenne. Allerdings bin ich wohl heute zu blockiert, um die passenden Elemente benennen zu können, auf die das Schubfachprinzip angewandt hier die Lösung bringt - vielleicht morgen mehr. Augenzwinkern


Die (bisher) beste meiner Ideen klappt leider erst für Würfel je Spieler:

Dann würde ich die Augensummen



für und betrachten. Diese Summen bewegen sich im Bereich . Nun ist , also sind zwei der Summen gleich . Mit O.B.d.A. folgt , und es ist dann



die gewünschte Teilsummengleichheit.

Mir ist natürlich klar, dass man sich bei diesem Konstruktionsprinzip auf nur einen Teil der Teilsummen einengt, nämlich die mit aufeinanderfolgenden Indizes, und damit eine Menge Information einfach nicht nutzt. Allerdings fehlt mir die Idee, wie ich diesem Makel beheben könnte. verwirrt
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Mir ist natürlich klar, dass man sich bei diesem Konstruktionsprinzip auf nur einen Teil der Teilsummen einengt, nämlich die mit aufeinanderfolgenden Indizes, und damit eine Menge Information einfach nicht nutzt. Allerdings fehlt mir die Idee, wie ich diesem Makel beheben könnte. verwirrt


Ja, ich würde sagen, du bist auf der richtigen Spur... Augenzwinkern

Die Sache mit den aufeinanderfolgenden Indizes ist jetzt nicht wirklich ein Problem, denn selbst mit dieser einschränkenden Bedingung ist es noch lösbar... Dieser "Makel" haftet auch der Lösung an, welche ich kenne... Ich sehe das Problem eher darin, dass du "zuviele" Schubfächer hast, nämlich 12n+1 Stück...

Ich würde unter der Voraussetzung



daher eher die Definition



(k=1,2,...,n, m=0,1,2,...,n) verwenden und von vornherein nur die Schubfächer mit den Zahlen 0,1,2,...,n-1 betrachten, wobei S(k,m), die da nicht "reinpassen", einfach weggeworfen werden...
AD Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
und von vornherein nur die Schubfächer mit den Zahlen 0,1,2,...,n-1 betrachten, wobei S(k,m), die da nicht "reinpassen", einfach weggeworfen werden...

Also irgendwie blicke ich noch nicht durch: Wie begründest du, dass immer noch mindestens n+1 Werte nicht weggeworfen werden, also in den Schubladen landen? verwirrt


EDIT: ... Ah, Ok, ich hab's. Augenzwinkern

Für festes ist und sowie . Also gibt es zu jedem mindestens ein mit .
Mystic Auf diesen Beitrag antworten »

Naja, man muss da schon eine kleine Fallunterscheidung machen... Wenn eine der Differenzen in das Schubfach 0 fällt, ist man ja fertig, ansonsten braucht man ja nur n Objekte und nicht n+1, die auch wirklich in die verbleibenden Schubfächer 1,2,..,n-1 "passen" ...

Edit: Sorry, habe dein edit nicht rechtzeitig gesehen...
AD Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Wenn eine der Differenzen in das Schubfach 0 fällt, ist man ja fertig

Wobei man da aber ausnehmen müsste. Aber es ist ja auch gar nicht nötig, die 0 extra zu behandeln. Augenzwinkern
Mystic Auf diesen Beitrag antworten »

Ja, habe ich jetzt auch gesehen... Augenzwinkern

Ansonsten habe ich dieses Rätsel aus diesem Büchlein von Peter Winkler, das auch sonst sehr empfehlenswert ist... Leider ist mir bei der "Einkleidung", welche von mir stammt, dann ein Mißgeschick passiert, wofür ich nochmals um Entschuldigung bitte...

Edit: Übrigens habe ich S(0,0) oben "in weiser Voraussicht" gar nicht erst zugelassen...
Mystic Auf diesen Beitrag antworten »

Eine abschließende Bemerkung noch zur ursprünglichen Aufgabe...

Zitat:
Original von Arthur Dent
Einfach BruteForce (auch wenn Mystic sicherlich eine intelligentere Lösung im Sinn hat):

Für jede der Wurffolgen wird die Menge der möglichen Teilsummen vorberechnet (technisch gesehen passt das als Bitmaske in eine 64Bit-Zahl). Und dann wird einfach gezählt, für wieviele der Paare die Bedingung erfüllt ist.

Rechenzeit ca. 10 Sekunden - Programmierzeit etwas länger. Big Laugh

Imho braucht man sich statt der Wurffolgen jeweils nur die 462 monotonen Wurffolgen anzusehen, was immerhin um mehr als den Faktor 100 (ingesamt also dann um mehr als den Faktor 10000) weniger Aufwand ist... Sonst fällt mir jetzt eigentlich auch nichts an Verbesserungen ein (zumal ich ja wie gesagt auch eine ganz andere Aufgabe im Sinn hatte)...

Ich habe das auch in Derive mal schnell überprüft und komm damit auf das Ergebnis



was also dann auch Arthur's obiges Resultat bestätigt...
AD Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Imho braucht man sich statt der Wurffolgen jeweils nur die 462 monotonen Wurffolgen anzusehen, was immerhin um mehr als den Faktor 100 (ingesamt also dann um mehr als den Faktor 10000) weniger Aufwand ist...

...allerdings mit erhöhtem Verwaltungsaufwand: Schließlich besitzen die monotonen Wurffolgen unterschiedliche Auftrittswahrscheinlichkeiten, je nach dem Grad des Mehrfachauftretens diverser Augenzahlen. Das will auch erst mal alles programmiert sein. Augenzwinkern

Bei mehr als 6 Würfen pro Spieler mag das dann eine lohnende Modifikation (hinsichtlich Programmier- + Laufzeit) sein - hier bei 6 Würfen m.E. noch nicht. Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »