Beiträge von AugustaSibylla

    Hier gibt es ja unheimlich viel zu lesen, keiner hat aber das Ergebnis klar hingeschrieben (oder ich habs überlesen). Ich komme bei meinen einfachen Überlegungen auf 2 hoch 65 Plätzchen für die erste (einfache) Variante. Das ist also 1 Keks mehr als in der klassischen Variante, die in der Aufgabe scherzhaft angerissen wurde. Da müssten es (2 hoch 65) – 1 sein. Hat jemand mehr Kekse für die einfache Variante oder ist dieses Ergebnis so schon beschrieben?


    Mein Verfahren (als Pseudo-Code formuliert, also keine real existierende Programmiersprache):

    - man möge mir die seltsame Einrück-Methode mit den Punkten verzeihen, aber ich hab keine Erfahrung mit diesem Texteditor


    // Ausgangssituation:

    // Die Felder haben von rechts nach links die Nummern 1 bis 8

    // Es sei: A(i) Die Anzahl der Kekse auf Feld i

    // Startposition: ein Keks auf dem Feld ganz rechts, also A(1) = 1, A(i) = 0 für alle i aus {2,3,4,5,6,7,8}


    // führe 6 mal aus:

    For i = 1 to 6 Do

    Begin (For)

    // Verschiebe einen Keks auf Feld i um ein Feld nach links (von i nach i+1) und verdopple dort die Anzahl

    .....A(i+1) := 2; A(i) := A(i)-1;


    …...// Wiederhole, solange auf dem Feld i noch Kekse sind:

    ......While A(i) > 0 Do

    ......begin (While)

    ………….// Verschiebe alle Kekse links von Feld i um ein Feld nach links (von i+1 nach Feld i + 2)

    ......…….// und verdopple dort die Anzahl


    .........….A(i+2) := 2 * A(i+1); A(i+1) := 0;


    …......….// Verwende einen Keks auf Feld i, um die Kekse auf den Feldern i+1 und i+2 zu tauschen,

    ............// also alle Kekse auf Feld i+2 um ein Feld nach rechts zu schieben.


    .........….A(i+1) := A(i+2); A(i+2) = 0; // Da A(i+1) zuvor 0 war, kein Tausch mit Hilfsvariable notwendig

    .........….A(i) := A(i)-1;

    ...….end (while)

    …….// Auf dem Feld (i+1) liegen nun 2 hoch k Kekse, wobei k = die Anzahl Kekse auf dem Feld i zu

    …….// Beginn der While-Scheife


    End (For)

    // die Kekse haben sich im Laufe des Verfahrens von Feld 1 auf Feld 7 wie folgt vermehrt:

    //1, 2, 4, 2 hoch 4=16, 2 hoch 16=65536, 2 hoch 32, 2 hoch 64



    //Verschiebe alle Kekse auf Feld 7 um ein Feld nach links auf Feld 8 und verdopple dort die Anzahl


    A(8) := 2 * A(7); A(7) := 0;


    //Auf dem Feld 8 liegen nun 2 hoch 65 Kekse, die letzten beiden Ziffern sind 32


    Die letzten beiden Ziffern habe ich einfach in Excel ermittelt, in dem ich die Zahl 2 65 mal verdoppelt und von dem Verdopplungsergebnis mit der Excel-Funktion REST den Rest bei Division durch 100 ermittelt habe.

    habe die von pierrot erwähnte Anzahl der Fixpunktfreien Permutationen rekursiv bestimmt. (Ich hoffe, das stimmt)

    Rekursive Ermittlung von P(k)

    •P(0) = 1 (per Definition)
    •P(1) = 0
    •P(2) = 1, Reihenfolge 2, 1
    •P(3) = 2, Reihenfolgen 2,3,1 und 3,1,2
    •P(4) = 4! – (4 über 4)*P(0) - (4 über 3) *P(1) - (4 über 2) * P(2) - (4 über 1) * P(3) = 24 – 1 – 0 – 6 – 8 = 9


    •P(5) = 5! – ∑_5i=1    (5 über i) * P (5-i) = 44


    •P(k) = k! – ∑_ki=1 (k über i) * P (k-i), für alle k >=2



    Die Idee dabei: von k! werden für alle i <= k alle Permutationen subtrahiert, in denen i Stellen Fixpunkte sind, das ist von der Anzahl her (k über i) multipliziert mit der Anzahl der Möglichkeiten, die übrigen k-i Plätze fixpunktfrei auf diese zu verteilen (P ( k-i ) )

    Antwort 9 ist die richtige Auswahl weil:


    Wenn man die Rundreise Winterwald - Wichtelstraße - Rentiergehege - Winterwald fährt, schafft man das auf Grund der Fahrzeiten frühestens in einer Stunde und einer Minute

    wenn man eine Minute als minimale Umsteigezeit ansetzt sind es 1 Stunde und 3 Minuten.


    (24 Minuten von Winterwald nach Wichtelstraße mit Linie 3,

    32 Minuten von Wichtelstraße nach Rentiergehege Linie 4,

    5 Minuten Rentiergehege nach Winterwald, Linie 5)


    Wenn die Umsteigezeit maximal 10 Minuten dauern darf, darf die Reisezeit der Route höchstens eine Stunde und 21 Minuten dauern.


    Also egal, wie Rudolf den Fahrplan gestaltet: wenn die Route diese Bedingungen erfüllt, ist die Umstiegsdauer vom Winterwald in die Wichtelstrasse zwischen 39 Minuten und 59 Minuten (bzw. 57, wenn man die minimale Umsteigezeit von einer Minute ansetzt).

    Ich denke die vermeintlich verschiedenen Lösungen liegen vom Prinzip her gar nicht so weit auseinander. Ich denke wir können uns auf Folgendes einigen:

    - Atto ist in einer vermeintlich fatalistischen Lage (kann eigentlich machen was ich will, die Erfolgswahrscheinlichkeit ist 1/3). Er muss aber seine Farbe gezielt so wählen, dass Bilbo und Chico die von Ihm genannte Farbe eindeutig auf ihre abbilden können unter Einbeziehung der Farbe des jeweils anderen (der beiden Chico oder Bilbo) als Abbildungs-Stellgröße.


    Die Matrix im Lösungsvorschlag hinter dem Link von pierrot hat Ähnlichkeit mit meinem Farbensudoku-Feld. Er schreibt da auch: in jeder roten Spalte (für Bilbo) und jeder roten Zeile (für Chico) dürfen keine gleichen Zahlen stehen.

    Wenn ich in meinen Farbauswahlregeln für Atto, Bilbo, Chico daraus hervorgehende Zahlencodes (Nummern 1-5) ermitteln würde, sähe das Sudokufeld in etwa so aus wie die Matrix bei pierrot.

    Atto musste als Erster raten. 3 Farben kamen in Frage, er hatte hierzu keine weiterführenden Hinweise. Die Wahrscheinlichkeit, dass er seine Farbe richtig erraten würde war 1/3, wie auch immer er sich entschiede.

    „1/3 ist also die nicht überschreitbare Obergrenze einer Gewinnwahrscheinlichkeit für die Gesamtstrategie“, grummelte er. D.h. N <= 20.

    Immerhin: für den Fall, dass Atto mit Glück die richtige Wahl treffen würde, hatten sich die drei Wichtel eine Strategie ausgedacht, der sie den Namen Farbensudoku-Strategie“ gaben. Mit dieser Strategie, so waren sie sich sicher, würden Chico und Bilbo ihre Mützenfarben richtig erraten. D.h. N = 20

    Sie dachten sich ein Farbensudoku-Rätsel aus, in dem die 5 Farben in der Diagonalen oben-links bis unten-rechts vorgegeben waren. (Im Folgenden steht das Wort Diagonale für genau diese Diagonale) Die übrigen Felder waren so mit einer Farbe auszufüllen, dass in jeder Zeile und in jeder Spalte jede der 5 Farben genau einmal vorkam.


    Für die drei Intelligenzwichtel war das Sudoku-Rätsel keine echte Herausforderung. Schnell hatten sie eine Lösung gefunden

    weiss rot blau schwarz gelb
    rot gelb schwarz weiss blau
    schwarz blau

    rot

    gelb weiss
    gelb schwarz weiss blau rot
    blau weiss gelb rot schwarz


    Auf Basis dieser Lösung definierten Sie folgende Gewinn-Strategie:

    Für die Erläuterung zu beachten: jede Zeile und jede Spalte hat genau ein Feld in der Diagonalen. (Felder, die fett und unterstrichen sind). Die Positionen dieser Felder bezeichnen wir im Folgenden als die eindeutigen Diagonalenpositionen einer Spalte bzw. einer Zeile.


    Regel für Atto: Suche in der Zeile mit Bilbos Farbe in ihrer Diagonalenposition das Feld mit Chicos Farbe. Wähle die Farbe in der Diagonalenposition der zu diesem Feld gehörigen Spalte.


    Regel für Bilbo: Suche in der Spalte mit Attos Farbe in ihrer Diagonalenposition das Feld mit Chicos Farbe. Wähle die Farbe in der Diagonalenposition der zu diesem Feld gehörigen Zeile.


    Regel für Chico: Wähle die Farbe des Feldes, für das gilt: Das Feld liegt in der Zeile mit Bilbos Farbe in ihrer Diagonalenposition und in der Spalte mit Attos Farbe in ihrer Diagonalenposition.

    Die drei Wichtel machten sich zusammen auf den Heimweg. Der Zichorienkaffee und der alte Kuchen vom Vormonat lagen ihnen schwer im Magen und verursachten heftige Bauchschmerzen. Missmutig knurrte Atto: “Da haben wir unser Bestes gegeben, aber der alte Geizhals wusste genau, dass wir kaum eine Chance hatten und er mit einer Zweidrittel-Wahrscheinlichkeit die Sachertorte für sich behalten würde“.


    Da kam Chico eine Idee der süßen Rache. Noch am selben Abend besuchten Sie Rudolph das Rentier, von dem sie wussten, dass es am 22. Dezember als Verhandlungsführer der Rentiergewerkschaft einen lukrativeren Arbeitsvertrag mit dem Weihnachtsmann aushandeln wollte. Der 22. Dezember wird als der Tag in die Geschichte eingehen, ab dem alle Rentiere und alle Wichtel im ganzen Land eine kostenlose Keksversorgung haben werden, für sich und für alle Ihre Nachkommen bis ans Ende aller Tage….