Lösung Aufgabge 19

[Anonymous]

Von hinten aufrollen und einige LGS lösen – schöne Aufgabe!! – Lösung hat gerade so auf
eine Seite gepasst:
https://www.dropbox.com/s/xvystj9nvp2o8c9/19_Casino_Resing.JPG?dl=0

[Anonymous]

Ich meine, ein implizites Bildungsgesetz für den zu setzenden Einsatz gefunden zu haben, konnte das allerdings weder in ein explizites Bildungsgesetz umwandeln, noch einen allgemeinen Beweis für die Richtigkeit finden.

Sei d die Anzahl der noch vorhandenen »Doppelt«-Karten und n die Anzahl der »Nichts«-Karten. Dann definieren wir die zwei Funktionen Z(d,n) und N(d,n) wie folgt: (Z und N stehen für Zähler und Nenner)

Für d>0 gilt Z(d,0) = 1 und N(d,0) = 1.
Für n>0 gilt Z(0,n) = 0 und N(0,n) = 2^n.

Für d>0 und n>0 definieren wir implizit:

Z(d,n) = Z(d-1,n) + Z(d,n-1)
N(d,n) = N(d-1,n) + N(d,n-1)

Der zu setzende Einsatz bei d »Doppelt«- und n »Nichts«-Karten beträgt dann Z(d,n)/N(d,n).

Für den Gewinn gibt es ein ähnliches Bildungsgesetz, die Startwerte lauten hier:

Z(d,0) = 2^d
N(d,0) = 1
Z(0,n) = 2^n
N(0,n) = 2^n

Die Werte stimmen komplett mit denen von Pierrot überein (abgesehen davon, daß die Brüche nicht gekürzt werden dürfen, sonst funktioniert es nicht mehr), ich vermute, daß auch für größere Werte für d und n die korrekten Ergebnisse rauskommen, konnte dafür aber wie gesagt keinen Beweis finden. Falls irgendjemand einen Beweis findet, wäre ich sehr an selbigem interessiert.

[Anonymous]

Verstehe nicht, welchen Beweis du noch brauchst. Der Grinch minimiert in jedem Zug den Gewinn von Ruprecht. Und da Ruprecht das weiss, nimmt er den Einsatz so, dass er damit den maximalen Gewinn hat. Und das ist dann der Fall, wenn der Gewinn für beide Karten gleich ist. Das kann man rekursiv schreiben, so wie von euch beiden schon getan. Und daher kann man sich an das Problem herantasten, indem man es sich mit kleineren Mengen an Startkarten überlegt. Und man braucht eh die Werte für D=0 und für N=0.

[Anonymous]

Ich bin die Lösung pragmatisch angegangen. Das mit der Rundung (ungefähr) hab ich als “Nebelkerze” interpretiert, denn bei solchen Aufgaben wurde auch in den letzten Jahren stets ganze Beträge gesetzt.
Wenn dem so ist, dann hab ich mir einen der beiden Extremfälle angeschaut: Wenn der Grinch zuerst alle
NICHTS – Karten spielt, dann kann Rupprecht, den dann noch übrigen Betrag verachtfachen. Da ich nach einer Lösung suche bei der an allen “Ausgängen” der gleiche Betrag steht, muss der Betrag also durch 8 teilbar sein. Dies ist bei den 10 angebotenen Beträgen nur zweimal der Fall: 256 und 288
Also habe ich den größeren der beiden Beträge ins Auge gefasst (wenn der geht, brauche ich mich um den anderen nicht mehr zu kümmern).
Dann muss Rupprecht eine Strategie wählen, die nach dem Spielen von je einer NICHTS und einer DOPPELT- Karte den gleichen Betrag liefert, egal welche der beiden Karten der Grinch zuerst einsetzt.
Sei x der noch vorhandene Betrag und y der Betrag der gesetzt wird.
Das führt auf eine einfache lineare Gleichung: x + y = 2*(x – y) ==> 3y = x ==> y = x/3
Rupprecht setzt also beim zweitletzten Zug (falls noch je eine Karte übrig ist) genau 1/3 seines Restbetrages. Wenn man dann die linke Hälfte des Baumes (die Hälfte bei der Grinch als erste Karte eine NICHTS- Karte spielt) von unten nach oben ausfüllt, dann ergeben sich wegen des 1.Zuges automatisch “Zwangszüge” für die rechte Hälfte des Baumes, die man dann ebenfalls von unten nach oben ausfüllt.
Und das hat für 288 geklappt. (um eventuelle nicht ganze Einsätze hab ich mir keinen Kopf gemacht).

[Anonymous]

Es gibt für jede Möglichkeit von d “Doppelt”- und n “Nichts”-Schildern, die der Grinch noch hat, einen Faktor a(d,n), sodass Knecht Ruprecht seinen Startbetrag b auf a(d,n)*b vervielfachen kann. In jedem Schritt sollte sein Einsatz e dann folgende Gleichung erfüllen

a(d-1,n)*(b+e) = a(d,n-1)*(b-e)

Der Geldbetrag am Ende sollte also gleich sein, egal ob der Grinch D oder N legt.
Die Gleichung lässt sich nach e auflösen und dieses e in eine Seite einsetzen, um im daraus resultierende Ausdruck den Faktor a(d,n) abzulesen.
Es gilt

a(d,n) = 2*a(d-1,n)*a(d,n-1) / (a(d-1,n)+a(d,n-1))

Zusammen mit den Startwerten a(d,0)=2^d und a(0,n)=1 lassen sich dann alle Faktoren rekursiv berechnen.

[Anonymous]

