Geldautomat

16.12.2006, 22:46

Kafka

Geldautomat

Hallo,

folgende Aufgabe: ein Geldautomat enthält 5, 10, 25 und 50 EUR Scheine. Auf wieviele Arten kann der Automat 500 EUR auszahlen? Ich weiß nicht wie ich hier anfangen soll.

Grüße

K.

16.12.2006, 23:13

Auf diesen Beitrag antworten »

Ganz sicher, dass es 25-Euro-Scheine und nicht 20-Euro-Scheine sind? Augenzwinkern

Wenn das die EZB erfährt...

17.12.2006, 12:10

Kafka

Auf diesen Beitrag antworten »

doch doch, es sollen schon 25-Euro-Scheine sein Augenzwinkern

17.12.2006, 12:20

Auf diesen Beitrag antworten »

Ok, dann kann man so anfangen: Seien

$\begin{eqnarray*} a \end{eqnarray*}$ ... Anzahl 5-Euro-Scheine
$\begin{eqnarray*} b \end{eqnarray*}$ ... Anzahl 10-Euro-Scheine
$\begin{eqnarray*} c \end{eqnarray*}$ ... Anzahl 25-Euro-Scheine
$\begin{eqnarray*} d \end{eqnarray*}$ ... Anzahl 50-Euro-Scheine

Dann muss $\begin{eqnarray*} 5a+10b+25c+50d = 500 \end{eqnarray*}$ , also

$\begin{eqnarray*} a+2b+5c+10d = 100\qquad (1) \end{eqnarray*}$

gelten. Nun ist die Anzahl $\begin{eqnarray*} N \end{eqnarray*}$ aller Tupel $\begin{eqnarray*} (a,b,c,d) \end{eqnarray*}$ nichtnegativer ganzer Zahlen gesucht, die (1) erfüllen.

Um das zu zählen, kann man vom größten Schein her anfangen: Möglich sind $\begin{eqnarray*} d=0,1,\ldots,10 \end{eqnarray*}$ es verbleibt dann eine Restsumme

$\begin{eqnarray*} a+2b+5c = 100-10d\qquad (2) \end{eqnarray*}$

Wegen $\begin{eqnarray*} a,b\geq 0 \end{eqnarray*}$ folgt daraus für gegebenes $\begin{eqnarray*} d \end{eqnarray*}$ ganz klar $\begin{eqnarray*} 5c\leq 100-10d \end{eqnarray*}$ oder umgeformt $\begin{eqnarray*} c\leq 20-2d \end{eqnarray*}$ , also $\begin{eqnarray*} c=0,1,\ldots,(20-2d) \end{eqnarray*}$ . Das ganze dann auch noch für $\begin{eqnarray*} b \end{eqnarray*}$ ...
$\begin{eqnarray*} a \end{eqnarray*}$ ist dann nach Festlegung von $\begin{eqnarray*} b,c,d \end{eqnarray*}$ automatisch über $\begin{eqnarray*} a = 100-10d-5c-2b \end{eqnarray*}$ bestimmt - wenn man bei den Bereichen für $\begin{eqnarray*} b,c,d \end{eqnarray*}$ keinen Fehler gemacht hat. Augenzwinkern

Und dann schön zusammmenzählen.

17.12.2006, 13:19

Kafka

Auf diesen Beitrag antworten »

hmm.. b wäre ja dann $\begin{eqnarray*} 2b \leq 100-10d-5c\ =>\ b \leq 50-5d-2.5c \end{eqnarray*}$
für d hab ich jetzt 11 Möglichkeiten. Für c auch 11? Für b 11*11? und a 11*11*11? verwirrt

hmmm...

17.12.2006, 13:21

Auf diesen Beitrag antworten »

Nein, so einfach ist es dann doch nicht. Ich schreib mal das, was ich bisher verbal ausgedrückt habe, in Gleichungsform: Sei $\begin{eqnarray*} |A| \end{eqnarray*}$ die Mächtigkeit einer Menge $\begin{eqnarray*} A \end{eqnarray*}$ , d.h., die Anzahl ihrer Elemente. Dann gilt

$\begin{eqnarray*} N &=& \left| \left\{ (a,b,c,d)\in\mathbb{N}_0^4 \bigm| a+2b+5c+10d = 100 \right\} \right|\\ &=& \sum_{d=0}^{10} \left| \left\{ (a,b,c)\in\mathbb{N}_0^3 \bigm| a+2b+5c = 100-10d \right\} \right|\\ &=& \sum_{d=0}^{10} \sum_{c=0}^{20-2d} \left| \left\{ (a,b)\in\mathbb{N}_0^2 \bigm| a+2b = 100-10d-5c \right\} \right| = \cdots \end{eqnarray*}$

