Bänder

26.06.2006, 18:26

Kitkat

Bänder

Hey Leute,
ich habe da ein kleines Problem mit einer Aufgabe. Ich habe zwar eine Idee, wie man es lösen könnte, doch diese ist soo lang. Vielleicht könnt ihr mir ja da weiterhelfen.

Zur Dekoration eines Raumes sollen 2m lange Bänder aus kürzeren Bandstücken zusammengenäht werden. Zur Verfügung stehen: Blaue Stücke der Länge 10cm, rote Stücke der Länge 20cm und gelbe Stücke der Länge 30cm, jeweils in genügender Anzahl. Beim Zusammennähen sollen niemals zwei einander gleichfarbige Stücke nebeneinander kommen. Wie viele Bänder können insgesamt hergestellt werden?

Hinweis: "Anfang" und "Ende" eines fertigen Bandes sind zu unterscheiden, weil am Anfang eine Schlaufe zum Aufhängen angebracht ist. Zwei fertige Bänder gelten dann als voneinander verschieden, wenn sie sich in der Reihenfolge der Farben, vom "Anfang" an aufgezählt, unterscheiden.

Ich hätte halt erstmal alle Möglichkeiten herausgesucht, die noch dazu eine verschiedene Anzahl der einzelnen Bandstücke haben. Doch dann müsste ich alle diese einzelnen Möglichkeiten ja nochmals einzeln bearbeiten, dadurch sie in verschiedenen Reihenfolgen möglich sind. Bei manchen Fällen ist dies ja recht einfach, da es nicht so viele gibt, doch es gibt auch welche, wo es so viele sind, dass es total unübersichtlich wird. Gibt es da irgendeinen Trick?

26.06.2006, 22:19

PrototypeX29A

Auf diesen Beitrag antworten »

Ich wuerd eine Tabelle machen in der ich in einer Achse die drei Farben Eintrage und in der anderen alle Laengen bis 2m in 10cm-Schritten. In die Felder der Tabelle die Anzahl der Moeglichkeiten Baender mit der angegebenen Laenge zu machen die mit der Angegebenen Farbe aufhoeren:

Anzahl der 10 cm langen Baender. die am Ende blau sind = 1 (ein blaues Bandstueck)
Anzahl der 10 cm langen Baender, die am Ende rot sind = 0 (geht nicht)
Anzahl der 10 cm langen Baender, die am Ende gelb sind = 0 (geht nicht)

Anzahl der 20 cm langen Baender. die am Ende blau sind = 0 (geht nicht)
Anzahl der 20 cm langen Baender, die am Ende rot sind = 1 (ein rotes Bandstueck)
Anzahl der 20 cm langen Baender, die am Ende gelb sind = 0 (geht nicht)

Anzahl der 30 cm langen Baender. die am Ende blau sind = 1 (ein rotes und ein blaues Bandstueck)
Anzahl der 30 cm langen Baender, die am Ende rot sind = 1 (ein blaues und ein rotes Bandstueck)
Anzahl der 30 cm langen Baender, die am Ende gelb sind = 1 (ein gelbes Bandstueck)

Alle folgenden Baender kannst du aus den schon berechneten Stuecken zusammensetzen:

Denn ein 40 cm langes Band mit blau am Ende besteht aus einem 30cm langen Band mit rot oder gelb am Ende + ein blaues Bandstueck.

Ein 40 cm langes Band mit rot am Ende besteht aus einem 20cm langen Band mit blau oder gelb am
Ende + ein rotes Bandstueck.

Ein 40 cm langes Band mit gelb am Ende besteht aus einem 10cm langen Band mit blau oder rot am Ende + ein gelbes Bandstueck.

Die Werte musst du dann nur noch in der Tabelle nachgucken. Damit musst du "nur" 60 Zahlen ausrechnen smile

Am Ende der Tabelle hast du die Moeglichkeiten fuer 200 cm lange Baender mit rot am Ende, fuer 200 cm lange Baender mit blau am Ende und fuer 200 cm lange Baender mit gelb am Ende stehen.
Die musst du dann nur noch zusammenzaehlen.

Ich hoffe einigermassen verstaendlich,
Gruss,
ProtoX29A

PS: Es sollte auch Loesungen in logarithmischer Laufzeit geben, aber ich denke die sind erst bei Baendern mit mehreren Metern Laenge lohnenswert...

26.06.2006, 23:30

Sciencefreak

Auf diesen Beitrag antworten »

