Kombination von Geldscheinen < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 18:19 So 02.05.2004 | | Autor: | Rauchwolke |
Hallo zusammen,
ich komme mit einer Aufgabe leider nicht voran:
Wie oft kann man 250,- wechseln (in Scheinen)?
Sicher gibt es dafür eine Formel, aber alle Möglichkeiten, die mir eingefallen sind, waren falsch.
Das Ergebnis soll 571 sein.
Danke schon mal für Eure Antworten... Eure Rauchwolke 
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:23 So 02.05.2004 | | Autor: | Oliver |
Hallo Rauchwolke,
ob es dafür wirklich eine Formel gibt, bezweifle ich stark. Rein methodisch würde ich wie folgt vorgehen: ich schaue mir alle 50 mit Scheinen möglichen Beträge von 5 EUR bis 250 EUR an und schaue, wieviele mögliche Kombinationen es gibt, auf diese zu kommen. Dabei fange ich bei 5 EUR an und arbeite mich hoch. Das hat den Vorteil, das ich bereits gewonnene Erkenntnisse einfließen lassen kann und ich quasi nur "eine Stufe niedriger" gehen muss - da ich es nicht besser erklären kann, hier am Beispiel:
01. 5 EUR: 1 Möglichkeit (1 x 5-EUR)
02. 10 EUR: Entweder ich nehme als erstes einen 10 EUR Schein oder einen 5 EUR-Schein. Im ersten Fall bin ich fertig (1 Möglichkeit), im zweiten habe ich noch einen Restbetrag von 5 EUR und bin im Fall 01 (1 Möglichkeit) -> Insgesamt 2 Möglichkeiten.
03. 15 EUR: Entweder ich nehme als erstes einen 10 EUR Schein oder einen 5 EUR-Schein. Im ersten Fall habe ich einen Restbetrag von 5 EUR und bin im Fall 01 (1 Möglichkeit). Im zweiten Fall bin ich im Fall 02 (2 Möglichkeiten) -> Insgesamt 3 Möglichkeiten.
04. 20 EUR: Entweder ich nehme als erstes einen 20 EUR Schein (fertig, eine Möglichkeit), einen 10 EUR Schein (Restbetrag 10 EUR, 2 Möglichkeiten) oder einen 5 EUR-Schein (Restbetrag 15 EUR, 3 Möglichkeiten) -> Insgesamt 6 Möglichkeiten.
05. 25 EUR: Entweder ich nehme als erstes einen 20 EUR Schein (Rest 5 EUR, eine Möglichkeit), einen 10 EUR Schein (Restbetrag 15 EUR, 3 Möglichkeiten) oder einen 5 EUR-Schein (Restbetrag 15 EUR, 6 Möglichkeiten) -> Insgesamt 10 Möglichkeiten.
06. 30 EUR: Entweder ich nehme als erstes einen 20 EUR Schein (Rest 10 EUR, zwei Möglichkeiten), einen 10 EUR Schein (Restbetrag 20 EUR, 6 Möglichkeiten) oder einen 5 EUR-Schein (Restbetrag 25 EUR, 10 Möglichkeiten) -> Insgesamt 18 Möglichkeiten.
Wenn man das ganze rekursiv definiert, kommt man auf folgendes (inspiriert durch ![[]](/images/popup.gif) http://www.research.att.com/projects/OEIS?Anum=A060945):
a(n)=0 für n<0
a(0)=1
a(1)=1
a(n)=a(n-1)+a(n-2)+a(n-4)+a(n-10)+a(n-20)+a(n-40)+a(n-100) für n>1
Da die mit Scheinen möglichen Beträge allesamt durch 5 teilbar sind, habe ich das Ganze normiert, so daß a(n) der Anzahl der Wechsel-Möglichkeiten für 5n EUR entspricht.
Damit hätten wir eine schöne Darstellung der Möglichkeiten mit Beachtung der Reihenfolge. Leider habe ich keinerlei Idee, wie wir von hier die gesuchte Anzahl der Möglichkeiten ohne Beachtung der Reihenfolge erhalten können ....
Mach's gut
Oliver
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:22 Mo 03.05.2004 | | Autor: | Paulus |
Hallo Rauchwolke,
wie dir Oliver bereits erklärt hat, gibt es wohl kaum eine einfache Formel für dein Problem.
Ich bin das Ganze mal von einer anderen Betrachtungsweise angegangen:
Mit der Varianlen [mm]a, b, c, d, e[/mm] und [mm]f[/mm] für die Geldscheine 5 , 10 , 20 , 50 , 100 und 200 respektive habe ich mal die folgende Formel aufgestellt:
[mm]5a+10b+20c+50d+100e+200f = 250[/mm] oder mit 5 gekürzt:
[mm]a+2b+4c+10d+20e+40f = 50[/mm]
Dieser Gleichung entspricht im 6-dimensionalen Vektorraum eine 5-dimensionale Hyperebene mit folgender Parameterdarstellung:
[mm]\begin{pmatrix} 50 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} + b \begin{pmatrix} -2 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}+c \begin{pmatrix} -4 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}+d \begin{pmatrix} -10 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}+e \begin{pmatrix} -20 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \end{pmatrix}+f \begin{pmatrix} -40 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}[/mm]
Die erste Koordinate gibt dabei die Anzahl 5er-Scheine, die zweite die Anzahl 10er-Scheine usw. an.
Die Parameter [mm]b[/mm] bis [mm]f[/mm] dürfen dabei für die Darstellung der Ebene beliebig gewählt werden. Für unsere Anwendung gibt es aber Einschränkungen für die Parameter:
1) sie dürfen nur natürliche Zahlen inklusive [mm]0[/mm] sein
2) Zusammen darf der Bertag von 250 nicht überschritten werden, was sich in unserer Formel so niederschlägt:
[mm]0 \leq b+2c+5d+10e+20f \leq 25[/mm]
Ich habe mit einem kleinen Programm die möglichen Werte für die Parameter zusammengestellt. Vielleicht hilft dir das Ergebnis, die Angahl Möglichkeiten auf raffinierte Art (Summenformeln) zu zählen.
![[a]](/images/paperclip.gif "Dateianhänge") "Euro.txt"
Das mit dem Hochladen scheint noch nicht so zu gelingen, ich versuchs nachher nochmals...
Dateianhänge:
Anhang Nr. 1 (Typ: txt) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:31 Mo 03.05.2004 | | Autor: | Stefan |
Hallo,
für eine ausführliche Antwort fehlen mir Zeit und Motivation, aber ich habe mir (bereits gestern) eine recht elementare Lösung überlegt, die man auch in einer (allerdings fiesen, mit vier ineinander verschachtelten Summenzeichen versehenen) geschlossenen Form angeben kann. Im Wesentlichen beruht sie darauf, dass man die 5-er-Scheine natürlich vergessen kann (die ergeben sich als Reste ja automatisch) und sich bei gegebenen "hohen" Scheinen überlegt, wie man diese durch 20-Euro-Scheine ersetzen kann. (Die anschließende Ersetzung durch 10-Euro-Scheine ist dann trivial.) Dabei kommt man dann auf Summen wie
[mm]\sum_{i=1}^{\frac{50j}{20}+1} (2i-1)[/mm]
bzw.
[mm]\sum_{i=1}^{[\frac{50j}{20}]+1} 2i[/mm]
(abhängig von [mm]j[/mm], d.h. ob [mm]j[/mm] gerade oder ungerade ist), wobei [mm][x][/mm] die Gaußklammer ist.
Naja, auf diese Weise erhält man dann mit wenig Aufwand
[mm](1+12+36+72+121+182) + (1+12+36+72) + (1+12) + (1+12) = 571[/mm]
Möglichkeiten, wie angegeben.
Vielleicht hat ja jemand Lust die fehlenden Schritte zu ergänzen. Ist nicht schwierig (okay, für einen Schüler schon), aber viel zu schreiben.
Viele Grüße
Stefan
|
|
|
|
