100? in Scheinen auszahlen. Wieviel Möglichkeiten hat man.

15.05.2011, 20:11

wippi

100? in Scheinen auszahlen. Wieviel Möglichkeiten hat man.

Meine Frage:
100? in Scheinen auszahlen. Wieviel Möglichkeiten hat man.100? =1mal. 50?+50? =2mal. 50?+ 20?+20E+10? =3mal. usw

Meine Ideen:
1+2*5*10*10= 1001 ?

15.05.2011, 21:07

lgrizu

Auf diesen Beitrag antworten »

RE: 100? in Scheinen auszahlen. Wieviel Möglichkeiten hat man.
Du kommst auf 1001 Möglichkeiten?

Das kann man aber noch leicht durch aufschreiben der Möglichkeiten überprüfen, wie kommst du denn darauf, dass es zwei Möglichkeiten gibt, zwei 50 Euro Scheine auszuzahlen, das ist nur eine Möglichkeit, 50+50.

Ebenso ist 50+20+20+10 nur eine Möglichkeit und nicht drei.

15.05.2011, 21:07

HAL 9000

Auf diesen Beitrag antworten »

Ich komme nur auf 50 Varianten, allerdings in einem deutlich komplizierteren Abzählverfahren.

P.S.: Und bei allen fragwürdigen Ereignissen rund um die Europäische Währungsunion: Das Währungssymbol ist immer noch € statt des Fragezeichens. Augenzwinkern

15.05.2011, 21:53

Roman Oira-Oira

Auf diesen Beitrag antworten »

Bei mir sind es 146 Möglichkeiten:

100
50, 50

50, 20, 20, 10
...
50, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5

Also 12 Möglichkeiten mit einem 50ger und einem gewechselten 50ger (nachzählen!)

Die 12 Möglichkeiten mal der 12Möglichkeiten des nun auch gewechselten ersten 50gers = 144

144 + der 2 Möglichkeiten von ganz oben = 146

15.05.2011, 22:21

HAL 9000

Auf diesen Beitrag antworten »

Auf diese Art und Weise zählst du zig Varianten mehrfach, z.B.:

(20+20+10) + (20+10+10+5+5) = (20+20+5+5) + (20+10+10+10)

usw. unglücklich

15.05.2011, 22:26

Roman Oira-Oira

Auf diesen Beitrag antworten »

Ja, da scheinst Du wohl recht zu haben!

Da muß ich mir wohl ein anderes Verfahren ausdenken. Einfach nur nachzählen (über 12) will ich nicht ...

15.05.2011, 22:46

Fibbo

Auf diesen Beitrag antworten »

Wie lautet hier denn die genaue Aufgabenstellung?

Schließlich muss die Aufgabe ja einen bestimmten Hintergrund aus einem Fachbereich haben, der in der Schule behandelt wird?

15.05.2011, 23:01

Roman Oira-Oira

Auf diesen Beitrag antworten »

Zitat:

Original von Fibbo
Wie lautet hier denn die genaue Aufgabenstellung?

Schließlich muss die Aufgabe ja einen bestimmten Hintergrund aus einem Fachbereich haben, der in der Schule behandelt wird?

Die steht doch im ersten Beitrag!
Und die Fragestellung gehört wohl in die Kombinatorik.

Deine Frage wirkt ziemlich unmotiviert!

15.05.2011, 23:25

Roman Oira-Oira

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Auf diese Art und Weise zählst du zig Varianten mehrfach, z.B.:

(20+20+10) + (20+10+10+5+5) = (20+20+5+5) + (20+10+10+10)

usw. unglücklich

Da fällt mir auf: Bei meinem Verfahren, die 50ger zu wechseln, kommen nicht nur Varianten mehrfach vor, sondern es fehlt auch mindestens eine: 20, 20, 20, 20, 20 !

16.05.2011, 01:22

roltab

Auf diesen Beitrag antworten »