Ne rukursive Folge könnte man leicht aufstellen. Dazu nimmt man sich einfach 3 Unterfolgen $\begin{eqnarray*} r_n \end{eqnarray*}$ $\begin{eqnarray*} g_n \end{eqnarray*}$ $\begin{eqnarray*} b_n \end{eqnarray*}$ für die Anzahl der Möglichkeiten ein Band der Länge n*10cm herzustellen, dass auf rot(r), gelb(g) oder blau(b) endet. Dann gilt:
$\begin{eqnarray*} b_1=1 \end{eqnarray*}$
$\begin{eqnarray*} r_2=1 \end{eqnarray*}$
$\begin{eqnarray*} g_3=1 \end{eqnarray*}$
Und als Rekursionsvorschrift gilt
$\begin{eqnarray*} b_n=r_{n-1}+g_{n-1} \end{eqnarray*}$
$\begin{eqnarray*} r_n=b_{n-2}+g_{n-2} \end{eqnarray*}$
$\begin{eqnarray*} b_n=r_{n-3}+b_{n-3} \end{eqnarray*}$
Und das kann man mit dem Rechner schön berechnen und vielleicht sogar mit etwas Mühe eine explizite Darstellung finden, aber dafür bin ich jetzt zu müde.
Edit:Wenns mans auf dem Rechner machen will, müsste man noch die Folgenwerte mit Index -1 und -2 ergänzen, welche natürlich auch 0 sind.
Edit2:ich seh gerade, dass diese Varainte bereits erwähnt wurde, nur dass sich jemand die Mühe gemacht hatte einen Roam draus zu formen, welchen ich mir nicht durchgelsen hatte
Edit3:Zum Glück ist niemand der Fehler bei den Startwerten aufgefallen smile

27.06.2006, 10:04

Auf diesen Beitrag antworten »

Zitat:

Original von Sciencefreak
und vielleicht sogar mit etwas Mühe eine explizite Darstellung finden

Das dürfte ziemlich eklig werden, aber es ist möglich. Ein systematischer Weg dazu führt über lineare Algebra: Man definiert den 9-elementigen Vektor $\begin{eqnarray*} x_n=(b_n,r_n,g_n,b_{n-1},r_{n-1},g_{n-1},b_{n-2},r_{n-2},g_{n-2})^t \end{eqnarray*}$ und kann dann durch Umschreiben von Sciencefreaks Rekursionsgleichungen für diesen eine Rekursion $\begin{eqnarray*} x_n=A\cdot x_{n-1} \end{eqnarray*}$ mit einer quadratischen 9x9-Matrix $\begin{eqnarray*} A \end{eqnarray*}$ aufstellen. Mit der Jordanzerlegung $\begin{eqnarray*} A=UJU^{-1} \end{eqnarray*}$ ergibt sich für $\begin{eqnarray*} y_n:=U^{-1}x_n \end{eqnarray*}$ die rekursive Darstellung $\begin{eqnarray*} y_n=J\cdot y_{n-1} \end{eqnarray*}$ und somit die explizite Darstellung $\begin{eqnarray*} y_n=J^{n-3}\cdot y_3 \end{eqnarray*}$ , d.h., $\begin{eqnarray*} x_n= UJ^{n-3}U^{-1}\cdot x_3 \end{eqnarray*}$ .

Dummerweise ist bei der Diagonalisierung einer 9x9-Matrix mit nicht sehr angenehm darstellbaren Eigenwerten zu rechnen, so dass ich persönlich diese Betrachtungen nur anstellen würde, um etwa das geometrische Wachstum der Anzahlfolge geeignet abzuschätzen.

Ergänzung:

Wenn ich MuPad trauen darf, wird das Wachstum der Anzahlfolge $\begin{eqnarray*} b_n+r_n+g_n \end{eqnarray*}$ dominant bestimmt durch die einzige reelle Wurzel von $\begin{eqnarray*} \lambda^5-\lambda^4+\lambda^3-2\lambda^2+\lambda-2=0 \end{eqnarray*}$ , das ist $\begin{eqnarray*} \lambda_0\approx 1.424 \end{eqnarray*}$ . Somit gilt für große $\begin{eqnarray*} n \end{eqnarray*}$ näherungsweise $\begin{eqnarray*} b_n+r_n+g_n\approx C\cdot \lambda_0^n \end{eqnarray*}$ mit einer noch zu bestimmenden Konstante $\begin{eqnarray*} C>0 \end{eqnarray*}$ .

27.06.2006, 16:38

grybl

Auf diesen Beitrag antworten »

fällt eigentlich nicht in die Kategorie Rätsel (hier sollte der Rätselsteller schon die Lösung wissen Augenzwinkern

), ich verschiebs mal in Sonstiges, wer was besseres meint verschiebts halt weiter smile

27.06.2006, 20:26

Kitkat

Auf diesen Beitrag antworten »

Naja.....okay
nur das ich die letzten beiden nicht versteh, denn ich geh ja erst in die 9. Klasse und habe weder von Rekursionsgleichung noch von einer rukursiven Folge gehört.
Kann man das auch mit dem Wissen, was man bis zur 9ten Klasse gelernt hat, irgendwie lösen?

28.06.2006, 09:26

Auf diesen Beitrag antworten »

