Rekursionsgleichung für Turm

26.08.2021, 08:06

sonny1001

Rekursionsgleichung für Turm

Hallo zusammen,
zuerst geht es mir um die Aufstellung der Rekurrenzgleichung(en)

Hier die Aufgabe:
Wir haben einen ausreichend großen Vorrat an Holzbausteinen vom Format 2x1x1. Auf wieviel verschiedene Arten können wir einen Turm der Höhe n mit einer Grundfläche der Größe 2 x2 bauen?
(Hinweis: Für n=6 gibt es 1681 Möglichkeiten)

Meine Lösung:
Für unteren Abschluss

1.Fall
2 liegende Steine 2M(n-1)

2.Fall
4 stehende Steine M(n-2)

3.Fall
1 liegender und 2 stehende 4M(n-2)

Das führt zu:

M(n)=2M(n-1)+5M(n-1)

Musterlösung:
$\begin{eqnarray*} b(n)=2b(n-1)+b(n-2)+4c(n-1) \end{eqnarray*}$
und
$\begin{eqnarray*} c(n)=b(n-1)+c(n-1) \end{eqnarray*}$

Das Zusammenfassen der beiden Gleichungen führt auf:
$\begin{eqnarray*} b(n)=3b(n-1)+3b(n-2)-b(n-3) \end{eqnarray*}$
Dies Gleichung kann ich nicht nachvollziehen.
Sind die Rekurrenzgleichungen für ein Problem eindeutig?

Gruß
sonny

28.08.2021, 17:41

Huggy

Auf diesen Beitrag antworten »

RE: Rekursionsgleichung für Turm

Zitat:

Original von sonny1001
Für unteren Abschluss

1.Fall
2 liegende Steine 2M(n-1)

2.Fall
4 stehende Steine M(n-2)

3.Fall
1 liegender und 2 stehende 4M(n-2)

$\begin{eqnarray*} M(n) \end{eqnarray*}$ soll wohl die Zahl der Türme mit der Höhe $\begin{eqnarray*} n \end{eqnarray*}$ sein. Für Fall 1 gibt es 2 Konfigurationen und man kann darauf einen beliebigen Turm der Höhe $\begin{eqnarray*} n-1 \end{eqnarray*}$ stellen, um einen Turm der Höhe $\begin{eqnarray*} n \end{eqnarray*}$ zubekommen. Für Fall 3 gibt es 4 Konfigurationen und man kann darauf so wie auf Fall 2 einen beliebigen Turm der Höhe $\begin{eqnarray*} n-2 \end{eqnarray*}$ stellen. Allerdings müssen doch im Fall 3 zwei liegende Steine aufeinanderliegen. Sonst hat der Turm ja eine Lücke.

Zitat:

Das führt zu:

M(n)=2M(n-1)+5M(n-2)

Ja. (Druckfehler korrigiert)

Aber da fehlt noch ein Fall für den unteren Abschluss. Man nimmt jetzt wie von dir für Fall 3 beschrieben einen liegenden Stein und zwei stehende Steine und setzt die Konfiguration noch mal gespiegelt darauf. Auf den liegenden Stein kommen zwei stehende Steine und auf die beiden stehenden Steine kommt ein liegender. Dieser Abschluss hat die Höhe $\begin{eqnarray*} 3 \end{eqnarray*}$ und es gibt 4 Konfigurationen. Darauf kann man einen beliebigen Turm der Höhe $\begin{eqnarray*} n-3 \end{eqnarray*}$ setzen. Das führt zu der Rekursion

$\begin{eqnarray*} M(n)=2 M(n-1)+5 M(n-2)+4 M(n-3) \end{eqnarray*}$

