| Autor |
Beitrag |
    
Johanna Goebel (Johanna)
| | Veröffentlicht am Montag, den 23. Oktober, 2000 - 03:32: | 
|
Al und Betty helfen Al's Familie einen Pfad mit Platten zu legen. Jede Platte ist exakt 2 feet breit. Jeder gelegte Stein ist rechtwinklig, mit der Dimension 1(lang) x 2(breit) feet. Um die Steine zu legen gibt es aber mehr als eine Moeglichkeit. Fuer 3 verschiedene Steine gibt es beispielsweise 3 Moeglichkeiten diese zu legen. Der Pfad auf den die Steine gelegt werden sollen ist 20 feet lang.
wieviele Moeglichkeiten gibt es um diesen 20 feet lagen pfad zu legen? Und gibt es eine generelle Formel um die moeglichkeiten herauszufinden?!?!?
Ueber eine schnelle Antort wuerde ich mich sehr freuen!
Mfg
Johanna G. |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Montag, den 23. Oktober, 2000 - 18:33: |
|
Hi Johanna
Bin ich jetzt begriffsstutzig, oder fehlt die angabe der breite des Pfades?
viele Gruesse
SpockGeiger |
Johanna Goebel (Johanna)
| | Veröffentlicht am Montag, den 23. Oktober, 2000 - 20:20: |
|
sorry hatte ich ganz vergessen der pfad soll 2 feet breit sein.. |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Dienstag, den 24. Oktober, 2000 - 01:02: |
|
Hi Johanna
Die Loesung des Problems sind die Fibonacci-Zahlen, allerdings um eins verschoben, sprich, wenn M(n) die Anzahl der Moeglichkeiten eines n Feet langen Pfades ist, dann ist M(1)=1, M(2)=2, und fuer n>2: M(n)=M(n-1)+M(n-2).
Spaetestens, wenn man bedenkt, wie lange ich daran rumgebruetet hab, sollte ich dass mal erklaeren:
Das Problem erscheint gar nicht mehr so schwer, wenn man es induktiv angeht, sprich wir haben einen Pfad von Laenge n vor uns, und uberlegen uns, wieviele Moeglichkeiten es gibt, vorausgesetzt, wir wissen alle Moeglichkeiten<n. Also: Wir koennen am Ende eine Stein quer legen, dafuer gibt es M(n-1) Moeglichkeiten. Die einzige andere Moeglichkeit, ist, oben zwei senkrechte Sreine hinzulegen, davon gibt es M(n-2) Moeglichkeiten, und siehe da, wir sind fertig, denn mehr Moeglichkeiten, ausser denen, die wir schon betrachtet haben, gibt es nicht.
Das heisst, wir koennen die Anzahl der Moeglichkeiten wie folgt beschreiben:
M(1)=1
M(2)=2
M(n)=M(n-1)+M(n-2)
Wie schon eingangs gesagt, ist das im Prinzip die Fibonacci-Folge, nur dass jene mit 0 und 1 anfaengt, also um eine Stelle verschoben ist.
Fuer die Fibonacci-Folge gibt es auch ne Formel:
Fib(n)=(an-bn)/w(5)
wobei w Quadratwurzel bedeutet, und
a=(1+w(5))/2
b=(1-w(5))/2
die Nullstellen des Polynoms x²-x-1 sind.
Also ist fuer uns die Formel (wegen der Verschiebung):
M(n)=Fib(n+1)=(an+1-bn+1)/w(5)
Fuer den speziellen Wert 20 ist unsere Loesung also: 10946
viele Gruesse
SpockGeiger |
Birk
| | Veröffentlicht am Dienstag, den 24. Oktober, 2000 - 02:01: |
|
Du kannsr also Platten längs oder quer zum Weg verlegen, wobei längs immer nur 2 Platten gleichzeitig in Frage kommen (wenn sie ganz bleiben sollen).Daraus ergibt sich also:
20 quer oder
2*1 längs + 18 quer oder
2*2 längs + 16 quer oder
2*3 längs + 14 quer oder
2*4 längs + 12 quer oder
2*5 längs + 10 quer oder
2*6 längs + 8 quer oder
2*7 längs + 6 quer oder
2*8 längs + 4 quer oder
2*9 längs + 2 quer oder
2*10 längs
in jedem Fall aber 20 Platten. Dabei können nun beliebig viele Platten quer nebeneinander an verschiedenen Positionen liegen. Z.B. bei nur 2 Platten quer ergeben sich allein schon 55 verschiedene Möglichkeiten. Das klingt nach Kombinatorik und zwar der Formel für Kombinationen (n!) / k!*(n-k)!
mit n Anzahl der möglichen Positionen
k Anzahl der querliegenden Platten
! Fakultät
und nun gehts los:
k=2 aus n=11 = 55
4 aus 12 = 495
6 aus 13 = 1716
8 aus 14 = 3003
10 aus 15 = 3003
12 aus 16 = 1820
14 aus 17 = 680
16 aus 18 = 153
18 aus 19 = 19
macht zusammen 10944 plus alle quer oder alle längs
sind 10946 verschiedene Möglichkeiten die Platten anzuordnen.
Ich hoffe, daß ich die Aufgabe richtig verstanden und mich nicht verrechnet habe.
Viel Spaß, Birk |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Dienstag, den 24. Oktober, 2000 - 09:18: |
|
Hallo zusammen
Ist doch klasse, die gleiche Loesung auf zwei verschiedenen Wegen.
viele Gruesse
SpockGeiger |
|