Ohne jegliches Basisverständnis von Rekursion ist es schwierig, ich würde sogar sagen unmöglich, die Lösung dieser Aufgabe zu verstehen. Wenn du letztere willst, musst du dich wohl oder übel da etwas reinknien, auch wenn es noch nicht Schulstoff deiner Altersstufe ist. Oder du geduldest dich eben, bis es dran kommt (Folgen und Reihen - Klasse 11? verwirrt

28.06.2006, 14:23

Sciencefreak

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Oder du geduldest dich eben, bis es dran kommt (Folgen und Reihen - Klasse 11? verwirrt

ich habe so was noch nicht in der Schule gehabt, bzw noch nicht so tiefgehend. Irgendwann hatte man mal so was wie geometrische Reihe oder arithmetische Reihe erste Ordnung, aber mehr auch nicht.

29.06.2006, 20:41

Kitkat

Auf diesen Beitrag antworten »

Also ich hätte versucht den Text über die Rekursion zu lesen und zu verstehen. Am letzteren bin ich allerdings gescheitert und das schon ziemlich bald. Nämlich schon beim zweiten Satz:-)
"Die gegenseitige Rekursion bildet sich durch den gegenseitigen Verweis zweier oder mehrerer Funktionen aufeinander"
Was genau heißt denn das?

30.06.2006, 12:57

Auf diesen Beitrag antworten »

Hallo kitkat,

die Verlinkung des Wikipedia-Artikels war ein Fehler von mir, der ist wohl etwas zu komplex und schwer verständlich - tut mir leid.

Ich füge mal eine Tabelle von Folgenwerten obiger Rekursion an:

n _| 1 _2 _3 _4 _5 _6 _7 _8 _9 _10 _11 _12
---+--------------------------------------
b _| 1 _0 _1 _2 _1 _3 _5 _4 _8 _13 _14 _23
r _| 0 _1 _1 _0 _2 _3 _2 _5 _7 __7 _14 _20
g _| 0 _0 _1 _1 _1 _2 _2 _3 _6 __7 __9 _15

Die blauen, roten und grünen Werte der letzten Spalte entstehen jeweils als Summe der zwei gleichfarbig markierten Zahlen in den Spalten vorher - so funktioniert hier diese Rekursion.

So kommt also zustande, dass es bei den Bändern von 130cm Länge genau 23 auf blau enden, 20 auf rot und 15 auf grün. Insgesamt gibt es also 23+20+15=58 verschiedene Bänder der Länge 130cm.

Und diese Tabelle kannst du jetzt bis n=20 fortführen.

01.07.2006, 10:34

Kitkat

Auf diesen Beitrag antworten »

Okay, wenn ich jetzt das so weiter mache komme ich bei n=20 auf b=379, r=311 und g=238. Somit gäbe es also 928 Möglichkeiten. Wenn man das beweisen müsste, schreibt man das einfach so als Tabelle hin und verweist auf die Rekursion?
Wie bekommt man die Anfangswerte, das sind doch die Möglichkeiten, die es bei so vielen cm gibt, oder?
Die ersten drei Spalten muss man noch ausfüllen, ab dann kann man es so rechnen, aber warum?
Bei n=12 sind es aber schon 120cm und nicht 130, oder? :-)

01.07.2006, 12:24

Auf diesen Beitrag antworten »

Zitat:

Original von Kitkat
Wie bekommt man die Anfangswerte, das sind doch die Möglichkeiten, die es bei so vielen cm gibt, oder?

Tja, das kann man ja noch von Hand abzählen, nicht wahr? Augenzwinkern

Außerdem standen diese ersten drei Spalten schon oben bei PrototypeX29A:

Zitat:

Original von PrototypeX29A
Anzahl der 10 cm langen Baender. die am Ende blau sind = 1 (ein blaues Bandstueck)
Anzahl der 10 cm langen Baender, die am Ende rot sind = 0 (geht nicht)
Anzahl der 10 cm langen Baender, die am Ende gelb sind = 0 (geht nicht)

Anzahl der 20 cm langen Baender. die am Ende blau sind = 0 (geht nicht)
Anzahl der 20 cm langen Baender, die am Ende rot sind = 1 (ein rotes Bandstueck)
Anzahl der 20 cm langen Baender, die am Ende gelb sind = 0 (geht nicht)

Anzahl der 30 cm langen Baender. die am Ende blau sind = 1 (ein rotes und ein blaues Bandstueck)
Anzahl der 30 cm langen Baender, die am Ende rot sind = 1 (ein blaues und ein rotes Bandstueck)
Anzahl der 30 cm langen Baender, die am Ende gelb sind = 1 (ein gelbes Bandstueck)

Zitat:

Original von Kitkat
Bei n=12 sind es aber schon 120cm und nicht 130, oder? :-)

Richtig, mein Fehler - rechnen müsste man können. Hammer

04.07.2006, 20:17

Kitkat

Auf diesen Beitrag antworten »

Dankeschön, soweit jetzt verstanden. Ich weiß zwar immer noch nicht, was Rekursion ist und warum man die weiteren Werte so berechnet, aber ansonsten habe ich jetzt verstanden. Danke

Neue Frage »

Antworten »

Bänder

Verwandte Themen