Beispiellösungen zu Aufgabenblatt 65

aktualisiert: 8. November 2007

drucken Zum Ausdrucken als pdf-File oder als ps-File
Leider führte das automatische Konvertieren in das HTML-Format zu einigen Darstellungsfehlern, die wir nicht beheben können. Die HTML-Darstellung auf dieser Seite ist daher nur im nicht formelhaltigen Text korrekt und somit nur für einen Überblick über die Lösungen geeignet. Für korrekte Formeln und Bilder verweisen wir auf die PDF- oder PS-Version - und bitten um Verständnis.


Aufgabe 1


Welche regelmäßigen n-Ecke der Seitenlänge 1 kann man in kleinere regelmäßige Vielecke (nicht unbedingt n-Ecke!) der Seitenlänge 1 zerlegen und auf welche Art und Weisen ist dies gegebenenfalls machbar?


Lösung:


Wir betrachten ein regelmäßiges n-Eck (n $ \geq$ 3):

\includegraphics[width=46mm]{n_winkel}
Es bezeichne M seinen Mittelpunkt. Wie in der Grafik dargestellt, können wir über jeder Seite des n-Ecks ein gleichschenkliges Dreieck mit M als drittem Eckpunkt errichten. Der Winkel dieses Dreiecks in M ist jeweils $ \gamma$. Wir erhalten:

n . $\displaystyle \gamma$ = 360o $\displaystyle \Leftrightarrow$ $\displaystyle \gamma$ = $\displaystyle {\frac{{360^\circ}}{{n}}}$.

Für die Innenwinkel des n-Ecks folgt (Bezeichnungen siehe Skizze):

$\displaystyle \delta$ = $\displaystyle \alpha$ + $\displaystyle \beta$ = 180o - $\displaystyle {\frac{{360^\circ}}{{n}}}$ = $\displaystyle \left(\vphantom{1 -
\frac{2}{n}}\right.$1 - $\displaystyle {\frac{{2}}{{n}}}$$\displaystyle \left.\vphantom{1 -
\frac{2}{n}}\right)$180o.

Insbesondere ist jeder Innenwinkel kleiner als 180o. Genauer erhält man als Innenwinkel
für das regelmäßige Dreieck: 60o   
für das regelmäßige Viereck: 90o   
für das regelmäßige Fünfeck: 108o   
für das regelmäßige Sechseck: 120o   
für das regelmäßige Zwölfeck: 150o   
für das regelmäßige 30-Eck: 168o  .
Wir wollen nun das regelmäßige n-Eck in kleinere regelmäßige m-Ecke, jeweils mit Seitenlänge 1, zerlegen. Dabei beginnen wir in Punkt A. Wollen wir in diesem mehrere regelmäßige Vielecke so aneinander legen, dass sie sich zu einer Zerlegung des gesamten n-Ecks ergänzen lassen, müssen sich ihre Innenwinkel zu $ \delta$ addieren.


Da für m $ \geq$ 3 jeder Punkt eines regelmäßigen m-Ecks einen Innenwinkel von mindestens 60o, jeder Punkt eines n-Eck jedoch einen Innenwinkel von weniger als 180o hat, können wir in A maximal zwei Vielecke zusammenlegen (wobei wir bei nur einem Vieleck das n-Eck selbst erhalten).


Wir beginnen mit zwei regelmäßigen Dreiecken. In diesem Fall erhalten wir als $ \delta$ = 60o + 60o = 120o den Innenwinkel eines Eckpunktes eines regelmäßigen Sechsecks.

Tatsächlich lässt sich das regelmäßige Sechseck in sechs regelmäßige Dreiecke zerlegen:

\includegraphics[width=48mm]{sechseck}

Nun versuchen wir es mit einem regelmäßigen Dreieck und einem regelmäßigen Viereck. In diesem Fall erhalten wir als $ \delta$ = 60o + 90o = 150o den Innenwinkel eines Eckpunktes eines regelmäßigen Zwölfecks.


