Ein Würfelspiel der anderen Art... |
22.07.2010, 16:26 | Mystic | Auf diesen Beitrag antworten » | ||||
Ein Würfelspiel der anderen Art... 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? |
||||||
22.07.2010, 17:13 | 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. |
||||||
22.07.2010, 17:19 | Shortstop | Auf diesen Beitrag antworten » | ||||
Wie hast du das Problem so schnell in ein Programm fassen können? |
||||||
22.07.2010, 17:23 | AD | Auf diesen Beitrag antworten » | ||||
Wahrscheinlich ZU schnell - es ist wohl noch ein Fehler drin - ich arbeite dran. |
||||||
22.07.2010, 17:26 | Shortstop | Auf diesen Beitrag antworten » | ||||
Ich wäre dir für einen kleinen Einblick dankbar, wenn du soweit bist. =) |
||||||
22.07.2010, 17:35 | 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. |
||||||
Anzeige | ||||||
|
||||||
22.07.2010, 17:54 | 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? |
||||||
22.07.2010, 17:56 | AD | Auf diesen Beitrag antworten » | ||||
Prinzipiell schon, aber dazu müsste ich noch das Interface für eine solche Abfrage nachrüsten. |
||||||
22.07.2010, 18:05 | 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... |
||||||
22.07.2010, 18:11 | 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 |
||||||
22.07.2010, 18:12 | 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. |
||||||
22.07.2010, 18:28 | Mystic | Auf diesen Beitrag antworten » | ||||
Ja, ich habe mich da furchtbar vertan, sorry... 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... |
||||||
22.07.2010, 18:29 | AD | Auf diesen Beitrag antworten » | ||||
Ja, irgend sowas hatte ich mir schon gedacht, wegen der Wirrheit deiner Einwürfe. |
||||||
22.07.2010, 21:50 | 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
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... |
||||||
22.07.2010, 23:12 | Mystic | Auf diesen Beitrag antworten » | ||||
Ja, dieses Ergebnis stimmt zunächst einmal... 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...
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... |
||||||
22.07.2010, 23:16 | AD | Auf diesen Beitrag antworten » | ||||
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. 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. |
||||||
23.07.2010, 11:26 | Mystic | Auf diesen Beitrag antworten » | ||||
Ja, ich würde sagen, du bist auf der richtigen Spur... 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... |
||||||
23.07.2010, 11:35 | AD | Auf diesen Beitrag antworten » | ||||
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? EDIT: ... Ah, Ok, ich hab's. Für festes ist und sowie . Also gibt es zu jedem mindestens ein mit . |
||||||
23.07.2010, 11:45 | 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... |
||||||
23.07.2010, 12:02 | AD | Auf diesen Beitrag antworten » | ||||
Wobei man da aber ausnehmen müsste. Aber es ist ja auch gar nicht nötig, die 0 extra zu behandeln. |
||||||
23.07.2010, 12:15 | Mystic | Auf diesen Beitrag antworten » | ||||
Ja, habe ich jetzt auch gesehen... 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... |
||||||
25.07.2010, 21:21 | Mystic | Auf diesen Beitrag antworten » | ||||
Eine abschließende Bemerkung noch zur ursprünglichen Aufgabe...
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... |
||||||
25.07.2010, 21:30 | AD | Auf diesen Beitrag antworten » | ||||
...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. 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. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |
|