Fibonacci Post Stamps Arrangement

Question

Aufgabe:

You have a large number of 10-p and 20-p stamps. In how many ways can you arrange these stamps on an envelope for a total of 10p, 20p, 30p, 40p, 50p, 60p?

Example: For 40p there are 5 ways to arrange the stamps.

10-10-10-10, 10-10-20, 10-20-10, 20-10-10, 20-20

b) Explain in words why exactly these numbers of arrangements appear in this problem.

Problem/Ansatz:

Mein Problem ist dabei, dass ich denke, dass es mit der Fibonacci Sequenz zu tun hat, sprich, es wird immer mehr um 1, 1, 2, 3, 5. Doch Beweise dafür zu haben fällt mir schwer und ob es stimmmt, weiss ich nicht.

Vielen Dank!

Answer 1

Hallo,

so eine Folge von Briefmarken besteht nur aus 10p--Marken - ich nenne die mal $1$ - oder aus 20p-Marken - das sei die $2$. Sind mir alle Folgen von der vorletzen (der $n-2$'ten) und der letzten (der $n-1$'ten) bekannt. So kann man alle $n$'te Folgen legen, indem man allen $n-1$'ten Folgen eine $1$ vorne an stellt und allen $n-2$'ten Folgen eine $2$. $$\begin{array}{llllll} 1: \space & 1\\ 2: &11 \quad & 2\\ 3: & \colorbox{#ffff00}{1}11 & \colorbox{#ffff00}{1}2 \quad & \colorbox{#88ff88}{2}1 \\ 4: & \colorbox{#ffff00}{1}111 & \colorbox{#ffff00}{1}12 & \colorbox{#ffff00}{1}21 \quad &\colorbox{#88ff88}{2}11 &\colorbox{#88ff88}{2}2 \\ 5: & \text{usw.}\end{array}$$jetzt muss man noch zeigen , dass die neue Menge der Folgen den richtigen Wert anzeigt, eindeutig und vollständig ist.

Der richtige Wert ist gegeben, da jede Folge des vorletzten Werts um 2 und jede des letzten um 1 erhöht wurde.

EIndeutig ist sie sicher, da sich hinter jeder 1 und jeder 2 jeweils eine Folge befindet, die zu allen anderen einddeutig ist.

Die Vollständigkeit ist auch gegeben. Jede Folge kann nur mit einer 1 oder einer 2 beginnen. Hinter dieser ersten Marke müssen jetzt alle Teilfolgen kommen, die zusammen den $n-1$ bzw. $n-2$'ten Wert ergeben. Und das ist ja garantiert, da die Vorgängerfolgen auch vollständig waren.

Somit setzt sich jede Anzahl $A_n$ aller Möglichketen, die Marken in einer Reihe zu plazieren, aus der Summe der beiden Vorgängeranzahlen zusammen $$A_n = A_{n-1} + A_{n-2}$$Gruß Werner

Answer 2

Nimm an,

du hast alle Möglichkeiten für die Preise 10*n und 10*(n+1).

Welche Möglichkeiten gibt es jetzt, dass Porto mit dem Preis 10*(n+2) aufzukleben?

Nun, du kannst entweder zu einem bereits aufgeklebten Porto 10*n noch eine 20-er-Marke dazukleben, oder du kannst einen schon aufgeklebten Preis 10*(n+1) mit einer weiteren 10-er-Marke ergänzen.

Somit ergibt sich die Anzahl als Summe der Anzahlen der beiden vorherigen Portobeträge.