Kleinstmöglichster Betrag ohne Wechselgeld berechnen?

Hallo, ich komme bei einer Hausaufgabe nicht weiter Die Aufgabe lautet:

Liesabyte, die Tochter von Prof. Bytewoman und Byteman, hat von ihrem Taschengeld die folgenden Münzen der in Bytetown verfügbaren Währung Bytecoins gespart: 7, 300, 35, 83, 1, 17, 2, 1, 17, 170, 5

Aufgabenstellung:

1. Welches ist der kleinst-möglichste Betrag (positiver Integer) den Liesabyte, ohne Wechselgeld entgegenzunehmen, nicht mit Ihrem Ersparten bezahlen kann?

2. Skizziere formell wie du zu deiner Lösung gekommen bist.

Ich habe jetzt halt keine Ahnung wie ich das machen soll und habe keine Lust das jetzt alles einzeln durchzurechnen. Kann mir einer vielleicht helfen?

Answer 1

[HEWKLDOe]

Hallo Losentos

Diese Art von Knobelaufgaben liebe ich. Sie sind nämlich ganz leicht zu lösen, wenn man das Lösungsschema erfasst hat.

Bei dieser Aufgabe sortiert man erst einmal die Zahlen (hier Bytecoins genannt) der Größe nach: 1, 1, 2,  5,  7,  17,  17,  35,  83,  170,  300.
Dann beginnt man links (bei den kleinen Zahlen) wie folgt:
Mit 1 und 1 kann ich bis 2 bezahlen.
Mit zusätzlich 2, kann ich bis 4 bezahlen, nämlich 1, 2, 3, 4 (=1+1+2).
Mit zusätzlich 5 kann ich bis 9 bezahlen, also bis 4+5=9
Mit zusätzlich 7 kann ich bis 16 bezahlen, also bis 9+7=16.
Mit zusätzlich 17 kann ich bis 33 bezahlen, also bis 16+17=33.
Mit zusätzlich 17 kann ich bis 50 bezahlen, also bis 33+17=50.
Mit zusätzlich 35 kann ich bis 85 bezahlen, also bis 50+35=85.
Mit zusätzlich 83 kann ich bis 168 bezahlen, also bis 85+83=168.
Da aber die nächstgrößere Münzeneinheit 170 ist, kann ich 169 nicht (ohne Wechselgeld zurück zu erhalten) bezahlen.

Es grüßt HEWKLDOe.

Answer 2

[Ewwas17]

Letztlich musst du den Intervall zwischen zwei Zahlen finden, der größer ist als die Summe aller darunter liegenden Zahlen.

Das ist beim Intervall 17-35 der Fall.

Denn 17+7+5+2+1+1=33

Das heißt der Betrag von 34 Bytecoins ist der kleinste, den sie nicht bezahlen kann.

Formell würde ich das so aufschreiben, auch wenn es bestimmt elegantere Wege gibt:

ai - ai-1 > a1+ a2...+ ai-1

Dabei sind a die jeweilig verfügbaren Bytecoinmengen also a1=1, a2=1, a3=2...

Comments

[Losentos]

34 lässt sich mit 17 + 17 bezahlen, da es zwei mal 17 gibt. Du hast aber trotzdem recht, da das gleiche bei 83-170 funktioniert.

Danke :D

[Ewwas17]

@Losentos

Haha :D stimmt. Es hilft tatsächlich, wenn man die Münzen sortiert. Die zweite 17 habe ich glatt übersehen.

Answer 3

[Willy1729]

Hallo,

Du arbeitest Dich von unten nach oben durch:

Mit den beiden Einsen und der Zwei kannst Du alle Zahlen von 1 bis 4 bilden.

Die 5 schließt lückenlos an, so daß nun schon Zahlen bis 9 gebildet werden können. Die 7 hast Du dazu noch nicht benötigt.

Kannst Du aber die Zahlen von 1 bis 9 bilden, kommst Du zusammen mit der 7 bis 16, an die wiederum 17 anschließt.

17+16 deckt alles bis 33 ab, die 34 ergibt 17+17, danach kommt schon 35.

Zusammen mit den 34 von vorhin kommst Du bis 69. Bis zur 82 fehlen noch 13, die ohne die beiden 17 gebildet werden kann. 83 ist vorhanden.

83+69=152, fehlen noch 17 bis zur 169. Jetzt wird's eng.

Um bis 152 zu kommen, benötigst Du die 83, die 35 und die beiden 17.

Die nächste Zahl, die Du hast, ist 170, Du mußt die 169 also aus 

83+35+17+17=152+17 bilden. Alle Zahlen bis auf die beiden Einser, die 2, die 5 und die 7 sind aber verbraucht und 1+1+2+5+7=16.

Damit kommst Du nur bis 168. Die 169 bekommst Du nicht zusammen.

Sie ist demnach die gesuchte kleinste Zahl, die mit dieser Währung nicht ohne Wechselgeld zu bezahlen ist.

Herzliche Grüße,

Willy