Münze aufteilen

27.06.2014, 17:04

C3po-wasauchimmer

Münze aufteilen

Meine Frage:
Wieviele Möglichkeiten gibt es 1 Euro in 1, 2 und 5 Cent Stücke aufzuteilen?

Meine Ideen:
Für ein 5 Cent Stück gibt es 4 Möglichkeiten:
5
221
2111
11111

Für ein 10 Cent Stück dann $\begin{eqnarray*} 4^{2}+1=17 \end{eqnarray*}$
+1, da eine Möglichkeit, und zwar 22222 dazukommt.

10 mal 10 Cent Stück ergibt:

$\begin{eqnarray*} 17^{10}=2,0159939\cdot 10^{12} \end{eqnarray*}$ (2 Billionen !?!)

Ist das so richtig? Kommt mir sehr hoch vor. Oder einfach weil der Mensch nicht exponentiell denken kann?

Danke für eure Hilfe!!!

27.06.2014, 21:34

HAL 9000

Auf diesen Beitrag antworten »

Tatsächlich sind es nur 541 Möglichkeiten.

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

Mit deiner Zählweise zählst du viel zu viel mehrfach, das geht schon bei deinen 10 Cent los, da gibt es nur 10 Möglichkeiten, wo du 17 angibst:

Z.B. sind bei deiner Zählweise

2111 + 2111

und

221 + 11111

verschiedene Variante, dabei repräsentieren beide nur 22111111. unglücklich

27.06.2014, 21:41

C3po-wasauchimmer

Auf diesen Beitrag antworten »

Ok,

...und wie kommt man auf die 541 Möglichkeiten? Kannst du mir einen Tipp geben?

27.06.2014, 21:49

HAL 9000

Auf diesen Beitrag antworten »

Kleine Ziele setzen.

Bezeichnen wir mit $\begin{eqnarray*} f(n) \end{eqnarray*}$ die Anzahl der Möglichkeiten, $\begin{eqnarray*} n \end{eqnarray*}$ Cent mit 1- und 2-Cent-Stücken zusammenzustellen. Dann ist (mit Gaußklammer geschrieben):

$\begin{eqnarray*} f(n) = \left\lfloor \frac{n}{2} \right\rfloor+1 \end{eqnarray*}$ ,

überleg dir, warum.

Nächster Schritt: Sei $\begin{eqnarray*} g(n) \end{eqnarray*}$ die Anzahl der Möglichkeiten, $\begin{eqnarray*} n \end{eqnarray*}$ Cent mit 1-, 2- und 5-Cent-Stücken zusammenzustellen, wir suchen also hier $\begin{eqnarray*} g(100) \end{eqnarray*}$ . Dann ist

$\begin{eqnarray*} g(n) = \sum_{k=0}^{\left\lfloor \frac{n}{5} \right\rfloor} f(n-5k)\qquad (*) \end{eqnarray*}$ ,

dabei repräsentiert Index $\begin{eqnarray*} k \end{eqnarray*}$ die Anzahl der 5-Cent-Stücke in der Zusammenstellung. Man muss Rekursion (*) inhaltlich begreifen, dann kann man auch mit ihr rechnen.

EDIT: Um die Systematik besser zu erkennen, hätte ich vielleicht zunächst $\begin{eqnarray*} f(n) = \sum_{k=0}^{\left\lfloor \frac{n}{2} \right\rfloor} 1 \end{eqnarray*}$ schreiben sollen. Augenzwinkern

27.06.2014, 22:08

C3po-wasauchimmer

Auf diesen Beitrag antworten »

Ich verstehe f(n) schon nicht. Fas ist ja dann gleich der anzahl an 2 cent stücken die ich maximal verwenden kann +1. Verstehe ich nicht ?

27.06.2014, 22:28

C3po-wasauchimmer

Auf diesen Beitrag antworten »

Also die rekursion verstehe ich!
Zu f(n):
Ich schaue mir also die maximale anzahl an 2cent stücken an die ich in n packen kann. Für diese 2 cent gibt es dann 2 möglichkeiten 11 oder 2 ...woher kommt aber jetzt die 1?

27.06.2014, 22:29

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von C3po-wasauchimmer
Ich verstehe f(n) schon nicht. Fas ist ja dann gleich der anzahl an 2 cent stücken die ich maximal verwenden kann +1.

Genau: Du kannst nämlich 0,1,... bis zur Maximalzahl $\begin{eqnarray*} \left\lfloor \frac{n}{2} \right\rfloor \end{eqnarray*}$ an 2-Cent-Stücken in der Auswahl haben - der Rest sind dann automatisch 1-Cent-Stücke. Und damit ist die Anzahl doch schon klar!

Beispiel: n=4 mit 0..2 2-Centstücken, ergibt f(4)=3

1111
211
22

Oder n=7 mit 0..3 2-Centstücken, ergibt f(7)=4

1111111
211111
22111
2221

27.06.2014, 22:36

C3po-wasauchimmer

Auf diesen Beitrag antworten »

Ok, ich glaube jetzt hab ichs...also die +1 kommt also von der möglichkeit die keine 2 enthält. Richtig?

27.06.2014, 22:37

HAL 9000

Auf diesen Beitrag antworten »

Ja klar: Wenn man bei 0 beginnt zu zählen statt bei 1, dann muss man das berücksichtigen. Augenzwinkern

EDIT: Anscheinend hat C3po das Interesse verloren - ich beende trotzdem mal die Rechnung. Basierend auf (*) folgt für $\begin{eqnarray*} n=10m \end{eqnarray*}$ sowie Umindizierung $\begin{eqnarray*} k=2m-j \end{eqnarray*}$ sowie nachfolgend Auftrennung in $\begin{eqnarray*} j=2i \end{eqnarray*}$ und $\begin{eqnarray*} j=2i+1 \end{eqnarray*}$

$\begin{eqnarray*} g(10m) = \sum_{k=0}^{2m} f(10m-5k) = \sum_{j=0}^{2m} f(5j) = \sum_{i=0}^{m} f(10i) + \sum_{i=0}^{m-1} f(10i+5) \end{eqnarray*}$

Mit $\begin{eqnarray*} f(10i) = 5i+1 \end{eqnarray*}$ sowie $\begin{eqnarray*} f(10i+5)=5i+3 \end{eqnarray*}$ sowie Einsatz des "Kleinen Gauß" bekommen wir damit

$\begin{eqnarray*} g(10m) = \sum_{i=0}^{m} (5i+1) + \sum_{i=0}^{m-1} (5i+3) = \frac{5}{2}m(m+1) + (m+1) + \frac{5}{2}(m-1)m + 3m = 5m^2+4m+1 \end{eqnarray*}$ ,

was für $\begin{eqnarray*} m=10 \end{eqnarray*}$ im Fall hier dann $\begin{eqnarray*} g(100)=541 \end{eqnarray*}$ bedeutet.

Neue Frage »

Antworten »

Münze aufteilen

Verwandte Themen