Wir setzen also auf jede Kante eines regelmäßigen Zwölfecks abwechselnd ein Drei- und ein Viereck. Nach innen hin schließt jeweils eine Kante eines Vierecks ab und wir erhalten ein Sechseck. An jedem Punkt dieses Sechsecks liegen außen zwei Vierecke und ein Dreieck an, wodurch wir als Innenwinkel jeweils 360o - 2 . 90o - 60o = 120o erhalten. Das Sechseck ist also regelmäßig und hat die Seitenlänge 1 (denn jedes der verwendeten Vierecke hat die Seitenlänge 1).

Es ergibt sich daher:

\includegraphics[width=46mm]{zwoelfeck1}

Natürlich lässt sich das innere regelmäßige Sechseck wiederum in sechs Dreiecke zerlegen. Man erhält dann eine Zerlegung in sechs Vier- und zwölf Dreiecke:

\includegraphics[width=46mm]{zwoelfeck2}

Als Nächstes testen wir das Zusammensetzen eines Dreiecks und eines Fünfecks. Es ergibt sich dann als Innenwinkel $ \delta$ = 60o + 108o = 168o. Dies ist der Innenwinkel eines Punktes eines regelmäßigen 30-Ecks. Setzen wir nun wie oben auf jede Kante eines regelmäßigen 30-Ecks abwechselnd ein regelmäßiges Dreieck und ein Fünfeck, so erhalten wir innen (wo jeweils zwei Kanten eines Fünfecks abschließen) ein (nicht konvexes) 30-Eck. An jedem zweiten Eckpunkt dieses 30-Ecks liegen ein Dreieck und zwei Fünfecke an und wir erhalten den Innenwinkel 360o - 2 . 108o - 60o = 84o. Dieser Winkel ist jedoch weder selbst Innenwinkel eines regelmäßigen n-Ecks noch ist er Summe zweier solcher Innenwinkel. Demnach ist eine solche Zerlegung nicht möglich.


Auch lassen sich keine weiteren Zerlegungen realisieren, da sich sowohl beim Zusammensetzen zweier Vierecke als auch eines Drei- und eines Sechsecks ein Winkel von 180o ergibt. Alle Innenwinkel eines n-Ecks (n $ \geq$ 3) sind jedoch kleiner als 180o. Bei allen anderen Kombinationen würde der Innenwinkel noch größer werden.


Es lassen sich also nur das regelmäßige Sechs- und Zwölfeck in andere regelmäßige Vielecke gleicher Kantenlänge zerlegen.



Aufgabe 2


Käpt'n Sperling hat elf Kandidaten für seine Piratentruppe gefunden. Zu Beginn muss er sie aber in piratöser Lebensweise unterrichten. Heute steht das Lügen auf dem Programm - das soll ja nicht etwa plump sein!

Der Käpt'n sagt: ,,Jungs, ich weiß, dass ihr alle aus Schwarzdorf oder aus Knochenbrück kommt, aber ich weiß nicht, wer woher ist. Sagt mir, woher ihr kommt - aber denkt daran: Keiner darf die Wahrheit sagen.``

Die Nr. 1 (alle anderen Neuen stehen in schöner Reihe links von ihm) sagt: ,,Die Zahl der Männer aus Schwarzdorf ist eine Quadratzahl.`` Nr. 2, 3, 6, 7 und 9 sagen: ,,Ich komme nicht aus derselben Stadt wie mein rechter Nachbar.`` Hingegen behaupten Nr. 4, 5, 10 und 11: ,,Ich komme aus derselben Stadt wie mein rechter Nachbar.`` Schließlich stellt Nr. 8 fest: ,,Aus Knochenbrück kommt eine ungerade Zahl Männer.``

Der Käpt'n ist zufrieden mit seinen neuen Mannen - wer kommt woher?


Lösung:


Der Einfachheit halber benutzen wir im Folgenden das Symbol \includegraphics[width=0.33cm]{haus}, das nichts anderes bedeuten soll, als ,,wohnt in derselben Stadt wie``.