@Pierrot. Magst du deine Lösung nochmal erklären? Ich verstehe noch nicht wieso du die einzelnen Faktoren jeweils in den weiteren Schritt einsetzt. Auch die notierten rekursiven Folgen sind mir noch zu abstrakt. Vielleicht kann mir diese auch noch wer versuchen zu erklären.

[Anonymous]

Der Grinch hat (d, n) Karten. Ruprecht hat r Geld und setz den Einsatz w.
Der Grinch kann Karte D oder N spielen. Wenn er D spielt, hat er statt (d, n) nur noch (d-1,n) und Ruprecht bekommt w. Wenn er N spielt, hat er statt (d, n) nur noch (d,n-1) und Ruprecht bekommt -w. Nach dem Zug hat Ruprecht also entweder r+w oder r-w.
Ruprecht setzt so, dass er den maximalen Gewinn bekommt, aber er weiss, dass der Grinch so spielt, dass er minimal verliert.
Natürlich ist r+w größer als r-w, aber man landet auf unterschiedlichen Zuständen (d, n), und da es nur eine endliche Zahl Karten gibt, lohnt es sich für den Grinch D zu spielen, wenn der Einsatz w klein genug ist.

Das ganze kann man am besten von den Kanten bestimmen. Für n=0 ist Ruprecht klar, dass grinch nur D spielen kann, und wird alles setzen. Er hat also r*2^d nach den d Spielzüge.
Für d=0 ist Ruprecht klar, dass grinch nur N spielen kann, und wird nichts setzen. Er hat also r nach den d Spielzüge.
Mit den Randbedingungen stellt man eine matrix g(d, n) auf. Für die Züge des grinch gilt nun, wenn er D spielt g(d-1,n)+w, bzw wenn er N spielt g(d,n-1)-w. Ruprecht setzt so, dass er seinen Gewinn maximiert, was der Fall ist, wenn beide Zahlen gleich sind (es also für ihn egal ist, ob grinch D oder N spielt). Und so kann man die matrix bis g(3,3) füllen.

[Anonymous]

Hi Kosakenzipfelchen,
vielen Dank. Nun habe ich die ganzen Variablen einwandfrei verstanden. Zwei Fragen bleiben mir noch: Du schreibst eine Matrix. Wie sieht die denn aus und wie genau komme ich denn nun auf die Lösung?

[Anonymous]

Also korrekter wäre wohl die Bezeichnung array gewesen. g(d, n) ist einfach zweidimensional, mit “Koordinaten” d und n. Und wenn man den Rand hat, kann man successive n und d erhöhen, bis zu d=3 und n=3. Oder wenn man spass hat auch darüberhinaus.
Den Arrayinhalt kann ich nicht posten; ich hab mit dem dienstrechner gerechnet und grad hab ich Urlaub.
Man kann in dem array den Betrag in Euro speichern, oder, da der startwert immer als multiplikativer Term drinsteckt nur den Faktor ohne 189.
Im ersten Fall steht in g(3,3) direkt die Lösung 288.

[Anonymous]

Kann ich mir g wie eine Funktion vorstellen mit zwei Variablen? Vielleicht könntest du mit der Schreibweise noch zwei Rechnungen zum Ziel ausführen. Ich vermute, dass es mir dann klarer werden würde.

[Anonymous]

Ich weiß nicht, ob dir das hilft, aber ich habe es mir so notiert:
G(d,n) ist der Gewinn, den ich maximal erreichen kann, wenn der Grinch noch d “doppelt” und n “nichts” Karten hat, als Faktor auf das Budget, das ich zu dem Zeitpunkt habe. Das ist also eine zweidimensionale Funktion.

Zum Beispiel ist, wie auch oben erwähnt, G(1,0)=2 und G(0,1)=1. (In einem Fall setze und verdoppele ich alles, im anderen Fall setze und verliere ich nichts)

Wenn ich p setze, kann der Grinch dann entscheiden, ob er verdoppelt, also geht es mit (1+p)*G(d-1, n) weiter, oder nichts spielt, dann geht es mit (1-p)*G(d, n-1) weiter. Die beiden müssen in einer optimalen Strategie gleich sein (die eine ist monoton steigend, die andere fallend in p, also wird das Minimum der beiden größer, wenn ich p für das kleinere der beiden vorteilhaft ändere, was immer geht, und die beiden nähern sich an)
Die Gleichheit der beiden ist dann im Prinzip auch schon der ganze Beweis, der Rest ist wie gesagt die Rekursion, die durchgerechnet wird.

[Anonymous]

Das habe ich alles verstanden und das leuchtet mir auch alles ein. Ich weiß einfach nicht, wie ich die Rekursion dann nach dem ersten Bestimmen von p, also p=1/3 weiterrechnen kann.

[Anonymous]

Ah ok.
Du hast also herausbekommen, dass bei (1,1) 1/3 eingesetzt werden sollte, also dass G(1,1) = 4/3.
Du weißt außerdem, dass G(0,2) = 1, kannst also für die Berechnung von G(1,2) das p so wählen, dass G(1,2) = (1-p)*G(1,1) = (1+p)*G(0,2), also
(1-p)*4/3=(1+p)*1, also
1/3 = 7/3*p, also
p = 1/7
Und damit
G(1,2) = 8/7

Danach kannst du mit G(1,3) weitermachen, das gleiche auch mit G(2,1),…
Das wäre dann das Ausfüllen der Zeilen/Spalten

[Anonymous]

Jetzt habe ich es gecheckt. Vielen Dank. Ich schreibe es dann mal sauber auf 😉

[Author]

Posts