#2 Auktionsspiel < Knobelaufgaben < Café VH < Internes < Vorhilfe
|
| Aufgabe | Knobelaufgabe #2 Auktionsspiel [mm] (\bigstar\bigstar\bigstar\bigstar\bigstar) [/mm]
Zwei Spieler A und B starten mit einem nichtnegativen ganzzahligen Geldbetrag. In jeder Runde wird ein Spielstein zur Auktion gestellt. A macht als erstes ein Gebot. Dann hat B genau zwei Möglichkeiten. Erstens: Er überbietet das Gebot von A um 1 und gewinnt so den Spielstein. Zweitens: Er passt (bietet 0) und überlässt A den Spielstein.
Am Ende jeder Runde verlieren beide Spieler das Geld, das sie gesetzt haben.
Sobald ein Spieler drei Spielsteine mehr als der andere hat, gewinnt dieser das Spiel. Auf diese Weise ist ein Remis nicht ausgeschlossen.
Offenbar hat B einen gewissen Vorteil gegenüber A, da ihm stets bekannt ist, was A geboten hat.
B hat zu Beginn 100 Geldstücke. Wie viel Geld benötigt A mindestens um eine Gewinnstrategie entwickeln zu können? |
Liebe Forumsgemeinde,
hier ist die zweite Knobelaufgabe. Jeder der sich daran probieren möchte, ist wieder herzlich dazu eingeladen.
Meiner Einschätzung nach ist diese Aufgabe ziemlich schwierig. Mir liegt auch nur eine computergestützte Lösung vor (was die Bezeichnung Knobelaufgabe noch in Frage stellt). Vielleicht schafft es ja ein Forenmitglied, diese Aufgabe auf mathematischem Wege zu lösen.
Einige interessante weitere Fragen zur Aufgabe:
Zu dieser 'Knobelaufgabe' stellt sich allgemein eine ganze Klasse von Problemen der folgenden Art: Angenommen B besitzt zu Beginn den Geldbetrag n. Was ist der minimale Betrag, den A zu Beginn haben muss, damit A eine Gewinnstrategie hat?
Lässt sich eine Struktur der Gewinnstrategien erkennen?
usw.
Viel Erfolg!
Liebe Grüße
[mm] \rule{\textwidth}{0.3pt}
[/mm]
[mm] \hspace{5pt}\footnotesize
[/mm]
[mm] \textit{Ältere Knobelaufgaben der Serie:}
[/mm]
[mm] \bigstar\bigstar:[/mm] 1
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:24 So 05.06.2011 | | Autor: | kamaleonti |
Liebe Rätselfreunde,
da die Knobelaufgabe offenbar etwas zu schwer ist, sei zu Vereinfachung nur nach einer Gewinnstrategie für eine Sieghöhe von 2 gefragt. Das heißt, ein Spieler, der zwei Spielsteine mehr als der andere hat, gewinnt das Spiel.
Nun ist zu fest vorgegeben Startbetrag |B| von B gefragt (sei etwa |B|=100), welchen Betrag A minimal benötigt, um eine Gewinnstrategie zu entwickeln.
Tipp: Hier spielen die Fibonaccizahlen eine bedeutende Rolle.
LG
|
|
|
| |
|
> Zwei Spieler A und B starten mit einem nichtnegativen
> ganzzahligen Geldbetrag. In jeder Runde wird ein Spielstein
> zur Auktion gestellt. A macht als erstes ein Gebot. Dann
> hat B genau zwei Möglichkeiten. Erstens: Er überbietet
> das Gebot von A um 1 und gewinnt so den Spielstein.
> Zweitens: Er passt (bietet 0) und überlässt A den
> Spielstein.
Am Ende jeder Runde verlieren beide Spieler das Geld, das
sie gesetzt haben. (!!!)
>
> Sobald ein Spieler drei zwei Spielsteine mehr als der andere
> hat, gewinnt dieser das Spiel. (abgeänderte Version)
> B hat zu Beginn 100 Geldstücke. Wie viel Geld benötigt A
> mindestens, um eine Gewinnstrategie entwickeln zu können?
Hallo, ich habe nun diese Aufgabe noch entdeckt und
versuche mal ein mögliches Beispiel eines Spielver-
laufs zu skizzieren.
Das Anfangskapital von A sei N €
Setzt A nun etwa in der ersten Runde [mm] $a_1=50$€ [/mm] , so hat
B die Möglichkeiten:
1.) [mm] b_1=51
[/mm]
Damit reduziert sich das Vermögen von B auf 49€ , und
er erwirbt dafür seinen ersten Stein. Aber auch A verliert
gemäß Spielregel seinen Einsatz und hat nur noch (N-50)€ .
2.) [mm] b_1=0
[/mm]
B behält sein Vermögen von 100€
A hat noch (N-50)€ und seinen ersten Stein.
Im ersten Fall muss A, um einen Gewinn von B zu verhindern,
das Minimalgebot von 49€ setzen, welches von B nicht über-
boten werden kann. B muss passen und A erwirbt seinen ersten
Stein. Sein Kapital beträgt noch (N-99)€. In der dritten Runde
kann er dann nochmals 49€ einsetzen (sofern er überhaupt
noch so viel besitzt) und gewinnt das Spiel.
Voraussetzung: [mm] N\ge148.
[/mm]
Im zweiten Fall gewinnt A mit Sicherheit, falls er nun direkt
100€ einsetzt und den zweiten Stein kauft, ohne dass ihn
B überbieten kann. Dieser Weg ist möglich, falls [mm] N\ge150.
[/mm]
Man sieht also: Mit [mm] N\ge150 [/mm] gibt es für A jedenfalls eine
sichere Gewinnstrategie.
Aber: das skizzierte Beispiel ist möglicherweise noch nicht
optimal. Im obigen 2. Fall könnte ja A in der zweiten Runde
ein Gebot machen, welches B zum Kauf verlockt. A könnte
darauf seinen zweiten Stein billiger erwerben ...
Auch der erste Einsatz von A ist möglicherweise mit [mm] $a_1=50$€
[/mm]
noch nicht optimal ...
Insgesamt also eine wirklich spannende Aufgabe !
LG Al-Chw.
Edit: Gerade habe ich noch einen Denkfehler in meiner
obigen Argumentation entdeckt. Um zu gewinnen, muss man
ja nicht nur zwei Steine erwerben, sondern zwei mehr als
der Gegenspieler. Hat also B den ersten Stein, so muss A
insgesamt nicht nur 2, sondern mindestens 3 Steine erwerben.
Damit werden die obigen Rechnungen wenigstens teilweise
hinfällig ...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:59 Sa 30.07.2011 | | Autor: | kamaleonti |
Hallo Al,
ja, das ist eine sehr spannende Aufgabe. So spannend, dass ich noch heute Nacht eine Antwort tippen musste. Es ist aber weniger eine Knobelaufgabe, sondern ein richtiges Problem. 
Ich will nun einige Überlegungen zum Spiel mit Sieghöhe 2 hier vortragen:
Es sei f(n) die Folge der Fibonaccizahlen (d. h. f(1)=1, f(2)=1, f(3)=2, usw.).
Behauptung:
Es gibt eine Gewinnstrategie für A, wenn A Startkapital f(n+1) und B Startkapital f(n) hat.
Beweis:
Den Beweis kann man mittels Induktion führen.
Den Fall n=1 handelt man leicht ab, denn dann hat A Startkapital f(1+1)=2 und B Startkapital 1. Um zu gewinnen setzt A zweimal hintereinander eine Geldeinheit. B kann nicht überbieten, weswegen A gewinnt.
Nun schauen wir uns den Induktionsschritt an. Diesen machen wir von n-1 zu n. Dann hat A also Startkapital f(n+1) und setzt f(n-1) beim Stand von 0-0. Neues Kapital von A ist dann f(n+1)-f(n-1)=f(n).
Es hat B zwei Möglichkeiten zu reagieren. Erstens B passt. Dann gewinnt A durch Setzen seines restlichen Kapitals f(n) sofort, denn B kann dies nicht überbieten.
Also muss B überbieten und wendet dafür Kapital f(n-1)+1 auf. Danach hat B allerdings nur noch Kapital [mm] f(n)-f(n-1)-1\leq [/mm] f(n-2) und der Spielstand ist 0-1 aus Sicht von A. Es gleicht A nun sicher aus und setzt f(n-2). Danach steht es also wieder ausgeglichen 1-1 und neues Kapital von A ist f(n)-f(n-2)=f(n-1) und das neue Kapital von B ist kleiner als f(n-2). Damit folgt die Behauptung aus der Induktionsannahme.
Es ist relativ offensichtlich, dass dieser Beweis noch keine optimale Strategie liefert:
A könnte im Induktionsschritt zum Beispiel auch nur f(n-2)-1 setzen und würde beim Rückstand schon ausgleichen. (Dieser Punkt hat mich öfters dazu gebracht zu überlegen, ob es nicht sinnvoller ist, die Regeln dahingehend zu ändern, dass B schon durch 'Gleichziehen' mit dem Gebot von A gewinnt...).
Weiterhin gewinnt A bei den aktuellen Regeln zum Beispiel auch schon beim Spielstand 0-1, wenn A und B beide noch Kapital 0 haben.
Offenbar sind diese Sachen aber alle asymptotisch vernachlässigbar, wie die folgende Grafik aus den Daten meines Computerprogramms zeigt:
[Dateianhang nicht öffentlich]
Die ermittelten minimalen Werte des Startkapitals #MinA(B) von A im Verhältnis zum Startkapital #B von B liegen für große #B sehr nahe beim goldenen Schnitt [mm] \blue{\Phi}. [/mm] Das fand ich ziemlich erstaunlich. Aber wen überraschts - der taucht ja beinahe überall auf . Weiterhin der Grafik zu entnehmen ist das Verhältnis des ersten Zugs von A zum jeweiligen #B. Dieses schmiegt sich asymptotisch an [mm] 1/\Phi. [/mm] Beides entspricht asymptotisch der oben angegebenen Strategie.
Viel mehr habe ich momentan leider nicht zur Aufgabe mit Sieghöhe 2. Ich bin auf eventuelle Meinungen dazu sehr gespannt.
Übrigens ist das minimale Kapital, das A im Spiel mit Sieghöhe 2 für eine Gewinnstrategie benötigt, 159 Geldeinheiten. Das hat zumindest mein Programm ausgerechnet
LG
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
Hallo kamaleonti,
kommt "kamaleonti" eigentlich von "Chwamäleon" ? Dann sind
wir ja möglicherweise verwandt ...
Nach der Fibonacci-Idee gibt es im Fall #B=8 für A eine
sichere Gewinnstrategie, wenn #A=13 (nächstgrößere
Fibonaccizahl). Wenn ich mich nicht verrechnet habe, kann
A aber auch noch mit dem Startkapital 12 sicher gewinnen,
wenn er zuerst einen Einsatz von 4 macht. B muss ihn
überbieten, wenn er nicht sogleich verlieren will. In der
zweiten Runde soll dann A den Einsatz 3 machen, den B
nicht überbieten kann. In der ditten Runde setzt A 2.
Wie immer B darauf reagiert, A kann noch sicher gewinnen.
Sagt das dein Programm auch ?
Noch eine Detailfrage: A muss doch stets einen Einsatz
von mindestens 1 machen, oder ? Sonst könnte er ja
dann, wenn B pleite ist, Steine kostenlos abräumen ...
LG Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:39 Fr 05.08.2011 | | Autor: | kamaleonti |
Hallo Al,
> kommt "kamaleonti" eigentlich von "Chwamäleon" ? Dann sind
> wir ja möglicherweise verwandt ...
"Kamaleonti" ist maltesisch und heißt zu deutsch Chamäleon. Es gibt einen Jazz-Standard von Herbie Hancock (pno.), der so heißt. Allerdings auf Englisch: "Chameleon". Diese 'Nummer' hat es mir schon lange angetan und ich habe mir nicht weniger als drei Versionen davon besorgt (die vierte spiele ich mit meinem Trio ).
Wenn du eine Vorstellung davon willst, kannst du ja mal auf youtube danach suchen, obwohl ich die Versionen dort eher unschön finde.
> Noch eine Detailfrage: A muss doch stets einen Einsatz
> von mindestens 1 machen, oder ? Sonst könnte er ja
> dann, wenn B pleite ist, Steine kostenlos abräumen ...
Mein ursprüngliches Programm hat zugelassen, dass A Null setzt. In diesem Fall erhält man für #B=100 Minimalkapital von A in Höhe von 159.
Ich habe jetzt noch ein neues Programm geschrieben, für den Fall, dass A nicht Null bieten darf. Ich finde diese Regeländerung nun auch besser. Man interessiert sich ja nur für Kapitale von A, wo es eine Gewinnstrategie gibt, sodass alle anderen Spielausgänge (z. B. Remis) irrelevant sind.
Ich werde gleich in einer anderen Mitteilung meinen Quellcode posten.
LG
|
|
|
| |
|
> Hallo Al,
>
> ja, das ist eine sehr spannende Aufgabe. So spannend, dass
> ich noch heute Nacht eine Antwort tippen musste. Es ist
> aber weniger eine Knobelaufgabe, sondern ein richtiges
> Problem.
>
> Ich will nun einige Überlegungen zum Spiel mit Sieghöhe 2
> hier vortragen:
>
> Es sei f(n) die Folge der Fibonaccizahlen (d. h. f(1)=1,
> f(2)=1, f(3)=2, usw.).
> Behauptung:
> Es gibt eine Gewinnstrategie für A, wenn A Startkapital
> f(n+1) und B Startkapital f(n) hat.
> Beweis:
> Den Beweis kann man mittels Induktion führen.
> Den Fall n=1 handelt man leicht ab, denn dann hat A
> Startkapital f(1+1)=2 und B Startkapital 1. Um zu gewinnen
> setzt A zweimal hintereinander eine Geldeinheit. B kann
> nicht überbieten, weswegen A gewinnt.
> Nun schauen wir uns den Induktionsschritt an. Diesen
> machen wir von n-1 zu n. Dann hat A also Startkapital
> f(n+1) und setzt f(n-1) beim Stand von 0-0. Neues Kapital
> von A ist dann f(n+1)-f(n-1)=f(n).
>
> Es hat B zwei Möglichkeiten zu reagieren. Erstens B passt.
> Dann gewinnt A durch Setzen seines restlichen Kapitals f(n)
> sofort, denn B kann dies nicht überbieten.
> Also muss B überbieten und wendet dafür Kapital f(n-1)+1
> auf. Danach hat B allerdings nur noch Kapital
> [mm]f(n)-f(n-1)-1\leq[/mm] f(n-2) und der Spielstand ist 0-1 aus
> Sicht von A. Es gleicht A nun sicher aus und setzt f(n-2).
> Danach steht es also wieder ausgeglichen 1-1 und neues
> Kapital von A ist f(n)-f(n-2)=f(n-1) und das neue Kapital
> von B ist kleiner als f(n-2). Damit folgt die Behauptung
> aus der Induktionsannahme.
>
>
> Es ist relativ offensichtlich, dass dieser Beweis noch
> keine optimale Strategie liefert:
> A könnte im Induktionsschritt zum Beispiel auch nur
> f(n-2)-1 setzen und würde beim Rückstand schon
> ausgleichen. (Dieser Punkt hat mich öfters dazu gebracht
> zu überlegen, ob es nicht sinnvoller ist, die Regeln
> dahingehend zu ändern, dass B schon durch 'Gleichziehen'
> mit dem Gebot von A gewinnt...).
> Weiterhin gewinnt A bei den aktuellen Regeln zum Beispiel
> auch schon beim Spielstand 0-1, wenn A und B beide noch
> Kapital 0 haben.
Diesen Fall sollte man wohl sinnvollerweise ausschließen:
dass A beliebig viele Steine "kostenlos" erwerben kann,
sobald B pleite ist, widerstrebt einem doch irgendwie ...
Unter der Voraussetzung, dass A in jeder Runde mindestens
den Einsatz 1 leisten muss, wäre für #B=2 das minimale
Startkapital, das A haben muss, um zu gewinnen, nicht 3,
sondern 4. Bei der Ausgangslage #A=3 und #B=2 kann A
maximal einen Stein mehr als B erreichen, wenn B sich
gegen einen Sieg von A wehrt. Das wäre dann ein Remis.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:00 Fr 05.08.2011 | | Autor: | kamaleonti |
Hallo,
Hier ist ein Java Programm für den Fall, dass A nicht Null bieten darf.
Es nutzt ein zweidimensionales Array als Speicher. In diesem kann zu den relevanten Spielständen (das sind diejenigen, wo das Spiel noch nicht entschieden ist) und ausgewählten Startkapitalen von B das jeweilige Minimalkapital von A gespeichert werden, welches A benötigt, um den Sieg zu erzwingen.
Diese relativ schlanke Speicherstruktur wird benötigt, um die Berechnung des minimalen Startkapitals von A mit Gewinnstrategie überhaupt für größere #B durchführen zu können. Die wesentliche Funktion ist nämlich rekursiv implementiert.
Ich hoffe die Kommentare sind hilfreich.
LG
Der Code:
| 1: | public class Auktion {
| | 2: | // Programm zum Auktionsspiel, in dem A nicht Null bieten darf d. h. gleiche Gebote sind ausgeschlossen
| | 3: | private static final int diff=2; //Sieghoehe Parameter
| | 4: |
| | 5: | public static int alength=10000, relscores=diff*2-1;
| | 6: | private static int[][] mem = new int[relscores][alength];
| | 7: | //mem speichert fuer relevante Spielstaende und #B den Wert #MinA
| | 8: | //relevante Spielstaende sind -diff+1,...,diff-1
| | 9: | static { // Speicher initialisieren
| | 10: | for(int i=0;i<relscores-1;i++) {
| | 11: | for(int j=0;j<alength;j++) {
| | 12: | mem[i][j]=-1; // Speicher 'leer' initialisieren
| | 13: | }
| | 14: | for (int j=1;j<alength;j++){
| | 15: | mem[relscores-1][j]=j;
| | 16: | // in dieser Situation braucht A nur noch einen Token zum Sieg
| | 17: | // A braucht mindestens #B (klar), also setzt A gerade das jeweilige #B
| | 18: | }
| | 19: | mem[relscores-1][0]=1; // A muss mindestens 1 setzen
| | 20: | }
| | 21: | }
| | 22: |
| | 23: | // Diese Funktion berechnet zu gegebenen Spielstand (Differenz Token von A/B) und einem Kapital von B
| | 24: | // das minimale Kapital von A, dass A für eine Gewinnstrategie benötigt
| | 25: | private static int minA(int score,int moneyB) {
| | 26: | if(mem[score+diff-1][moneyB]!=-1) {// Wert schon berechnet
| | 27: | return mem[score+diff-1][moneyB];
| | 28: | }
| | 29: | if(score==-diff+1) {// B darf keinen Token mehr gewinnen
| | 30: | int res; // A muss zwangslaeufig einen Token gewinnen
| | 31: | if (moneyB==0)
| | 32: | res=1+minA(-diff+2,moneyB);
| | 33: | else
| | 34: | res=moneyB+minA(-diff+2,moneyB);
| | 35: | mem[0][moneyB] = res;
| | 36: | return res;
| | 37: | }
| | 38: |
| | 39: | int min=Integer.MAX_VALUE;
| | 40: | int h;
| | 41: |
| | 42: | for(int j=1;j==1||j<=moneyB;j++) {//moegliche Zuege A
| | 43: | if (moneyB-j>=1){ // wenn B ueberbieten kann
| | 44: | // B zieht optimal, daher Maximum
| | 45: | h=j+Math.max(minA(score+1,moneyB), minA(score-1,moneyB-j-1));
| | 46: | }
| | 47: | else {// B kann nur passen
| | 48: | h=j+minA(score+1,moneyB);
| | 49: | }
| | 50: | if(h < min) min = h; // Suchen unter allen möglichen Zügen j das Minimum an 'verbrauchtem' Kapital
| | 51: | }
| | 52: | mem[score+diff-1][moneyB] = min; // Speicherupdate für spaetere Rekursionsaufrufe
| | 53: | return min;
| | 54: | }
| | 55: |
| | 56: | public static void main(String[] args) {
| | 57: | for (int b=0;b<=1000;b++){
| | 58: | System.out.printf("%d\t%d\n", b, minA(0,b));
| | 59: | }
| | 60: | }
| | 61: |
| | 62: | }
|
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:04 Fr 05.08.2011 | | Autor: | kamaleonti |
Output des Programm in einer Matrix (c) Al .
Die mittlere Spalte entspricht der Ausgabe des obigen Programms - A darf nicht Null bieten.
Die rechte Spalte entspricht der alten Regel, A darf Null bieten.
$ [mm] \pmat{B & A_{min} | Einsatz\ge1 & A_{min} | Einsatz\ge0\\___ &_______&_______\\ \ & &\\0&2&0\\1&2&0\\2&4&1\\3&4&2\\4&6&4\\5&8&5\\6&9&7\\7&10&8\\8&12&10\\9&14&12\\10&15&13\\...&...&...\\...&...&...\\100&161&159} [/mm] $
LG
|
|
|
| |
|
Hallo,
Hier mein Mathematica-Programm, in welchem man den Mindesteinsatz ME des Spielers A festlegen kann (ME=1 oder ME=0). Durch die Prozedur "analyze" wird im dreidimensionalen Array z[a,b,v] schrittweise berechnet, ob der Spielstand [a,b,v] eine Gewinn-, Remis- oder Verlustsituation für A ist. v bedeutet dabei den Vorsprung von A auf B, was die Anzahl der erworbenen Spielsteine betrifft. v=-1 bedeutet also etwa, dass B um einen Stein im Vorsprung ist. A darf ihm also den nächsten Stein nicht überlassen, falls er gewinnen will. Die Parameter n und bmax können festgelegt werden und setzen einfach fest, wie viele Runden analysiert und dargestellt werden sollen.
[Dateianhang nicht öffentlich]
Al-Chwarizmi
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
|