1 \includegraphics[width=0.33cm]{haus}2 bedeutet also, dass Nr. 1 in derselben Stadt wohnt wie Nr. 2, und 2 \includegraphics[width=0.33cm]{nhaus}3 steht dafür, dass Nr. 2 nicht in derselben Stadt wohnt wie Nr. 3.


Betrachten wir zunächst die Aussagen von Nr. 2, 3, 6, 7 und 9: Da alle gelogen haben, wissen wir, dass jeder von ihnen aus derselben Stadt kommt wie sein rechter Nachbar. Es gilt also 1 \includegraphics[width=0.33cm]{haus}2 \includegraphics[width=0.33cm]{haus}3, 5 \includegraphics[width=0.33cm]{haus}6 \includegraphics[width=0.33cm]{haus}7 sowie 8 \includegraphics[width=0.33cm]{haus}9.

Unseren momentanen Informationsstand können wir folgendermaßen darstellen, wobei ein gleicher Buchstabe bedeutet, dass die Jungs aus derselben Stadt kommen, verschiedene Buchstaben aber nicht unbedingt eine unterschiedliche Heimat bedeuten. Ein leeres Feld heißt, dass wir noch nichts über diese Nummer wissen:

rechts (aus 1 2 3 4 5 6 7 8 9 10 11 links (aus
Piratensicht) a a a   b b b c c     Piratensicht)
   

Auch Nr. 4, 5, 10 und 11 haben geschwindelt. Jeder von ihnen kommt daher nicht aus derselben Stadt wie sein rechter Nachbar. Also: 4 \includegraphics[width=0.33cm]{nhaus}3, 2, 1 und 7, 6, 5 \includegraphics[width=0.33cm]{nhaus}4. Da es nur zwei mögliche Städte gibt, folgt 1 \includegraphics[width=0.33cm]{haus}2 \includegraphics[width=0.33cm]{haus}3 \includegraphics[width=0.33cm]{haus}5 \includegraphics[width=0.33cm]{haus}6 \includegraphics[width=0.33cm]{haus}7 \includegraphics[width=0.33cm]{nhaus}4. Aus den Aussagen von Nr. 10 und 11 können wir schließen, dass 8 \includegraphics[width=0.33cm]{haus}9 \includegraphics[width=0.33cm]{haus}11 \includegraphics[width=0.33cm]{nhaus}10 gilt.

Nun gibt es folgende zwei Möglichkeiten:

rechts 1 2 3 4 5 6 7 8 9 10 11 links
1. Möglichkeit a a a b a a a a a b a  
2. Möglichkeit a a a b a a a b b a b  
   

Durch die Aussagen von Nr. 1 und 8 wissen wir, dass die Anzahl der Männer aus Schwarzdorf keine Quadratzahl ist und dass die Anzahl der Männer aus Knochenbrück gerade sein muss.

Angenommen, Nr. 1 kommt aus Knochenbrück, so gibt es folgende Möglichkeiten:

rechts 1 2 3 4 5 6 7 8 9 10 11 links
1. Möglichkeit K K K S K K K K K S K  
2. Möglichkeit K K K S K K K S S K S  
   

In beiden Fällen wäre die Anzahl der aus Knochenbrück kommenden Männer ungerade. Pirat Nr. 1 muss also aus Schwarzdorf kommen. Wir erhalten:

rechts 1 2 3 4 5 6 7 8 9 10 11 links
1. Möglichkeit S S S K S S S S S K S  
2. Möglichkeit S S S K S S S K K S K  
   

Bei der ersten Möglichkeit ist die Anzahl der aus Schwarzdorf kommenden Männer 9 und also eine Quadratzahl. Diese Möglichkeit scheidet daher auch aus.

Es bleibt nur noch die zweite Möglichkeit, in der tatsächlich alle Bedingungen erfüllt sind:

rechts 1 2 3 4 5 6 7 8 9 10 11 links
  S S S K S S S K K S K  
   



Aufgabe 3