Eine Möglichkeit könnte sein sich zu überlegen wie viele Scheine man jeweils braucht und so von 1 Schein zu max. 20 Scheinen durchzuzählen wie viele verschiedene Möglichkeiten es dafür gibt. Also:
1 Schein : 100 -> 1 Möglichkeit
2 Scheine: 50-50 -> 1 Möglichkeit
3 : unmöglich -> 0
4: 50-20-20-10 -> 1
5: 50-20-10-10-10; 50-20-20-5-5; 20-20-20-20-20 -> 3
.......
19: unmöglich -> 0
20: 5-5-5-5-5-5-5-5-5-5-5-5-5-5-5-5-5-5-5-5 -> 1

Und die Summe bilden!

16.05.2011, 07:53

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Roman Oira-Oira
Einfach nur nachzählen (über 12) will ich nicht ...

Wollte ich auch nicht, deswegen habe ich MuPad zählen lassen, durch Vorgabe einer geeigneten Rekursionsformel. Augenzwinkern

16.05.2011, 20:44

Roman Oira-Oira

Auf diesen Beitrag antworten »

@roltab Dieses Verfahren ist zwar recht übersichtlich, trotzdem werden letztendlich alle 50 Möglichkeiten durchgezählt.

@HAL9000 Kannst Du uns deine Rekursionsformel verraten? Habe selbst auch nach einer Formel gesucht, kam aber leider nur auf ziemlich unübersichtliche Abfolgen.

16.05.2011, 20:48

HAL 9000

Auf diesen Beitrag antworten »

Die möglichen Werte der Scheine seien mit

$\begin{eqnarray*} w_1 = 5, \; w_2 = 10, \;w_3 = 20, \; w_4 = 50, \; w_5 = 100 \end{eqnarray*}$

bezeichnet, vielleicht auch noch (obwohl hier nicht benötigt) $\begin{eqnarray*} w_6 = 200, \; w_7 = 500 \end{eqnarray*}$ .

Außerdem bezeichne $\begin{eqnarray*} N(w,k) \end{eqnarray*}$ die Anzahl der Möglichkeiten, Wert $\begin{eqnarray*} w \end{eqnarray*}$ als Summe von Werten $\begin{eqnarray*} w_1,\ldots,w_k \end{eqnarray*}$ darzustellen .

Gesucht ist dann hier $\begin{eqnarray*} N(100,5) \end{eqnarray*}$ . Es ergibt sich für $\begin{eqnarray*} w>0 \end{eqnarray*}$ folgende Rekursionsformel

$\begin{eqnarray*} N(w,k) = \sum_{i=1}^k N(w-w_i,i) \qquad (*) \end{eqnarray*}$

mit den Startwerten $\begin{eqnarray*} N(0,k)=1 \end{eqnarray*}$ und $\begin{eqnarray*} N(w,k)=0 \end{eqnarray*}$ für $\begin{eqnarray*} w<0 \end{eqnarray*}$ .

Wenn man rechts in der Rekursion keine $\begin{eqnarray*} N(\cdot,k) \end{eqnarray*}$ mehr stehen haben will, kann man das noch zu

$\begin{eqnarray*} N(w,k) = \delta_{w \bmod w_k,0} + \sum_{j=0}^{\left\lceil \frac{w}{w_k} \right\rceil-1} ~ \sum_{i=1}^{k-1} N(w-jw_k-w_i,i) \qquad (**) \end{eqnarray*}$

entflechten. Sieht zwar komplizierter aus als (*), belastet aber nicht so sehr den Rekursionsstack von MuPad. Augenzwinkern

EDIT: Natürlich kann man diese Formel auch "von Hand" nutzen, es bietet sich dann aber an, basierend auf (**) schon mal ein paar Hilfsrechnungen wie etwa

$\begin{eqnarray*} N(5t,1) = 1 \end{eqnarray*}$
$\begin{eqnarray*} N(10t,2) = N(10t+5,2) = t+1 \end{eqnarray*}$
$\begin{eqnarray*} N(20t,3) = N(20t+5,3) = (t+1)^2 , \qquad N(20t+10,3) = N(20t+15,3) = (t+1)(t+2) \end{eqnarray*}$

für alle nichtnegativen ganzen Zahlen $\begin{eqnarray*} t \end{eqnarray*}$ vorzunehmen.

Neue Frage »

Antworten »

100? in Scheinen auszahlen. Wieviel Möglichkeiten hat man.

Verwandte Themen