Problem des Monats November 2013: Marco bezahlt mit den neun Münzen.

Question

Marco muss beim Einkauf 3,38 € bezahlen. Er bezahlt dies passend mit den abgebildeten neun Münzen. Petra erkennt, dass dafür auch sieben Münzen genügen würden.

a) Welches ist der kleinste Betrag, für den man mindestens sieben Münzen benötigt, wenn man passend bezahlen möchte und alle Münzen mehrfach zur Verfügung hat?

Anschließend stellen beide fest, dass man zum Bezahlen von allen Geldbeträgen unter 5 € höchstens acht Münzen benötigt.

b) Bei welchen dieser Beträge braucht man genau acht Münzen?

Comments

Warum schreibt ihr hier nicht ehrlich rein, dass diese Aufgabe das sog. Problem des Monats in Bawü ist? Das sollen die Kinder als Wettbewerb lösen und nicht die Lösung im Netz suchen, weil jemand die Aufgabe hier reinkopiert hat...

Also das nächste Mal bitte ehrlich sein und wenn schon, dann die Lösung erst nach Ablauf des jeweiligen Aufgaben-Monats reinstellen.

Gruß, MP

Answer 1

Wert	2€	1€	0.5€	0.2€	0.1€	0.05€	0.02€	0.01€
3.38	1	1		1	1	1	1	1
1.88		1	1	1	1	1	1	1

 

Nun solltest du mal Probieren welche Beträge man mit nur mit wenigstens 8 Münzen legen kann.

Comments

wert	2€	1€	0,5€	0,2€	0,1€	0,05€	0,02€	0,01€
3,88	1	1	1	1	1	1	1	1

Bei Frage A) dachte ich darf man nur die abgebildeten Münzen verwenden, da man ja die Münzen mehrfach zur Verfügung hat oder nicht?

---

Schon in der Beschreibung steht:

Petra erkennt, dass dafür auch sieben Münzen genügen würden.

Das ist ja z.B. auch nur Möglich, wenn man ein 20 Cent Stück hat. Also gehe ich davon aus, dass man alle Münzen mehrfach hat. Also auch die nicht abgebildeten. Die Abbildung ist ja nur ein Beispiel für 3.38€.

Answer 2

Geht bei a nicht auch 0,07 ct, also 7 Münzen mal 0,01 ct, da man diese mehrfach nehmen kann. Dann wäre der kleinste Betrag 0,07 ct.???

Comments

ja, ich dachte auch, dass bei a) die lösung 0,07 € ist. stimmt das nicht?

---

Ja oder 7,76 ich weiss nicht was stimmt. Bei b bin ich mir auch nicht sicher.

---

wie kommst du auf 7,76?

---

3,88 x 2 jede Münze doppelt

---

Warum denn das?

---

keine Ahnung.

Was hättet Ihr als Vorschlag für a bzw. b ?

Könnte es stimmen, dass a 3,38

bzw. b 3,88 ist?

gibt es für b noch weitere Lösungen?

Was meint Ihr, was stimmt?

---

1,88€ ist die Lösung für a. Es ist ja der kleinste Betrag bei dem man mindestens 7 Münzen benötigt gefragt. bei0,07€ könnte man ja auch ein 5cent und ein 2cent Stück nehmen.......

---

Ja aber wenn ich passend bezahlen möchte, brauche ich dann nicht 3,38? Was wäre bei b das Ergebnis ausser 3,88?

---

Der kleinste Betrag bei dem man mindestens 7 Münzen braucht wenn man passend bezahlen möchte ist 1,88€, der setzt sich zusammen aus 1x1cent; 1x2cent; 1x5cent; 1x10cent; 1x20cent; 1x50cent und 1x1€. Kleiner geht nicht bei mindestens 7 Münzen. Zu b muss ich noch überlegen.........

---

zu b sind es 3,88€(1x2€; 1x1€; 1x50cent; 1x20cent; 1x10cent; 1x5cent; 1x2cent: 1x1cent) und 4,88€(2x2€;1x50cent; 1x20cent; 1x10cent; 1x5cent; 1x2cent; 1x1cent) Grüße

---

Ich kann aber mit 8 Münzen zig Beträge unter 5 Euro legen z.b. 8 mal 1 Cent, 7 mal 1 Cent 1mal 2 Cent USW.

---

Ja ab 8cent um genau zu sein geht jeder Betrag mit 8 Münzen. Aber diese Beträge kann man auch alle mit weniger Münzen bezahlen, aber 3,88 und 4,88 nicht.

---

Aber ich habe doch jede Münze mehrfach zur Verfügung ,also wäre doch  7 mal 1Cent zu Frage a) richtig

---

7cent geht nicht weil ich dafür auch 1x2cent und 1x5cent nehmen könnte.

---

7cent geht nicht weil ich dafür auch 1x2cent und 1x5cent nehmen könnte. Der Knackpunkt ist doch das es mindestens 7 Münzen sein sollen und desshalb der Betrag mit weniger nicht gehen soll.

Answer 3

Bei a) hängt alles an der Bezeichnung "benötigt".

Umsetzung ohne "benötigt"  in ein lineares Problem:

 

Minimiere den Betrag B (in Euro)

B = 0,01a₁+ 0,02a₂+0,05a₃+0,10a₄+0,20a₅+0,50a₆+1,00a₇+2,00a₈

Unter den Nebenbedingungen (NB):