Ein ,,Pythagorasbaum`` entsteht, wenn man auf ein Quadrat der Seitenlänge 1 als Stamm ein rechtwinkliges Dreieck mit seiner Hypotenuse aufsetzt, dann die beiden Kathetenquadrate zeichnet und dann weiter beliebig (aber endlich) oft auf irgendein schon gezeichnetes Quadrat wieder ein dem ursprünglichen rechtwinkligen Dreieck ähnliches rechtwinkliges Dreieck aufsetzt (der Ästhetik zuliebe gleichorientiert zum ersten) und dann wieder die beiden Kathetenquadrate einzeichnet usw.

Die ,,äußeren`` Quadrate am Baum werden ,,Blätter`` des Baumes genannt. Die folgende Abbildung zeigt einen Baum mit drei verschieden großen Blättern.

\includegraphics[width=5cm]{pythagorasbaum2}

Gibt es einen Pythagorasbaum mit mehr als 1000 Blättern, aber nur zwei verschiedenen Blattgrößen, bei dem das verwendete Dreieck nicht gleichschenklig ist?


Lösung:


Ja, solch einen Baum gibt es, nämlich eine Art ,,Goldener-Schnitt-Baum``, den wir im Folgenden konstruieren werden.


Wir wählen das Dreieck mit den Seitenlängen

c = 1    und    a : = $\displaystyle \psi$    und    b : = $\displaystyle \sqrt{{\psi}}$,    

wobei

$\displaystyle \psi$ = $\displaystyle {\frac{{- 1 + \sqrt{5}}}{{2}}}$ $\displaystyle \approx$ 0, 618...    

das Inverse des sogenannten Goldenen Schnittes ist. Dieses Dreieck ist nach der Umkehrung des Satzes des Pythagoras tatsächlich rechtwinklig, denn es erfüllt

a2 + b2 = $\displaystyle \psi^{2}_{}$ + $\displaystyle \psi$ = $\displaystyle {\frac{{1-2\sqrt{5}+5}}{{4}}}$ + $\displaystyle {\frac{{- 1 + \sqrt{5}}}{{2}}}$ = 1 = c2.    

Zu diesem Zeitpunkt haben wir Blätter in den beiden Größen a2 = $ \psi^{2}_{}$ und b2 = $ \psi$. Die Anzahl der kleineren Blätter sei mit A1, die der größeren Blätter mit B1 bezeichnet. Es ist dann A1 = B1 = 1.


Jedes zum ersten Dreieck ähnliche Dreieck mit den Seiten a', b', c' erfüllt

$\displaystyle {\frac{{a'}}{{c'}}}$ = $\displaystyle {\frac{{a}}{{c}}}$ = $\displaystyle \psi$    und    $\displaystyle {\frac{{b'}}{{c'}}}$ = $\displaystyle {\frac{{b}}{{c}}}$ = $\displaystyle \sqrt{{\psi}}$,    

also

a' = $\displaystyle \psi$ . c'    und    b' = $\displaystyle \sqrt{{\psi}}$ . c'.    


Wir setzen nun auf das Blatt mit der größeren Seitenlänge - das ist b - ein neues Dreieck. Dieses hat dann die Seitenlängen

c2 = b = $\displaystyle \sqrt{{\psi}}$,    a2 = $\displaystyle \psi$ . c2 = $\displaystyle \psi$$\displaystyle \sqrt{{\psi}}$,    b2 = $\displaystyle \sqrt{{\psi}}$ . c2 = $\displaystyle \psi$,    

und es liefert uns zwei neue Blätter, eines von Größe a22 = $ \psi^{3}_{}$ und eines von Größe b22 = $ \psi^{2}_{}$. Von zuvor haben wir noch ein Blatt der Größe a2 = $ \psi^{2}_{}$, das andere Blatt hingegen ist zu einem Teil des Stammes geworden.

Insgesamt haben wir nun A2 : = 1 = B1 Blätter der kleineren Größe $ \psi^{3}_{}$ und B2 : = 1 + 1 = B1 + A1 Blätter der größeren Größe $ \psi^{2}_{}$.


Im nächsten Schritt setzen wir wiederum auf alle B2 Blätter der größeren Sorte ein Dreieck. Diese haben die Seitenlängen

