Flaschensammeln Rätsel

13.10.2014, 21:45

Knock^3-Penny

Flaschensammeln Rätsel

Hat man Flaschen gesammelt, und will sie im nächsten Supermarkt in neue Getränke um-
tauschen stellt sich manchmal folgendes Problem: Der Betrag, den das neue Getränk kostet,
lässt sich einfach nicht exakt mit den Flaschen bezahlen – z. B. die Wasserflasche für 34
Cent (inkl. Pfand): entweder man muss noch einen Cent drauf legen, oder man bekommt
vier Cent zurück. Ist der Betrag allerdings groß genug, kann dieses Problem nicht mehr
auftreten.
a) Nehmen Sie an, es gibt die folgenden Typen von Flaschen (was bis auf wenige patho-
logische Fälle der Realität entspricht):
• Bierflaschen – 8 Cent Pfand,
• Wasserflaschen (Mehrweg) – 15 Cent Pfand,
• Eistee-Flaschen (Einweg) – 25 Cent Pfand.
Geben Sie den größten Betrag (in Cent) an, der sich nicht passend mit diesen Flaschen
bezahlen lässt. Geben Sie diesen Betrag ohne führende Nullen an.

Hat jemand eine Idee???

Ich werde schon ganz irre... smile

Unendlich ist anscheinend nicht die Lösung!

EDIT(Helferlein): Da Du anscheinend selber die Lösung nicht kennst, ist dies nicht die richtige Kategorie für deine Frage. Beachte hierzu die Boarddefinition eines Rätsels.
Ich erlaube mir, den Beitrag in ein passenderen Bereich zu verschieben.

14.10.2014, 09:54

HAL 9000

Auf diesen Beitrag antworten »

Es gilt folgendes Lemma:

Zitat:

Es seien $\begin{align*} a,b \end{align*}$ zwei positive teilerfremde Zahlen. Dann ist $\begin{align*} ab-a-b \end{align*}$ die größte ganze Zahl, die sich nicht in der Form $\begin{align*} ma+nb \end{align*}$ mit nichtnegativen ganzen Zahlen $\begin{align*} m,n \end{align*}$ darstellen lässt.

Es geht hier nun um den Gesamtpreis $\begin{align*} p = 8x + 15y + 25z = 8x + 5(3y+5z) = 8x+5t \end{align*}$ mit $\begin{align*} t=3y+5z \end{align*}$ .

Kommen wir zunächst zu $\begin{align*} t \end{align*}$ : Laut Lemma können wir alle Werte größer als $\begin{align*} 3\cdot 5-3-5=7 \end{align*}$ in der Form $\begin{align*} 3y+5z \end{align*}$ darstellen.

Zurück zu $\begin{align*} p = 8x + 5(t-8) + 40 \end{align*}$ : Laut Lemma können wir garantiert alle Werte größer als $\begin{align*} 8\cdot 5-8-5 = 27 \end{align*}$ in der Form $\begin{align*} 8x+5t' \end{align*}$ darstellen, mithin dann also alle Werte größer als $\begin{align*} 27+40 = 67 \end{align*}$ in der gewünschten Form $\begin{align*} 8x+5t = 8x + 15y + 25z \end{align*}$ .

Nehmen wir uns doch die 67 selbst vor, d.h. wir überprüfen die Lösbarkeit von $\begin{align*} 67 = 8x+15y+25z \end{align*}$ im nichtnegativen Bereich:

Modulo 5 ergibt sich $\begin{align*} 2 \equiv -2x \bmod 5 \end{align*}$ , also $\begin{align*} x\equiv -1 \equiv 4\bmod 5 \end{align*}$ oder anders ausgedrückt $\begin{align*} x=5u+4 \end{align*}$ . Dies eingesetzt und umgestellt ergibt $\begin{align*} 7 = 8u+3y+5z \end{align*}$ . Offenbar muss dann $\begin{align*} u=0 \end{align*}$ sein, und dass aber $\begin{align*} 7=3y+5z \end{align*}$ keine nichtnegative Lösung besitzt, haben wir oben schon festgestellt.

14.10.2014, 12:33

Knock^3-Penny

Auf diesen Beitrag antworten »

Danke dir. Das klingt logisch... Werde mal ausführlich darüber nachdenken. Freude

14.10.2014, 12:54

HAL 9000

Auf diesen Beitrag antworten »

Für den eigentlichen Nachweis, dass 67 die gesuchte Zahl ist, braucht man das Lemma nicht wirklich - ich habe es nur angeführt, um zu erklären, wie man ohne groß rumzuprobieren auf den Wert kommt.

14.10.2014, 13:31

URL

Auf diesen Beitrag antworten »

Wie sieht man ohne das Lemma, dass alle Zahlen zwischen 68 und 99 darstellbar sind?
Ich habe mit den Resten von 8,15,25 mod 8 argumentiert, dass die kleinste Zahl darstellbare Zahl p mit $\begin{align*} p \equiv 3 \bmod 8 \end{align*}$ die 75 ist. Das liefert 67 als nicht darstellbare.
Aber dann muss ich das analog für die übrigen Reste überlegen, was nahe am Probieren ist Augenzwinkern

