22: Plätzchenexplosion / Cookie Explosion

  • [...] wohl mit Abstand die schwierigste Aufgabe dieses Jahr.

    Scheint mir auch so - jedenfalls ist es die einzige Aufgabe, bei der meine Lösung falsch ist ;(


    Hat jemand eine Musterlösung da? Ich wüsste doch zu gerne, warum meine Endziffer 6 falsch ist...

    I like to prove it prove it
    I like to prove it prove it
    I like to prove it prove it
    Ya like to . . . PROVE IT!

  • Schöne knifflige Aufgabe. Wenn man eine optimale Strategie auch im Bezug auf die Zusatzaufgaben finden will und dann beweisen will, dass diese auch wirklich optimal ist, wohl mit Abstand die schwierigste Aufgabe dieses Jahr.

    Und ja, diese Zahl ist schon irgendwie unvorstellbar groß, und wenn man dann bedenkt, wie unglaublich klein sie im Vergleich zu Grahams Zahl ist...

    Ich denke, dass die Optimalität nicht so schwierig ist, weil man hier lokal optimieren kann, weil eine Stellung A strikt besser als eine Stellung B ist, wenn es eine Folge von Zügen gibt, sodass man aus A eine Stellung C erhalten kann, sodass auf jedem Feld mindestens so viele Plätzchen wie bei B liegen.


    Die Schwierigkeit liegt vor allem darin, die Zahl zu bestimmen bzw. eine gute Beschreibung dafür zu finden (die nicht die Aufgabenstellung ist).

  • Scheint mir auch so - jedenfalls ist es die einzige Aufgabe, bei der meine Lösung falsch ist ;(


    Hat jemand eine Musterlösung da? Ich wüsste doch zu gerne, warum meine Endziffer 6 falsch ist...

    Schau mal was von Feld 7 auf Feld 8 passiert, da kannst du nicht die gleiche Strategie anwenden. Du hast wahrscheinlich temporär ein Feld 9 benutzt.

  • Scheint mir auch so - jedenfalls ist es die einzige Aufgabe, bei der meine Lösung falsch ist ;(


    Hat jemand eine Musterlösung da? Ich wüsste doch zu gerne, warum meine Endziffer 6 falsch ist...

    Bis zum vorletzten Feld ist die Endziffer 6. Dann kann die Anzahl der Kekse nur noch verdoppelt werden -> Damit ist die Endziffer dann 2. - Habe ich leider auch falsch gemacht 😩

  • Hast du vielleicht vergessen, am Ende den Potenzturm noch mal 2 zu nehmen, da man von Feld 7 auf Feld 8 nur noch verdoppeln kann?


    Meine Lösung ist leider etwas lang geworden, da sie alle Zusatzaufgaben einschließt: https://imgur.com/a/tkh0Vio

    Geht es nur um die Hauptaufgabe, kann man den langen Abschnitt mit dem Beweis, dass alle Felder mehr als drei Felder rechts neben dem ganz linken belegten Feld leer sind, bevor man das ganz linke Feld aufbraucht, überspringen, da diese nach Regel 4 gar nicht belegt sein dürfen.


    /edit:

    Ich denke, dass die Optimalität nicht so schwierig ist, weil man hier lokal optimieren kann, weil eine Stellung A strikt besser als eine Stellung B ist, wenn es eine Folge von Zügen gibt, sodass man aus A eine Stellung C erhalten kann, sodass auf jedem Feld mindestens so viele Plätzchen wie bei B liegen.

    Genau das ist mein Ansatz, den ich allerdings in der Lösung nie so gut beschrieben habe.

  • Scheint mir auch so - jedenfalls ist es die einzige Aufgabe, bei der meine Lösung falsch ist ;(


    Hat jemand eine Musterlösung da? Ich wüsste doch zu gerne, warum meine Endziffer 6 falsch ist...

    Nach meiner (wahrscheinlich optimalen - bewiesen hab ich es aber nicht) Strategie erhält man, links in der ersten Spalte mit einem Plätzchen beginnend, in den weiteren Spalten folgende max. Zahlen von Plätzchen: 2, 2 hoch 2, 2 hoch (2 hoch 2), ... 2 hoch (2 hoch (2 hoch ...) bis hin zur 7. Spalte. Jetzt ist nur noch eine Spalte frei, die achte, und ich kann nur noch verdoppeln, bekomme dadurch aber einen Exponenten, der auf 4 den Rest 1 lässt. Damit Endziffer 2.

  • Man startet immer mit 2 Plätzchen auf Feld 2. Hat man gerade n Plätzchen und ist genug Platz, erhält man für m nebeneinander erlaubte Felder 2↑^(m-2) n Plätzchen auf dem nächsten Feld (zu Herleitung und Beweis der Formel siehe meinen Post weiter oben), also 2↑^(m-2) 2 auf Feld 3, 2↑^(m-2) 2↑^(m-2) 2 = 2↑^(m-1) 3 auf Feld 4, ... bis hin zu 2↑^(m-1) (9-m) Plätzchen auf Feld 10-m. Danach muss man bei jeder weiteren Ausführung der Rekursionsformel m um eins reduzieren, da der Platz ausgeht.


    2 Felder nebeneinander:

    2↑7 = 2^7 Plätzchen auf Feld 8


    3 Felder nebeneinander:

    2↑↑6 Plätzchen auf Feld 7

    2*2↑↑6 Plätzchen auf Feld 8


    4 Felder nebeneinander:

    2↑↑↑5 Plätzchen auf Feld 6

    2^(2↑↑↑5) Plätzchen auf Feld 7

    2*2^(2↑↑↑5) Plätzchen auf Feld 8


    5 Felder nebeinander:

    2↑↑↑↑4 Plätzchen auf Feld 5

    2↑↑(2↑↑↑↑4) Plätzchen auf Feld 6

    2^(2↑↑(2↑↑↑↑4)) Plätzchen auf Feld 7

    2*2^(2↑↑(2↑↑↑↑4)) Plätzchen auf Feld 8


    6 Felder nebeneinander:

    2↑↑↑↑↑3 Plätzchen auf Feld 4

    2↑↑↑(2↑↑↑↑↑3) Plätzchen auf Feld 5

    2↑↑(2↑↑↑(2↑↑↑↑↑3)) Plätzchen auf Feld 6

    2^(2↑↑(2↑↑↑(2↑↑↑↑↑3))) Plätzchen auf Feld 7

    2*2^(2↑↑(2↑↑↑(2↑↑↑↑↑3))) Plätzchen auf Feld 8

  • Man kann da so einiges Verallgemeinern. Wenn man insgesamt auf n Feldern spielt, m benachbarte Felder zum Manövrieren hat und mit Regel 2 bewegte Kekse ver-k-facht werden, dann kann man insgesamt f(n,m,k) Kekse bekommen mit


    f(1,m,k)=1

    f(n,m,k)=k(↑^min(m-2,n-1))f(n-1,m,k)


    Leider hab ich dafür dann keine geschlossene Formel mehr finden können^^

  • Vorschläge für die Zusatzaufgaben:


    Zusatzaufg. 1: Zehnerstelle ist 7

    (kann sein, dass ich mich verrechnet habe, aber im Prinzip ist es eine einfache Rechnung)


    Zusatzaufg. 2:

    max. Anzahl auf Feld8 = 2*2↑(2↑↑(2↑↑↑(2↑↑↑↑(2↑↑↑↑↑2))))

    (wenn man die Beschränkung, dass nur 3 Felder hintereinander belegt sein dürfen, fallen lässt)

    (Beweis fehlt mir allerdings)

    Frage an die Aufgabensteller: sieht die Formel nur schön aus, oder könnte sie auch noch stimmen?

  • Dann kann man sich auch an die Konstruktion von Grahams Number machen: Wir modifizieren das Spiel so, dass Plätzchen nicht nur verdoppelt sondern verdreifacht werden, wenn man sie ein Feld weiter schiebt (das "Vertauschen" soll weiterhin ein Plätzchen kosten). Dann wird die Plätzchenanzahl vom vorletzten Feld verdreifacht, um die des letzten Felds zu erreichen; die vom vorvorletzten als Exponenten in eine Dreierpotenz geschrieben, um die vom vorletzten zu erhalten; die vom vorvorvorletzten als Höhe eines Dreierpotenzturms genommen, um die vom vorletzten zu erhalten; ...


    Ist a die Anzahl der Plätzchen, die man maximal auf dem n-k-ten Feld von insgesamt n zur Verfügung stehenden erzeugen kann, so ist 3↑^(k-1) a die maximale Anzahl an Plätzchen, die man auf dem n-(k-1)-ten Feld erzeugen kann. Dabei stehe 3↑^(z) a für den Ausdruck 3↑↑...↑ a mit insgesamt z Pfeilen. Definieren wir noch zusätzlich 3↑^(0) z als 3*z ergeben sich also maximal 3↑^(0) 3 ↑^(1) 3 ... ↑^(n-2) 3 Plätzchen auf dem letzten Feld, da man als erstes in jedem Fall das eine Plätzchen auf dem ersten Feld zu 3 Plätzchen auf dem zweiten machen muss und ab dann die gerade zuvor erläuterte Rekursion , beginnend mit k=n-2, anwenden kann.


    Wenn man also zu Beginn n=6 Felder zur Verfügung hat, erhält man maximal P_1:=3*3↑3↑↑3↑↑↑3↑↑↑↑3 Plätzchen, was deutlich größer als G_1:=3↑↑↑↑3 ist. Insbesondere ist P_1>G_1+2. Generell erhält man auf einem Brett mit n Feldern mehr Plätzchen als 2 + 3↑^(n-2) 3.


    Dies führt uns zu folgender Konstruktion einer Zahl, die größer ist als Grahams Number G_64:


    *) Starte das Spiel auf 6 zur Verfügung stehenden Feldern. Die maximale Plätzchenanzahl, die du darauf erreichst, nenne P_1. Es ist P_1 > G_1 + 2.

    *) Spiele nun das Spiel auf einem Brett, auf dem P_1 Felder zur Verfügung stehen. Die maximale Plätzchenanzahl, die du darauf erreichst, nenne P_2. Es ist P_2 > 2 + 3↑^(P_1 - 2) 3 > 2 + 3↑^(G_1) 3= 2+ G_2, da G_2 als 3↑^(G_1) 3 definiert ist.

    *) Spiele das Spiel nun auf einem Brett, auf dem P_2 Felder zur Verfüung stehen. Die maximale Plätzchenanzahl, die du darauf erreichst, nenne P_3. Analog oben ist P_3 > 2 + 3↑^(P_2 - 2) 3> 2 + 3↑^(G_2) 3 = 2 + G_3 mit G_3:=3↑^(G_2).

    *) ...

    *) Spiele das Spiel nun auf einem Brett mit P_63 Feldern. Die maximale Plätzchenanzahl, die du darauf erreichst, nenne P_64. Nun ist P_64 > ... > G_64, was Grahams Number ist.



    Cyrix

  • 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.