c3 = b2 = $\displaystyle \psi$,    a3 = $\displaystyle \psi$ . c3 = $\displaystyle \psi^{2}_{}$,    b3 = $\displaystyle \sqrt{{\psi}}$ . c3 = $\displaystyle \sqrt{{\psi}}$ . $\displaystyle \psi$.    

Die B2 ehemals großen Blätter werden ein Teil des Stammes und es entstehen B2 neue Blätter der Größe a32 = $ \psi^{4}_{}$ und B2 neue Blätter der Größe b32 = $ \psi^{3}_{}$. Insgesamt haben wir dann A3 = B2 Blätter der kleineren Größe $ \psi^{4}_{}$ und B3 = B2 + A2 Blätter der größeren Größe $ \psi^{3}_{}$.


Abbildung: Der Baum nach 1, 2 bzw. 3 Schritten
\includegraphics[width=20mm]{pythbaum01} \includegraphics[width=30mm]{pythbaum02} \includegraphics[width=40mm]{pythbaum03}
Dies machen wir nun so weiter: Haben wir im n-ten Schritt Bn große Blätter der Größe bn2 = $ \psi^{n}_{}$ und An kleine Blätter der Größe an2 = $ \psi^{{n+1}}_{}$, so setzen wir auf alle Bn Blätter der größeren Größe Dreiecke mit den Seitenlängen

cn+1 = bn = $\displaystyle \sqrt{{\psi^n}}$,    
an+1 = $\displaystyle \psi$ . cn+1 = $\displaystyle \sqrt{{\psi^{n+2}}}$,    
bn+1 = $\displaystyle \sqrt{{\psi}}$ . cn+1 = $\displaystyle \sqrt{{\psi^{n+1}}}$    

und erhalten zusätzlich zu den An ehemals kleinen Blättern der Größe an2 = $ \psi^{{n+1}}_{}$ noch je Bn Blätter der Größen bn+12 = $ \psi^{{n+1}}_{}$ und an+12 = $ \psi^{{n+2}}_{}$ hinzu. Insgesamt haben wir dann also wieder nur Blätter in zwei Größen, nämlich

Bn+1 = Bn + An /TD> große Blätter der Größe /TD> bn+12 = $\displaystyle \psi^{{n+1}}_{}$    
An+1 = Bn   kleine Blätter der Größe   an+12 = $\displaystyle \psi^{{n+2}}_{}$.    


Unsere Konstruktion liefert demnach in jedem Schritt einen Pythagorasbaum, der genau zwei verschiedene Blattgrößen hat.

Abbildung: Goldener-Schnitt-Pythagorasbaum nach 10 Schritten
\includegraphics[width=110mm]{pythbaum10}


Außerdem wird in jedem Schritt die Anzahl der Blätter größer, denn an jedes Blatt, das zu einem Teil des Stammes wird, werden zwei neue Blätter angehängt.

Mit einer ganz groben Abschätzung folgt, dass wir spätestens nach 1000 Schritten 1000 Blätter haben. Damit sind wir fertig.

Abbildung: Goldener-Schnitt-Pythagorasbaum nach 15 Schritten
\includegraphics[width=\textwidth]{pythbaum15}


Wir können die Anzahl der Blätter aber auch genau ausrechnen: Nach dem ersten Schritt (d. h. wir haben genau ein Dreieck, das wir auf den Stamm aufgesetzt hatten) haben wir A1 + B1 = 1 + 1 = 2 Blätter. Nach dem n-ten Schritt haben wir An + Bn Blätter. Für die einzelnen Anzahlen gilt

B1 = 1,    B2 = 2    und    Bn+1 = Bn + An = Bn + Bn-1.    

Die Bn bilden die unter Mathematikern wohlbekannte Fibonacci-Folge:

(1,)1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,...    

Es gilt B15 = 987 und A15 = B14 = 610. Nach 15 Schritten haben wir demnach bereits 987 + 610 = 1597 Blätter.