14.10.2014, 13:35

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von URL
Wie sieht man ohne das Lemma, dass alle Zahlen zwischen 68 und 99 darstellbar sind?

Gib einfach für die 8 aufeinander folgenden Werte 68..75 jeweils direkt passende Kombinationen an. Wie es damit dann weitergeht, sollte doch klar sein, oder?

14.10.2014, 13:40

URL

Auf diesen Beitrag antworten »

ja, dann ist es klar

14.10.2014, 14:03

tmo

Auf diesen Beitrag antworten »

Eine andere Möglichkeit das einzusehen bzw. die 67 zu finden, wäre die folgende (Und das gibt auch gleich einen Existenzbeweis für den allgemeinen Fall von beliebig vielen Zahlen ohne gemeinsamen Primteiler):

Klar ist: Sobald wir 2 aufeinander folgende Zahlen darstellen können, kriegen wir über die 3 verschiedenen Summen, die wir mit dieser beiden Zahlen bilden können, 3 aufeinander folgende darstellbare Zahlen.

Dann bilden wir wieder alle möglichen Summen und erhalten 5 aufeinander folgenden Zahlen usw...Das Argument zieht man durch bis man (wie HAL ja eben schon gesagt hat) so viel aufeinanderfolgende darstellbare Zahlen gefunden, wie die kleinste darstellbare Zahl (hier 8) angibt.

Konkret wäre das in dem Beispiel so:

Man findet schnell 15 und 16 als darstellbar.
Durch Summenbildung findet man 30,31,32 und sieht dann, dass auch noch 33 passt.

Durch weitere Summenbildung sieht man, dass die Zahlen 60-66 darstellbar sind, also fehlt nur noch eine.

Dann stellt man fest, dass 59 und 67 aber nicht passen, also geht man durch Addition mit 8 zu 68-74 über und findet, dass die 75 auch noch darstellbar ist. Fertig.

Dass aus diesen Überlegungen der allgemeine Fall folgt, ist klar:

Hat man $\begin{align*} n \end{align*}$ natürliche Zahlen $\begin{align*} a_1 < \dotsc < a_n \end{align*}$ , die teilerfremd (aber natürlich nicht notwendigerweise paarweise) sind, so gibt es ganze Zahlen $\begin{align*} b_i \end{align*}$ mit $\begin{align*} 1 = \sum b_ia_i \end{align*}$ .

Nun bringen wir alle Summanden mit negativem $\begin{align*} b_i \end{align*}$ auf die linke Seite und haben so zwei aufeinanderfolgende darstellbare Zahlen gefunden und obige Maschine fängt an zu rollen, womit bewiesen ist, dass nur endlich viele Zahlen nicht darstellbar sind. Dieser Beweis macht im Gegensatz zu dem obigen Lemma natürlich keine (bzw. nur eine sehr schwache) Aussage über die Größe der größten nichtdarstellbaren Zahl.

Das Lemma wäre übrigens eine gute Aufgabe für den Schulmarathon, oder nicht? Augenzwinkern

14.10.2014, 14:15

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Das Lemma wäre übrigens eine gute Aufgabe für den Schulmarathon, oder nicht? Augenzwinkern

Stimmt, aber vielleicht eher Übergangs-Marathon. Die "Erweiterung"

Zitat:

Es seien $\begin{align*} a,b,c \end{align*}$ drei positive paarweise teilerfremde Zahlen. Dann ist $\begin{align*} 2abc-ab-bc-ca \end{align*}$ die größte ganze Zahl, die sich nicht in der Form $\begin{align*} mab+nbc+kca \end{align*}$ mit nichtnegativen ganzen Zahlen $\begin{align*} m,n,k \end{align*}$ darstellen lässt.

war in den 1980ern tatsächlich sogar mal IMO-Aufgabe. Augenzwinkern

EDIT: Form korrigiert, Dank an tmo.

14.10.2014, 14:32

tmo

Auf diesen Beitrag antworten »

Für 2,3 und 5 kommt da 29 raus verwirrt

14.10.2014, 14:34

HAL 9000

Auf diesen Beitrag antworten »

Entschuldigung, beim Copy+Paste sollte man auch wirklich alles ändern: Statt $\begin{align*} ma+nb+kc \end{align*}$ muss da $\begin{align*} mab+nbc+kca \end{align*}$ stehen. smile

14.10.2014, 17:45

tmo

Auf diesen Beitrag antworten »

So wird ein Schuh draus. Interesanterweise ist die Erweiterung (die ja für c=1 das alte Lemma ergibt) gar nicht echt schwerer. Wer das Lemma bewiesen hat, wird wohl auch die Erweiterung schaffen.

Die Schwierigkeit damals bei der IMO entstand wohl dadurch, dass man das Lemma gar nicht kannte.

Neue Frage »

Antworten »

Flaschensammeln Rätsel

Verwandte Themen