17.12.2006, 14:01

Kafka

Auf diesen Beitrag antworten »

wie kann man es dann von innen nach außen aufsummieren? da blicke ich noch nicht ganz durch...

17.12.2006, 14:20

Auf diesen Beitrag antworten »

Ok, der letzte konsequente Schritt in dieser obigen Gleichungskette wäre

$\begin{eqnarray*} N = \sum_{d=0}^{10} \sum_{c=0}^{20-2d} \sum_{b=0}^{\left\lfloor 50-5d-\frac{5}{2}c \right\rfloor} ~ \left| \left\{ a\in\mathbb{N}_0 \bigm| a = 100-10d-5c-2b \right\} \right| \end{eqnarray*}$

Die Mächtigkeit dieser letzten Menge ist natürlich 1, es bleibt ja nur die eine Möglichkeit $\begin{eqnarray*} a = 100-10d-5c-2b \end{eqnarray*}$ , wenn $\begin{eqnarray*} b,c,d \end{eqnarray*}$ schon vorher festgelegt sind. So, jetzt das ganze von innen nach außen aufrollen:

$\begin{eqnarray*} N = \sum_{d=0}^{10} \sum_{c=0}^{20-2d} ~ \left\lfloor 51-5d-\frac{5}{2}c \right\rfloor \end{eqnarray*}$

Tja, die Gaußklammer stört, ganz eindeutig. Aber die kriegt man weg, indem man sich überlegt, dass

$\begin{eqnarray*} \left\lfloor 51-5d-\frac{5}{2}c \right\rfloor = \begin{cases} 51-5d-\frac{5}{2}c & \;\mbox{für gerade}\; c\\ 51-5d-\frac{5}{2}c-\frac{1}{2} & \;\mbox{für ungerade}\; c \end{cases} \end{eqnarray*}$

gilt. Dann muss man also für $\begin{eqnarray*} c=1,3,5,\ldots,19-2d \end{eqnarray*}$ jeweils $\begin{eqnarray*} \frac{1}{2} \end{eqnarray*}$ abziehen, das sind genau $\begin{eqnarray*} (10-d) \end{eqnarray*}$ ungerade Zahlen $\begin{eqnarray*} c \end{eqnarray*}$ . Also gilt

$\begin{eqnarray*} N &=& \sum_{d=0}^{10} \left[ \left( \sum_{c=0}^{20-2d} 51-5d-\frac{5}{2}c \right) - \frac{10-d}{2}\right] \end{eqnarray*}$

und jetzt bist du erstmal wieder an der Reihe.

17.12.2006, 17:12

Kafka

Auf diesen Beitrag antworten »

hmm wenn ich es jetzt zerlege bekomme ich:
$\begin{eqnarray*} N = 50 - 5\sum_{d=0}^{10}d - 2.5\sum_{d=0}^{10}\sum_{c=0}^{20-2d}c +5\sum_{d=0}^{10}d \end{eqnarray*}$
es bleibt also nur:
$\begin{eqnarray*} N = 50 - 2.5\sum_{d=0}^{10}\sum_{c=0}^{20-2d}c = 50 - 2.5*825 \end{eqnarray*}$
was natürlich falsch ist traurig

17.12.2006, 17:15

Auf diesen Beitrag antworten »

Lass doch erstmal das $\begin{eqnarray*} d \end{eqnarray*}$ in Ruhe und summiere über $\begin{eqnarray*} c \end{eqnarray*}$ .

Deine Rechnung ist in keinster Weise nachvollziehbar: Wenn du eine Konstante über c summierst, heißt das nicht, dass du die c-Summe weglassen kannst! Sondern:

$\begin{eqnarray*} \sum_{c=0}^{20-2d} A = (21-2d)\cdot A \end{eqnarray*}$

17.12.2006, 18:05

Kafka

Auf diesen Beitrag antworten »

ok ich sehe schon die Fehler. ich lasse es erstmal sein, irgendwie komme ich alleine nicht wirklich weiter. Hammer

vielen Dank für die Hilfe smile

17.12.2006, 18:10

Auf diesen Beitrag antworten »

Komisch, dass du jetzt aufgibst. Dabei brauchst du nur die drei Summenformeln

$\begin{eqnarray*} \sum_{k=0}^n ~ 1 = n+1,\qquad \sum_{k=0}^n ~ k = \frac{n(n+1)}{2},\qquad \sum_{k=0}^n ~ k^2 = \frac{n(n+1)(2n+1)}{6} \end{eqnarray*}$