Bemerkung: Dieser Goldener-Schnitt-Baum ist der einzige Baum, bei dem das verwendete Dreieck nicht gleichseitig ist und der nur zwei verschiedene Blattgrößen hat.

Beweisidee: An den ,,Enden`` jeder Verästelung entsteht ein Teil-Pythagorasbaum mit drei Blättern. Auch dieser darf dann nur zwei verschiedene Blattgrößen haben. Sind a, b, c die Seitenlängen des größeren Dreiecks, so haben die drei Blätter die Größen a2, $ {\frac{{b^4}}{{c^2}}}$ und $ {\frac{{a^2 b^2}}{{c^2}}}$. Damit müssen die beiden Blätter mit den Größen a2 und $ {\frac{{b^4}}{{c^2}}}$ gleich groß sein. Stellen wir dieses um und nutzen noch aus, dass a2 + b2 = c2 gilt, so erhalten wir, dass auch hier - wie bei dem oben konstruierten Baum - die Beziehungen $ {\frac{{a}}{{c}}}$ = $ \psi$ und $ {\frac{{b}}{{c}}}$ = $ \sqrt{{\psi}}$ gelten.



Aufgabe 4


Auf wie viele Art und Weisen kann man Spielsteine so auf ein 3×10-Spielbrett setzen, dass keine zwei Steine horizontal, vertikal oder diagonal benachbart sind?


Lösung:


Es gibt genau 47003 Möglichkeiten, Steine unter den erlaubten Regeln auf das Spielbrett zu setzen.


Dabei haben wir auch die eine Möglichkeit mitgezählt, gar keinen Stein auf das Brett zu setzen. Ob man diese Möglichkeit mitzählen möchte oder nicht, ist eine Geschmacksfrage, auf jeden Fall macht sie unsere Rechnungen einfacher.


Wir berechnen die Anzahl der Möglickeiten rekursiv, indem wir zuerst zählen, wie viele Möglichkeiten es bei einer Spalte (d. h. bei einem 3×1-Spielbrett) gibt, dann, wie viele es bei zwei Spalten (d. h. bei einem 3×2-Spielbrett) gibt, und so weiter bis zu einem 3×10-Spielbrett. Rekursiv heißt dabei, dass wir immer die alte Anzahl nutzen wollen, um die Anzahl bei einer weiteren Spalte auszurechnen.


Dazu unterteilen wir die Gesamtanzahl in gewisse Unteranzahlen, je nachdem, wo die Steine in der letzten Spalte liegen:

an sei die Gesamtanzahl aller Möglichkeiten bei n Spalten,
  inklusive der Möglichkeit gar keinen Stein zu verteilen
$ \ell_{n}^{}$ die letzte (n-te) Spalte ist leer
mn in der letzten Spalte liegt ein Stein in der Mitte
bn in der letzten Spalte liegt oben und unten je ein Stein
on in der letzten Spalte liegt nur oben ein Stein
un in der letzten Spalte liegt nur unten ein Stein
Spiegelt man eine Verteilung, bei der in der letzten Spalte nur oben ein Stein liegt, an der Waagerechten, so erhält man eine Verteilung, die in der letzten Spalte nur unten einen Stein hat. Es gilt also on = un.


Jetzt nehmen wir eine neue ((n + 1)-te) Spalte hinzu. Jede alte Möglichkeit liefert eine neue, bei der die neue letzte Spalte leer bleibt. In die Mitte oder gleichzeitig nach oben und unten der neuen letzten Spalte können wir nur dann einen bzw. zwei Steine legen, wenn die n-te Spalte leer ist. Nach unten können wir einen Stein legen, wenn die n-te Spalte leer ist oder wenn in der n-ten Spalte nur oben ein Stein liegt. Wir erhalten die Formeln

$\displaystyle \ell_{{n+1}}^{}$ = an    
mn+1 = $\displaystyle \ell_{n}^{}$    
bn+1 = $\displaystyle \ell_{n}^{}$    
un+1 = $\displaystyle \ell_{n}^{}$ + on = $\displaystyle \ell_{n}^{}$ + un.    