1.  ∑ a_i ≥ 7  [ für i=1 ...8 ]                                                ...entspricht "mindestens 7 Münzen"

2.  a_i ∈ { 0 , 1 , 2 , ... }  bzw.  a_i ∈ ℕ₀   für i = 1, ... 8     ...entspricht "alle Münzen mehrfach vorhanden"

Hier ist die Lösung:  a₁ = 7,  restliche a_i = 0, für i = 2,...,8    Betrag B = 0,07 Euro

 

Eigentlich kann die NB 1. das "≥" auch durch "=" ersetzt werden, dies verändert die Lösung nicht.

 

Will man die Beschreibung "benötigt" umsetzen, wird es anspruchsvoller,

da einige mehrfach benutzte Münzen durch höherwertige Münzen in geringerer Zahl ersetzt werden können.

Es müssen weitere NB 3. bis 11. aufgenommen werden,

die NB2. wird dadurch verschärft, sie ist ebenfalls erfüllt, wenn die NB3. bis NB11. erfüllt sind

Neue, zusätzliche NB:

3. "2 und mehr 1-Cent Münzen werden umgewandelt..."

     a₁ ≤ 1   d.h.   a₁ ∈ {0;1}

4. "3 und mehr 2-Cent Münzen werden umgewandelt..."

     a₂ ≤ 2   d.h.   a₂ ∈ {0;1;2}

5. "2 und mehr 5-Cent Münzen werden umgewandelt..."

     a₃ ≤ 1   d.h.   a₃ ∈ {0;1}

6. "2 und mehr 10-Cent Münzen werden umgewandelt..."

     a₄ ≤ 1   d.h.   a₄ ∈ {0;1}

7. "3 und mehr 20-Cent Münzen werden umgewandelt..."

     a₅ ≤ 2   d.h.   a₅ ∈ {0;1;2}

8. "2 und mehr 50-Cent Münzen werden umgewandelt..."

     a₆ ≤ 1   d.h.   a₆ ∈ {0;1}

9. "2 und mehr 1-Euro Münzen werden umgewandelt..."

     a₇ ≤ 1   d.h.   a₇ ∈ {0;1}

10. "2 Euro Münzen werden nicht mehr umgewandelt, aber können maximal 7 Münzen verwendet werden"

     a₈ ≤ 7   d.h.   a₈ ∈ {0;1;2;3;4;5;6;7}

11. "Umrechnung in 5-Cent aus 1-Cent und 2-Cent Münzen...

     a₁ + a₂ ≤ 2

12. "Umrechnung in 50-Cent aus 10-Cent und 20-Cent Münzen..."

     a₄ + a₅ ≤ 2

 

Um den Gesamtbetrag zu minimieren geht man von den kleinsten Münzwerten an aufwärts,

d.h. die a_i von 1 nach 8 durch, und versucht bei den kleinsten a_i die maximal

zulässige Anzahl an Münzen so zuzuordnen, dass die Nebenbedingungen erfüllt bleiben.

Sind erstmals alle NB erfüllt, dann erhält man die optimale Lösung.

ai max.Anzahl Münzen min.Betrag Münzensumme NB Nr. erfüllt

Lösungsweg
Spalte1= a_i     Sp2=max.Anzahl der Münzen  Sp3=min. Betrag  Sp4=Münzensumme  Spalte5=erfüllte NB Nr.

a1 + a2 ≤ 2	2	0,03 Euro	2	NB3, NB4, NB11
a3 ≤ 1	1	0,05 Euro	3	NB5
a4 + a5 ≤ 2	2	0,30 Euro	5	NB6, NB7, NB12
a6 ≤ 1	1	0,50 Euro	6	NB8
a7 ≤ 1	1	1,00 Euro	7	NB9, NB1
Summe	7	1,88 Euro

Abbruch durch Münzensumme =7 in NB1 erreicht, alle NB (auch NB10 a₈=0) erfüllt

Lösung:  Die 7 Münzen sind:  1ct, 2ct, 5ct, 10ct, 20ct, 50ct, 1€ ,  der Betrag ist 1,88 Euro

Dieser Lösungsweg ist etwas aufwändiger, ich hoffe er ist nachvollziehbar !

Nette Grüße  jomai

Comments

Ach ja, Nachtrag...

die Lösung zu b). lautet:

Für folgende Beträge braucht man immer genau 8 Münzen: (weniger geht nicht)

in Euro: 3,88 / 3,89 / 3,98 / 3,99 / 4,88 / 4,89 / 4,98 / 4,99.


"Ja, ich weiß, dass die Kids die Aufgabe intuitiv lösen können ! Ist ok.

Aber es ist ja auch mal interessant, leichte Probleme mit mathematischem Werkzeug (OR) zu lösen.

Bei schweren Problemen braucht man es sowieso..."

---

Lösung zu frage b)

---

1. Vielen Dank an jomai für seine Lösung.

2. Der Zusatz "wenn man passend bezahlen möchte" ist wegen Marcos Einkauf in Höhe von 3,88 € mehr als irreführend und eigentlich auch überflüssig. Erst wenn man die Lösung kennt, weiß man, was genau damit gemeint ist.

3. Weshalb sollte das Wort "benötigt" jemanden zu dieser Annahme und all diesen Bedingungen zwingen? Es liegt vielmehr an der Bezeichnung "mindestens".

4. Deshalb kann die Lösung niemals 0,07 € heißen, da man dafür mindestens zwei Münzen benötigt.