um jetzt zum Ziel zu gelangen. Aber ist ja deine Sache... Wink

17.12.2006, 20:06

Kafka

Auf diesen Beitrag antworten »

noch ein versuch:
$\begin{eqnarray*} N = \sum_{d=0}^{10}[\sum_{c=0}^{20-2d}(50-5d-2.5c)-\frac{10-d}{2}] \\= \sum_{d=0}^{10}[\sum_{c=0}^{20-2d}50 -5\sum_{c=0}^{20-2d}d -2.5\sum_{c=0}^{20-2d}c -5+\frac{d}{2})]\\ = \sum_{d=0}^{10}[1000-100d-100d+10d^2-2.5\sum_{c=0}^{20-2d}c-5+\frac{d}{2}]\\= \sum_{d=0}^{10}1000-200\sum_{d=0}^{10}d+10\sum_{d=0}^{10}d^2 -2.5\sum_{d=0}^{10}\sum_{c=0}^{20-2d}c -\sum_{d=0}^{10}5 +0.5\sum_{d=0}^{10}d\\= 10000-11000+3850-2.5\sum_{d=0}^{10}\sum_{c=0}^{20-2d}c-50+27.5\\= 2827.5 - 2062.5 = 760 \end{eqnarray*}$
das sieht schon viel besser aus aber irgendwo muss noch ein Fehler sein weil es sollte eine eine 4-stellige natürliche Zahl mit der Quersumme 10 rauskommen... noch ein Tipp? Augenzwinkern

Grüße

K.

17.12.2006, 20:12

Auf diesen Beitrag antworten »

Zitat:

Original von Kafka
weil es sollte eine eine 4-stellige natürliche Zahl mit der Quersumme 10 rauskommen..

Das bezweifle ich - raus kommt 2156, das will ich schon mal verraten.

Ok, ausführlich die nächsten Schritte:

$\begin{eqnarray*} \sum_{c=0}^{20-2d} 51-5d-\frac{5}{2}c = \sum_{c=0}^{20-2d} (51-5d) ~ - ~ \frac{5}{2} \sum_{c=0}^{20-2d} c = (21-2d)(51-5d) ~ - ~ \frac{5}{4} (20-2d)(21-2d) \end{eqnarray*}$

Dann noch das $\begin{eqnarray*} -\frac{10-d}{2} \end{eqnarray*}$ dranhängen, alles ausmultiplizieren und erstmal vereinfachen, da muss summa summarum $\begin{eqnarray*} 5d^2-104d+541 \end{eqnarray*}$ herauskommen. Das dann über $\begin{eqnarray*} d=0\ldots 10 \end{eqnarray*}$ summieren!

17.12.2006, 20:16

Kafka

Auf diesen Beitrag antworten »

ich sehe schon ich habe statt 51 mit 50 gerechnet. jetzt muss es stimmen. vielen Dank! smile

18.12.2006, 12:03

Kafka

Auf diesen Beitrag antworten »

jetzt muss ich doch noch mal nachhacken weil ich immer noch nicht auf das gleiche komme Augenzwinkern

wo kommen im letzten schritt die 5/4 her? für c haben Sie 20-2d eingesetzt, richtig?

18.12.2006, 14:17

Auf diesen Beitrag antworten »

Nicht "haben Sie" sondern "hast du" ! Augenzwinkern

Das ist die Summenformel

$\begin{eqnarray*} \sum_{k=0}^n ~ k = \frac{n(n+1)}{2} \end{eqnarray*}$

nur mit Index $\begin{eqnarray*} c \end{eqnarray*}$ statt $\begin{eqnarray*} k \end{eqnarray*}$ , und $\begin{eqnarray*} n=20-2d \end{eqnarray*}$ . Da davor noch der Faktor $\begin{eqnarray*} \frac{5}{2} \end{eqnarray*}$ war, wird daraus

$\begin{eqnarray*} \frac{5}{2} \cdot \frac{n(n+1)}{2} = \frac{5}{4} n(n+1) = \frac{5}{4} (20-2d)(21-2d) \end{eqnarray*}$

20.12.2006, 19:35

Kafka

Auf diesen Beitrag antworten »

stimmt. die aufgabe ist endlich gelöst Augenzwinkern

danke.

20.12.2006, 19:40

Auf diesen Beitrag antworten »

Ich hätte auch lieber eine einfachere Lösung gehabt, aber mir fällt nicht ein, wie man den Aufwand wesentlich reduzieren könnte.

Neue Frage »

Antworten »

Geldautomat

Verwandte Themen