Gewinnstrategie |
| 12.10.2011, 12:48 | Lyla 2005 | Auf diesen Beitrag antworten » | ||||
| Gewinnstrategie Meine Frage: Hallo, wir haben heute in der Uni folgende Knobelaufgabe bekommen. Sie und ein Kommilitone spielen ein Spiel An der Tafel steht zunächst die Zahl 2 Wer am Zug ist, ersetzt die Zahl n an der Tafel durch die Zahl m+n, wobei m ein beliebiger Teiler von n ist und 1 <= m <n Verloren hat, wer eine Zahl > 2011 an die Tafel schreibt Welche Strategie sollte man verfolgen, wenn man gewinnen möchte Meine Ideen: Ich habe jetzt schon paar Varianten ausprobiert habe aber keine sinnvolle Lösung gefunden. Ich weiß nicht ob das richtig ist, aber ich gehe auch immer davon aus, das m eine ganze Zahl ist. Also wenn man davon ausgeht, dass beide immer den kleinsten Teiler addieren, dann sollte man Anfangen, weil dann würde man immmer die ungeraden Zahlen haben und der Kommilitone ist am Ende gezwungen eine größere Zahl als die 2011 zu schreiben. Aber irgendwie fällt mir keine Strategie ein. Kann mir da einer vll. einen Tipp geben. |
||||||
| 12.10.2011, 21:32 | Abakus | Auf diesen Beitrag antworten » | ||||
| RE: Gewinnstrategie Hallo, der erste Schritt ist immer mal ein bisschen mit so einem Problem herumzuspielen. Bei Primzahlen zB ist die Situation hier recht übersichtlich. Wenn p eine Primzahl größer 2 ist, und die (gerade) Zahl p-1 an der Tafel steht und du dran bist, bist du dann in einer Gewinn- oder Verlustposition (angenommen jeder macht die besten Züge immer)? Und wieso? Darfst du also so spielen, dass du selbst eine Zahl der obigen Form p-1 anschreibst? Abakus 
|
||||||
| 13.10.2011, 11:23 | Lyla2005 | Auf diesen Beitrag antworten » | ||||
| RE: Gewinnstrategie Also das mit den Primzahlen ist mir heute morgen auch eingefallen. Wenn ich anfangen würde und die 3 hinschreiben würde und danach würde ich immer versuchen eine Primzahl zu schreiben, was zwar nicht immer klappen wird, aber dann habe ich nach meiner Überlegung gute Chancen, das ich Gewinne oder habe ich da wieder einen Denkfehler drin? |
||||||
| 13.10.2011, 11:28 | Lyla2005 | Auf diesen Beitrag antworten » | ||||
| RE: Gewinnstrategie Also ich sollte nicht eine p-1 Zahl schreiben, weil dann ist die Wahrscheinlichkeit groß, dass ich die 2011 an die Tafel schreiben kann und somit Gewinne. Also meine Strategie sollte sein, immer eine Primzahl bzw nicht p-1 zu nehmen |
||||||
| 13.10.2011, 17:33 | Abakus | Auf diesen Beitrag antworten » | ||||
RE: Gewinnstrategie
Ja, da ist ein Denkfehler drin. Was ist denn deine Begründung, wieso das so sein sollte?
Um Wahrscheinlichkeiten geht es hier nicht. Gesucht ist eine Strategie, also die Angabe einer Zugmöglichkeit in jeder möglichen Spielsituation. Und auch hier fehlt die Begründung: was ist die Logik dahinter? ------------------------------- Als Erstes brauchst du vielleicht ein Modell, wie du dieses Spiel mathematisch darstellen willst. Wie wäre es mit einem Graphen: du hast die Knoten von 2 bis 2011 und den Knoten V (für Verloren) und du hast Pfeile zwischen diesen Knoten, wenn du von einer Zahl zur anderen kommst. ZB hast du von der 9 Pfeile zu den Knoten 10 und 12. Die Menge der Pfeile zerfällt jetzt in 2 Mengen, die der Gewinnzüge und die der Verlustzüge. Ebenso die Menge der Knoten, Knoten von denen mindestens ein Gewinnpfeil ausgeht, sind Gewinnknoten; Knoten von denen nur Verlustpfeile ausgehen sind Verlustknoten. Soweit erstmal. Welcher Knoten und Pfeil ist nun was? 2011 ist ein Verlustknoten, denn jeder Zug verliert. Jeder Knoten, von dem sich 2011 in einem Schritt erreichen lässt, ist ein Gewinnknoten und der zugehörige Pfeil ist ein Gewinnpfeil... So geht es rückwärts weiter und daraus lässt sich eine Strategie entwickeln (ein kleines Programm macht das blitzschnell). Für Knoten der Form p-1 kannst du jedoch sofort sagen, was für Knoten das sind. Kommst du drauf, wieso? Mein Vorschlag: zeichne den Graphen mal für das Problem mit n=20 statt 2011. Das ist noch übersichtlich. Markiere Gewinnerknoten & - pfeile ROT und Verliererknoten & - pfeile BLAU. Abakus
|
||||||
| 13.10.2011, 21:22 | Lyla | Auf diesen Beitrag antworten » | ||||
Irgendwie habe ich da voll eine Blokade. Also ich habe jetzt gerade mal einen "Baum" gezeichnet mit allen Möglichkeiten bis 20. Aber ich habe noch nicht so ganz verstanden was ich´jetzt tun soll, bzw was ich dann sehe. Also zum Beispiel erst kommt die 2 dann die 3 und dann die 4 und dann gibt es ja zwei Möglichkeiten entweder kommt dann die 5 oder die 6. Aber wann ist was ein Gewinnknoten? Weil angenommen von der 9 da geht es einmal zur 10 und einmal zu 12. Aber von diesen beiden Zahlen gehen jeweils wieder mehrere Mengen ab. Es tut mir leid, das ich mich anscheinend echt so blöd stelle, aber ich verstehe das noch nicht wirklich. Also ein Knoten ist eine Zahl oder? |
||||||
| Anzeige | ||||||
|
|
||||||
| 13.10.2011, 21:29 | Abakus | Auf diesen Beitrag antworten » | ||||
Ja, genau. Fange von hinten an (also bei 20), nicht von vorne: 20 ist ein Verlustknoten (blau), jeder weitere Zug führt zu einer Zahl über 20. Jeder Zug, der zu 20 führt, ist also ein Gewinnzug (rot) und jeder Knoten, von dem ein solcher Zug ausgeführt werden kann, ist ein Gewinnknoten (19, 18, 16, 15). 17 und 14 führen nur zu roten Knoten, müssen also selbst blau sein.... und weiter rückwärts dann. Abakus
|
||||||
| 13.10.2011, 21:33 | Lyla | Auf diesen Beitrag antworten » | ||||
ich habe nur noch herausgefunden, dass man immer von der16,18,15 direkt auf die 20 kommen würde, aber ich weiß nicht was mich das weiter bringen könnte. Wenn ich mir die Reihen angucke, die zur 20 führen, dann kommen da gerade Zahlen Primzahlen und ungerade Zahlen vor, sodass ich mir daraus auch keine Strategie vorstellen kann |
||||||
| 13.10.2011, 21:35 | Lyla | Auf diesen Beitrag antworten » | ||||
hatte nicht gesehen, dass ich schon eine Antwort bekommen habe, ich Probiere das mal eben aus. danke |
||||||
| 13.10.2011, 21:43 | Lyla | Auf diesen Beitrag antworten » | ||||
so ich muss nochmal nachfragen, ob ich das richtig verstanden habe. ich habe jetzt zum beispiel die 18, zur 18 kommen 9, 12,15,16,17 das wären dann jetzt alle blaue Pfeile und Knoten oder wären die 15 und 16 Rote Knoten? Weil von da käme man ja sofort zur 20? |
||||||
| 13.10.2011, 21:47 | Abakus | Auf diesen Beitrag antworten » | ||||
Von der 9 kommst du nicht zur 18, denn zugelassen sind ja nur echte Teiler und die 1 (so habe ich es verstanden). Alle Pfeile zur 18 sind blau, ja. Die 15 und 16 sind rote Knoten, denn von diesen geht ja mindestens ein roter Pfeil aus (in diesem Fall zur 20). Abakus
|
||||||
| 13.10.2011, 22:02 | Lyla | Auf diesen Beitrag antworten » | ||||
ja stimmt die 9 hatte da nichts zu suchen. ich habe jetzt in der zwischenzeit mal alle möglichen Wege aufgeschrieben, aber bei mir sind dann alle anderen Wege blau und es gibt auch nur noch blaue Knoten, weil es keine Zahlen gibt außer 15,16,,18,19 die direkt zur 20 führen und die Pfeile sind sonst bei mir auch nur noch blau, weil es keinen direkten Weg dorthin gibt sondern, es gibt überall irgendwo Abzweigungen. Irgendwas habe ich doch schon wieder falsch gemacht, das kann ja nicht sein |
||||||
| 13.10.2011, 22:37 | René Gruber | Auf diesen Beitrag antworten » | ||||
Ich schlage vor, im Anschluss statt mit 20 auch mal mit Schwelle 21 oder 19 ein derart einfaches Beispiel durchzurechnen. 
|
||||||
| 13.10.2011, 22:49 | Lyla | Auf diesen Beitrag antworten » | ||||
Ich verzweifel hier total. Ich verstehe das nicht. Ok habe das jetzt auch mit 19 gemacht. ist ja ziemlich ähnlich. Aber was habe ich davon? ich sehe glaube ich den Wald vor lauter Bäumen nicht mehr |
||||||
| 13.10.2011, 23:35 | Abakus | Auf diesen Beitrag antworten » | ||||
Für ungerade Schwellen wird es dann recht einfach, ja 
. Fast schade, dass wir das nicht zuerst betrachtet haben.
Alle Pfeile zu einem roten Knoten sind blau (solche Züge verlieren ja). Alle Pfeile zu einem blauen Knoten sind rot (der Gegenspieler hat einen Verlustknoten). ----------------- Für allgemeine Schwellen n lässt sich jedenfalls sagen: p-1 (p>2 prim) ist ein Gewinnknoten, denn es gibt die möglichen Züge auf p und p+1 (p-1 hat mindestens die Teiler 1 und 2). Wird der Zug auf p gemacht, muss der Gegenspieler auf p+1 ziehen. Man hat also die Wahl, wer die p+1 an die Tafel anschreibt und kann so einen Gewinnknoten erreichen oder seinen Gegenspieler einen Verlustknoten zuschieben. Da 4 die erste Zahl mit dieser Eigenschaft ist, lässt sich auch sagen, wer diese Spiele bei beliebiger Schwelle gewinnt; es ist immer derselbe. Abakus
|
||||||
| 14.10.2011, 17:08 | Lyla | Auf diesen Beitrag antworten » | ||||
Hat also derjenige gewonnen,der die 4 an die tafel schreibt? und danach muss man versuchen p-1 Zahlen (also ungerade und Primzahlen) zu schreiben? Ich bedanke mich schon einmal für die ganze Mühe |
||||||
| 14.10.2011, 19:09 | René Gruber | Auf diesen Beitrag antworten » | ||||
Nein, derjenige, der eine 4 vorfindet. Ob er nun als nächstes eine 5 oder 6 hinschreibt, hängt vom Zielwert ab - lies dir mal Abakus' Ausführungen ruhig und gründlich durch, es lohnt sich! Bei ungeraden Zielwerten (wie hier 2011) ist diese Entscheidung allerdings ungleich einfacher als bei geraden Zielwerten. EDIT: Ich hab Abakus' Strategie wohl selbst noch nicht richtig verinnerlicht - es ist klar, dass der Gewinnzug hier "4 ->5" ist, denn mit "4 -> 6" würde man dem Gegner ja ein Gewinnposition vom Typ p-1 hinterlassen. Weiter hinten wird's dann aber doch komplizierter. 
|
||||||
| 14.10.2011, 20:33 | D. Pauly | Auf diesen Beitrag antworten » | ||||
Dies ist eine Uni aufgabe, die dazu gedacht ist unsere Studenten zum Überlegen zu bewegen. Sich hier einfach nur alles vorkauen zu lassen bringt rein garnichts. Ihr müsst die Knobelaufgabe nicht lösen ! Diese bringt auch nur etwas, wenn man spaß an der sache hat. |
||||||
| 14.10.2011, 22:30 | Abakus | Auf diesen Beitrag antworten » | ||||
Ja. Die Frage ist noch (bei allg. Schwelle und beliebiger an der Tafel stehender Zahl), ob es möglich ist, den richtigen Zug rauszufinden ohne alles von hinten aufzudröseln. Das verallgemeinert dann die in diesem Thread gestellte Frage. Abakus
@ D. Pauly: siehe unser Forumprinzip, wir leisten Hilfe zur Selbsthilfe. Lösungen werden i.A. nicht explizit verraten. Und wir haben Spaß an der Sache, schließlich bekommen wir weder Bezüge noch Studiengebühren! |
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|