Mit den Anfangswerten $\begin{eqnarray*} M(0)=1, M(1)=2, M(2)=9 \end{eqnarray*}$ führt das allerdings auf $\begin{eqnarray*} M(6)=1573 \end{eqnarray*}$ und nicht auf $\begin{eqnarray*} M(6)=1681 \end{eqnarray*}$ . Vielleicht habe ich zum Bau des Turmes etwas falsch verstanden. Zur Musterlösung kann ich nichts sagen, da die Definitionen von $\begin{eqnarray*} b(n) \end{eqnarray*}$ und $\begin{eqnarray*} c(n) \end{eqnarray*}$ fehlen.

28.08.2021, 18:12

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von sonny1001
Musterlösung:
$\begin{eqnarray*} b(n)=2b(n-1)+b(n-2)+4c(n-1) \end{eqnarray*}$
und
$\begin{eqnarray*} c(n)=b(n-1)+c(n-1) \end{eqnarray*}$

Das Zusammenfassen der beiden Gleichungen führt auf:
$\begin{eqnarray*} b(n)=3b(n-1)+3b(n-2)-b(n-3) \end{eqnarray*}$
Dies Gleichung kann ich nicht nachvollziehen.

Wenn ich jetzt mal unabhängig vom inhaltlichen Hintergrund einfach annehme, dass die beiden erstgenannten Rekursionsgleichungen für b(n) und c(n) stimmen, dann kann man so vorgehen:

Aus der ersten Gleichung folgt $\begin{eqnarray*} 4c(n-1) = b(n)-2b(n-1)-b(n-2) \end{eqnarray*}$ . Einen Index hochgezählt ergibt das $\begin{eqnarray*} 4c(n) = b(n+1)-2b(n)-b(n-1) \end{eqnarray*}$ .

Beides in das Vierfache der zweiten Gleichung, d.h. $\begin{eqnarray*} 4c(n)=4b(n-1)+4c(n-1) \end{eqnarray*}$ eingesetzt führt zu

$\begin{eqnarray*} b(n+1)-2b(n)-b(n-1)=4b(n-1)+b(n)-2b(n-1)-b(n-2) \end{eqnarray*}$ ,

umgestellt $\begin{eqnarray*} b(n+1)=3b(n)+3b(n-1)-b(n-2) \end{eqnarray*}$ . Jetzt kann man wieder einen Index runtergehen und erhält

$\begin{eqnarray*} b(n)=3b(n-1)+3b(n-2)-b(n-3) \end{eqnarray*}$ .

P.S.: Meine Vermutung zur Bedeutung von b(n) und c(n) im Eröffnungsbeitrag:

$\begin{eqnarray*} b(n) \end{eqnarray*}$ ... Gesuchte Anzahl an Türmen der Höhe $\begin{eqnarray*} n \end{eqnarray*}$

$\begin{eqnarray*} c(n) \end{eqnarray*}$ ... Anzahl an Türmen der Höhe $\begin{eqnarray*} n \end{eqnarray*}$ , wo ein in der Grundfläche liegender Platz 2x1x1 schon "vorbelegt" ist

@Huggy

Ich bin nicht ganz hinter deine Fallunterscheidung gestiegen, aber mich beschleicht ein Verdacht:

Bildest du den Fall richtig ab, dass nur in der Grundschicht und in der Deckschicht des $\begin{eqnarray*} n \end{eqnarray*}$ -Turmes jeweils ein liegender Stein zu finden sind, und ansonsten der Turm nur aus stehenden Steinen besteht, immer paarweise gebündelt und um eine Höheneinheit gegen das nächste Paar versetzt?

Dieser Fall widersetzt sich nämlich der gewöhnlichen Betrachtung, dass man den Turm irgendwo zwischendurch auftrennen kann in zwei Teiltürme, ohne die Bausteine zu zerschneiden - das ist es aber, was man bei der "gewöhnlichen" Rekursionsbetrachtung gern haben möchte, hier aber eben nicht erreicht.

Der Trick mit der Anzahlbetrachtung $\begin{eqnarray*} c(n) \end{eqnarray*}$ für spezielle "Hilfstürme" löst diesen Knoten auf.