Nutzen wir dabei aus, dass dann auch $ \ell_{n}^{}$ = an-1 gilt, so wird die letzte Formel zu

un+1 = $\displaystyle \ell_{n}^{}$ + un = an-1 + un    

und die Gesamtanzahl berechnet sich als

an+1 = $\displaystyle \ell_{{n+1}}^{}$ + mn+1 + bn+1 + 2 . un+1    
  = an + $\displaystyle \ell_{n}^{}$ + $\displaystyle \ell_{n}^{}$ + 2 . an-1 + 2 . un    
  = an + 4 . an-1 + 2 . un.    

Um die Anzahl der Möglichkeiten dann tatsächlich auszurechnen, brauchen wir zusätzlich zu den beiden Rekursionsformeln für an+1 und un+1 noch einige Anfangswerte.

Haben wir nur eine Spalte, so ist $ \ell_{1}^{}$ = m1 = b1 = u1 = 1, was zusammen a1 = $ \ell_{1}^{}$ + m1 + b1 + 2u1 = 5 ergibt. Jetzt haben wir einen Anfangswert für un und einen für an. Da die Rekursionsformel für an+1 aber immer zwei vorhergende Werte benutzt, müssen wir noch an für einen zweiten Wert bestimmen. Wir könnten a2 ausrechnen; einfacher ist es aber, noch a0 hinzuzunehmen. Es ist a0 = 1, denn auf null Spalten kann man keinen Stein legen, aber gar keinen Stein zu verteilen, wollten wir ja auch als eine erlaubte Möglichkeit mitzählen. - Oder wir begründen den Wert a0 = 1 durch: Der Summand an-1 kam dadurch in die Formel, dass wir die Rekursionsformel $ \ell_{{n+1}}^{}$ = an auch für (n - 1) + 1 angewandt haben: $ \ell_{n}^{}$ = an-1. Umgekehrt ist dann aber auch a0 = a1-1 = $ \ell_{1}^{}$ = 1.


Nun haben wir alle Formeln zusammen. Es gilt

a0 = 1, a1 = 5, u1 = 1    

für die Anfangswerte, und die benötigten Rekursionsformeln sind

an+1 = an + 4 . an-1 + 2 . un          fürn $\displaystyle \geq$ 1,    
un+1 = an-1 + un   fürn $\displaystyle \geq$ 1.    

Damit berechnen wir dann nacheinander

a2 = a1 + 4a0 + 2u1 u2 = a0 + u1    
  = 5 + 4 . 1 + 2 . 1 = 11   = 1 + 1 = 2    
a3 = a2 + 4a1 + 2u2 u3 = a1 + u2    
  = 11 + 4 . 5 + 2 . 2 = 35   = 5 + 2 = 7    
a4 = 35 + 4 . 11 + 2 . 7 = 93 u4 = 11 + 7 = 18    
a5 = 93 + 4 . 35 + 2 . 18 = 269 u5 = 35 + 18 = 53    
a6 = 269 + 4 . 93 + 2 . 53 = 747 u6 = 93 + 53 = 146    
a7 = 747 + 4 . 269 + 2 . 146 = 2115 u7 = 269 + 146 = 415    
a8 = 2115 + 4 . 747 + 2 . 415 = 5933 u8 = 747 + 415 = 1162    
a9 = 5933 + 4 . 2115 + 2 . 1162 = 16717 u9 = 2115 + 1162 = 3277    
a10 = 16717 + 4 . 5933 + 2 . 3277 = 47003      

Insgesamt gibt es somit 47003 Möglichkeiten, Steine nach den geforderten Regeln auf dem 3×10-Spielbrett zu verteilen.

Oder, falls man die Möglichkeit ohne Steine nicht mitzählen möchte: Es gibt 47002 Möglichkeiten, einen oder mehrere (mehr als 10 sind übrigens nicht möglich) Steine nach den geforderten Regeln auf dem 3×10-Spielbrett zu verteilen.


drucken Zum Ausdrucken als pdf-File oder als ps-File