Wie viele Möglichkeiten hat Theo, den Turm zu bauen?

Question

Aufgabe :

Theo hat 8 Würfel mit den Seitenlängen 1, 2, 3, ..., 8. Er möchte einen Turm aus allen acht Würfeln bauen. Für die Stabilität müssen jedoch folgende Regeln gelten:

* Der unterste Würfel kann beliebig gewählt werden.

* Der Würfel, der unmittelbar auf einem Würfel mit der Seitenlänge k liegt, muss eine Seitenlänge von höchstens k + 2 für alle k ∈ [8] haben.

Wie viele Möglichkeiten hat Theo, den Turm zu bauen?

Problem/Ansatz:

Comments

Ich sitze seid ungefähr Tagen an dieser Aufgabe und komme einfach auf die Lösung. Die Aufgabe muss bis morgen fertig werden und wenn jemand mir helfen kann, dann wäre es wirklich großartig.

---

Baumdiagramm?

---

Ich würde mit 4 Würfeln anfangen.

Wenn keine Einschränkungen gelten würden, gäbe es 4!=24 Möglichkeiten.

4 auf 1 ist aber verboten, d.h.

unten ---------- oben

            14xx

             x14x

             xx14

xx kann 23 oder 32 sein.

Also sind 6 Fälle verboten und 18 erlaubt.

---

Bei 8 Würfeln sind verboten

14, 15, 16, 17, 18, 25, 26, 27, 28, 36, 37, 38, 47, 48, 58

Wenn ich jetzt von 8! alle Möglichkeiten subtrahiere wo obige Möglichkeiten vorkommen wäre das schon ein Anfang.

Beachte das man Möglichkeiten bei denen 14 und 25 vorkommen mind. zweimal abziehen würde.

Die Frage ist ob man das über Inklusion und Exklusion einfach hinbekommen kann. Denk vielleicht mal darüber nach.

---

Du hast das mit "Extremwertaufgabe" verschlagwortet. Steckt da Absicht dahinter?

In was für einer Veranstaltung soll das gelöst werden? Ist Infomatik dort ein Thema?

Fred Feuerstein sagt:

Zur Not kann man ja die 8 ! Möglichkeiten durchprobieren. Dem Fred sein Programm probiert sogar 8⁸ Möglichkeiten durch, weil sein Softwareingenieur Barney gerade im Steinbruch anderweitig beschäftigt war.

---

Wie gesagt, ich sitze nicht erst seit heute dran. Baumdiagramm habe ich schon probiert und mir viel den Kopf zerbrochen.

"Die Frage ist ob man das über Inklusion und Exklusion einfach hinbekommen kann. Denk vielleicht mal darüber nach." - Ja, darüber habe ich sehr wohl nachgedacht. das, was ich brauche, sind Lösungen. Und meine Teammates haben noch weniger Ahnung, auf die ist kein Verlass.

Diese Aufgabe ist Teil einer Hausaufgabe, die in meiner nächsten Vorlesung, sprich, morgen, fertig sein muss.

---

Hier ist meine Lösung:

Machen wir es etwas allgemeiner. Stellt euch vor, dass 1 bis n Zahlen bereits angeordnet sind. Und das nächste n+1 kann nur das Ende von n oder n-1 sein. Oder der vorderste Platz. Wenn also die 1-zu-n-Anordnung nach dieser Regel bn ist, dann gilt bn+1 = bn * 2 bn und b1=1, b2=2, b3=6, b4=18, b5=54, wir können wissen, dass die Anfangsbedingung folgt die Regel von b3, also b8 =1458

---

Das ist die Lösung die willyengland auch schon verlinkt hatte. Schöne Lösung übrigens.

Answer 1

Guck z.B. mal hier:

https://artofproblemsolving.com/wiki/index.php/2006_AIME_I_Problems/Problem_11

10 s Google-Suche.

:-)