Damit machen die beiden o.g. Rekursionsgleichungen durchaus Sinn.

28.08.2021, 18:48

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
@Huggy

Ich bin nicht ganz hinter deine Fallunterscheidung gestiegen, aber mich beschleicht ein Verdacht:

Bildest du den Fall richtig ab, dass nur in der Grundschicht und in der Deckschicht des $\begin{eqnarray*} n \end{eqnarray*}$ -Turmes jeweils ein liegender Stein zu finden sind, und ansonsten der Turm nur aus stehenden Steinen besteht, immer paarweise gebündelt und um eine Höheneinheit gegen das nächste Paar versetzt?

Du hast Recht. Diese Möglichkeit habe ich übersehen.

28.08.2021, 18:50

sonny1001

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

P.S.: Meine Vermutung zur Bedeutung von b(n) und c(n) im Eröffnungsbeitrag:

b(n) ... Gesuchte Anzahl an Türmen der Höhe n
$\begin{eqnarray*} c(n) \end{eqnarray*}$ ... Anzahl an Türmen der Höhe $\begin{eqnarray*} n \end{eqnarray*}$ , wo ein in der Grundfläche liegender Platz 2x1x1 schon "vorbelegt" ist

Ist richtig.

Die algebraische Herleitung von $\begin{eqnarray*} b(n)=3b(n-1)+3b(n-2)-b(n-3) \end{eqnarray*}$ war mir klar. Es geht mir darum, durch Überlegungen direkt auf diese Rekurrenzgleichung zu kommen oder ist das nicht möglich. es müssen offensichtlich zuviel gezählte Möglichkeiten wieder abgezogen werden.

28.08.2021, 18:54

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von sonny1001
Die algebraische Herleitung von $\begin{eqnarray*} b(n)=3b(n-1)+3b(n-2)-b(n-3) \end{eqnarray*}$ war mir klar.

Das hättest du auch vorher sagen können, denn "Diese Gleichung kann ich nicht nachvollziehen" klingt für mich schon so, dass du das nicht hingekriegt hast. Hinterher durch solch altkluge Bemerkungen die Bemühungen der Helfer zu entwerten ist nicht sehr nett.

Zitat:

Original von sonny1001
Es geht mir darum, durch Überlegungen direkt auf diese Rekurrenzgleichung zu kommen oder ist das nicht möglich.

Zumindest ist der negative Vorfaktor vor b(n-3) ein Indiz, dass man nicht durch reine Additionen von Anzahlen für Türme niedrigerer Bauhöhe zu dieser Rekursionsgleichung kommen kann. Bei den "gemischten" Rekursionsgleichungen für b(n) und c(n) schafft man es rein mit Additionen - warum wohl?

---------------------------------------------------------------

Auch hier bekommt man über die charakteristische Gleichung $\begin{eqnarray*} 0 = \lambda^3-3\lambda^2-3\lambda+1 = \left(\lambda+1\right)\left(\lambda^2-4\lambda+1\right) \end{eqnarray*}$ den Ansatz

$\begin{eqnarray*} b(n) = C_1\cdot (-1)^n + C_2\cdot \left(2+\sqrt{3}\right)^n + C_3\cdot \left(2-\sqrt{3}\right)^n \end{eqnarray*}$ ,

was über die Startwerte $\begin{eqnarray*} b(0)=1,b(1)=2,b(2)=9 \end{eqnarray*}$ schließlich zu den gesuchten Koeffizienten $\begin{eqnarray*} C_1,C_2,C_3 \end{eqnarray*}$ führt, die dann

$\begin{eqnarray*} b(n) = \frac{1}{6}\left[ 2\cdot (-1)^n + \left(2+\sqrt{3}\right)^{n+1} + \left(2-\sqrt{3}\right)^{n+1}\right] \end{eqnarray*}$

ergeben. Ähnlich wie es Leopold im anderen Thread getan hat, kann man das auch zu $\begin{eqnarray*} b(n) = \left\lfloor \frac{\left(2+\sqrt{3}\right)^{n+1}}{6} + \frac{1}{2} \right\rfloor \end{eqnarray*}$ verkürzen.

28.08.2021, 20:30

sonny1001

Auf diesen Beitrag antworten »

"Das hättest du auch vorher sagen können, denn "Diese Gleichung kann ich nicht nachvollziehen" klingt für mich schon so, dass du das nicht hingekriegt hast. Hinterher durch solch altkluge Bemerkungen die Bemühungen der Helfer zu entwerten ist nicht sehr nett."

Es war nicht meine Absicht irgend jemand zu nahe zu treten oder seine Bemühungen zu entwerten. Ich wußte nicht, daß das so rüberkommt.

29.08.2021, 10:35

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von sonny1001
Die algebraische Herleitung von $\begin{eqnarray*} b(n)=3b(n-1)+3b(n-2)-b(n-3) \end{eqnarray*}$ war mir klar. Es geht mir darum, durch Überlegungen direkt auf diese Rekurrenzgleichung zu kommen oder ist das nicht möglich. es müssen offensichtlich zuviel gezählte Möglichkeiten wieder abgezogen werden.

Dafür habe ich eine Möglichkeit gefunden. Man beginnt mit einem unteren Abschluss gemäß deinen Fällen 1 bis 3. In den Fällen 1 und 2 kann darauf ein beliebiger Turm der Höhe $\begin{eqnarray*} n-1 \end{eqnarray*}$ bzw. $\begin{eqnarray*} n-2 \end{eqnarray*}$ gesetzt werden. Den Fall 3 setzt man bis zu einer Höhe $\begin{eqnarray*} i \end{eqnarray*}$ mit versetzt stehenden Steinen fort und schließt ihn in der Höhe $\begin{eqnarray*} i \end{eqnarray*}$ mit einem liegenden Stein ab. Es müssen alle Höhen $\begin{eqnarray*} i \end{eqnarray*}$ von $\begin{eqnarray*} 2 \end{eqnarray*}$ bis $\begin{eqnarray*} n \end{eqnarray*}$ berücksichtigt werden. Darauf kann dann ein beliebiger Turm der Höhe $\begin{eqnarray*} n-i \end{eqnarray*}$ gesetzt werden. Das führt zu:

$\begin{eqnarray*} b(n)=2b(n-1)+b(n-2)+4 \sum_{i=2}^n b(n-i)=2b(n-1)+b(n-2)+4 \sum_{i=0}^{n-2} b(i) \end{eqnarray*}$

$\begin{eqnarray*} b(n+1)-b(n)=2b(n)+3b(n-1)-b(n-2) \end{eqnarray*}$

$\begin{eqnarray*} b(n+1)=3b(n)+3b(n-1)-b(n-2) \end{eqnarray*}$

29.08.2021, 10:45

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
$\begin{eqnarray*} b(n)=2b(n-1)+b(n-2)+4 \sum_{i=2}^n b(n-i)=2b(n-1)+b(n-2)+4 {\color{red}\sum_{i=0}^{n-2} b(i)} \end{eqnarray*}$

Was letztlich sehr nah bei

Zitat:

Original von sonny1001
$\begin{eqnarray*} b(n)=2b(n-1)+b(n-2)+4{\color{red}c(n-1)} \end{eqnarray*}$
und
$\begin{eqnarray*} c(n)=b(n-1)+c(n-1) \end{eqnarray*}$

liegt, denn die zweite dieser beiden Gleichungen kann ja unmittelbar zu $\begin{eqnarray*} c(n)=b(n-1)+b(n-2)+\ldots \end{eqnarray*}$ expandiert werden.

Neue Frage »

Antworten »

Rekursionsgleichung für Turm

Verwandte Themen