Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

Währungsproblem

ZahlReich - Mathematik Hausaufgabenhilfe » Denksport » Unterhaltungsmathematik » Währungsproblem « Zurück Vor »

Das Archiv für dieses Kapitel findest Du hier.

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

helmut (Hoocker)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Donnerstag, den 13. Dezember, 2001 - 17:04:   Beitrag drucken

Mein Sohn hat von seinem Mathe-Lehrer folgende Aufgabe bekommen:

Es gibt ein Land das eine Währung hat, die nur auf zwei Einheiten beschränkt ist, z. B. einen 5-Einheiten-Chip und einen 7-Einheiten-Chip. Was ist der größte Preis, der nicht durch exaktes Wechseln bezahlt werden kann? Was ist die generelle Regelung für Währungen, die auf zwei Einheiten x und y beschränkt sind?

Wie sieht das ganze ohne Wechseln aus, also ohne Wechselgeld zu bekommen?

Hat jemand eine Idee, wie man so etwas rechnet??

big thx im voraus
helmut
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Lars Brünjes (Lbrunjes)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 14. Dezember, 2001 - 10:34:   Beitrag drucken

Hallo, Helmut!

In dem Beispiel mit 5,7 kann man jeden (ganzzahligen) Betrag bezahlen, sofern man Wechselgeld bekommt. Der Grund ist, daß man 1 Einheit bezahlen kann, indem man 3 7-er Chips abgibt und 4 5-er Chips Wechselgeld bekommt. Also z.B.:

Betragich bezahleWechselgeld
7-er5-er7-er5-er
13004
26008
390012
4120016
...............
n3n004n


Natürlich gibt es i.a. mehrere Möglichkeiten, einen bestimmten Betrag zu bezahlen, aber die genannte Methode funktioniert immer.

Offenbar ist der Grund dafür, daß man jeden Betrag bezahlen kann, der, daß ich 1=3*7-4*5 habe, daß ich also die Zahl 1 aus Siebenen und Fünfen zusammenbauen kann. Für zwei beliebige Zahlen x,y geht das nach einem bekannten mathematischen Satz aus der elementaren Zahlentheorie genau dann, wenn x und y teilerfremd sind, d.h. wenn ihr größter gemeinsamer Teiler 1 ist.

Z.B. sind auch 3 und 8 teilerfremd sowie 10 und 21, und man hat die Gleichungen 1=3*3-1*8 bzw. 1=1*21-2*10.

Sind x und y nicht teilerfremd und haben den größten gemeinsamen Teiler d, so kann man nur genau die Beträge zahlen, die durch d teilbar sind.

Ist z.B. x=4 und y=6, so ist d=2, und offenbar kann man nur geradzahlige (also durch d teilbare) Beträge bezahlen - dann allerdings wieder alle, denn so wie man im Falle d=1 immer ganze Zahlen a,b findet mit 1=a*x+b*y, so findet man allgemein stets ganze Zahlen a,b mit d=a*x+b*y, im Beispiel etwa 2=1*6-1*4.

Anders sieht die Sache aus, wenn man kein Wechselgeld zurückbekommt.

Schauen wir uns wieder das Beispiel mit 5 und 7 an. Angenommen, ich finde einen Betrag n, den ich ohne Wechselgeld bezahlen kann, derart, daß ich auch n+1,n+2,n+3 und n+4 ohne Wechselgeld bezahlen kann, d.h. ich kann fünf aufeinanderfolgende Beträge bezahlen. Dann kann ich ab n wieder jeden Betrag bezahlen, denn mit n kann ich durch Zulegen von Fünfern auch n+5, n+10, n+15 usw. bezahlen, also auch n+5+1, n+5+2,n+5+3,n+5+4,n+10+1,n+10+2 usw.

Nehmen wir uns die Gleichung 1=3*7-4*5 vor. Da ich kein Wechselgeld bekomme, ist die (-4) schelcht - es sei denn, ich habe genügend Fünfer, die sowieso dabei sind - in diesem Fall brauche ich mindestens 16 Fünfer (da ich zu n viermal 1 addieren will), d.h. ich wähle n=16*5=80:

BetragSiebenerFünfer
80016
81312
8268
8394
84120
85017
86313
8769
8895
89121
90018
91314
.........


Vielleicht ist 79 nicht die größte Zahl, die man ohne Wechselgeld nicht bezahlen kann (womöglich kann man 79 sogar bezahlen), aber wir haben zumindest bewiesen, daß man ab 80 jeden Betrag bezahlen kann. Im Prinzip muß man jetzt nur von 79 an rückwärts gehen und eine Zahl suchen, die man nicht bezahlen kann - das ist dann die größte.

Für allgemeines teilerfremdes x,y zeigen dieselben Überlegungen, daß man ab einem bestimmten Betrag mit Sicherheit jeden Betrag bezahlen kann. Ist z.B. 1=a*x-b*y, so kann man ab dem Betrag b*(y-1)*y alles bezahlen - vielleicht aber auch schon vorher, aber das sind nur endlich viele Beträge, die man (im Prinzip) einzeln ausprobieren kann.

Sind x,y nicht teilerfremd, so kann man stets nur durch d teilbare Beträge bezahlen - aber dieselbe Überlegung zeigt, daß man ab einem hinreichend großen Betrag jeden durch d teilbaren Betrag bezahlen kann.

Ich hoffe, meine Ausführungen helfen Deinem Sohn ein wenig!

Viele Grüße -
Lars
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

SpockGeiger (Spockgeiger)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Sonntag, den 16. Dezember, 2001 - 13:42:   Beitrag drucken

Hallo Lars

Wahrscheinlich bin ich grad blind, aber wo kommst Du bei deinem letzten Beispiel darauf, dass Du 16 Fünfer nehmen musst?

viele Grüße
SpockGeiger
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Lars Brünjes (Lbrunjes)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Montag, den 17. Dezember, 2001 - 08:55:   Beitrag drucken

Hallo, SpockGeiger!

Meine Überlegung war die folgende: Ich benutze die Gleichung 1=3*7-4*5, und ich muß 5 aufeinanderfolgende Zahlen darstellen können, um dann alle folgenden Zahlen darstellen zu können. Um gemäß meiner Gleichung 1 zu addieren, muß ich drei 7-er addieren und 4 5-er wegnehmen. Ich muß viermal 1 addieren, um meine fünf aufeinanderfolgenden Zahlen zu erhalten, d.h. ich muß 4*4 5-er wegnehmen, muß also vorher mindestens 16 5-er gehabt haben.

Im übrigen behaupte ich ja nicht, daß 80 wirklich der kleinste Betrag ist, mit dem das geht - ich wollte ja nur beweisen, daß man ab einem bestimmten Betrag N alle Beträge >=N bezahlen kann, und im Fall N=80 sah ich besonders leicht, daß es stimmt - mit obiger Argumentation.

Viele Grüße -
Lars
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

helmut (Hoocker)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Montag, den 17. Dezember, 2001 - 17:19:   Beitrag drucken

hi,

Ich hab die Lösung gefunden:

Ohne Wechselgeld ergibt sich die Formel (x - 1) * (y - 1) - 1 für den höchsten nicht bezahlbaren Betrag, also bei 5 DM und 7 DM sind das 23 DM
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

SpockGeiger (Spockgeiger)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Montag, den 17. Dezember, 2001 - 23:40:   Beitrag drucken

Hallo Lars

Fühl Dich bitte nicht auf den Schlips getreten. Ich wollte auf keinen Fall was bemeckern, ich hatte nur nicht verstanden, wie Du überhaupt auf die Zahl 16 kamst. Vielen Dank für die Erklärung, jetzt verstehe ich es.

Hallo Helmut

Kannst Du das auch beweisen? würde mich sehr interessieren.

viele Grüße
SpockGeiger
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Dienstag, den 18. Dezember, 2001 - 20:52:   Beitrag drucken

Hier ist Teil 1 des Satz von Helmut:

Es seien x,y > 0 mit ggT(x,y) = 1.

Angenommen, es gibt a,b >= 0 mit ax + by = (x - 1)(y - 1) -1.

Hieraus folgt (a + 1)x + (b + 1)y = xy (*).

Aus (*) folgt einerseits (b + 1)y = x(y - a - 1)
Da ggT(x,y) = 1, folgt nun, dass x ein Teiler von b + 1 sein muss. Insbesondere also x <= b+1.

Andererseits folgt aus (*) analog y <= a + 1.

Hieraus ergibt sich
2xy = yx + xy <= (a + 1)x + (b + 1)y,
und mit (*) also
2xy <= xy. Widerspruch :-)

Um den Rest der Helmut'schen These zu beweisen, ist zu zeigen, dass für jedes c >= (x - 1)(y - 1) Zahlen a,b >= 0 existieren mit ax + by = c.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Dienstag, den 18. Dezember, 2001 - 21:27:   Beitrag drucken

Voilà! Hier ist der Rest.

Sei Ax + By = c (*).
(Solche A und B gibt es, da c ein Vielfaches von ggT(x,y) = 1 ist. Das folgt aus dem euklidischen Algorithmus. Will ich jetzt nicht näher drauf eingehen.)

Mindestens eine der beiden Zahlen A oder B ist nicht negativ. Wir betrachten den Fall, dass A >= 0 - der andere Fall ist analog zu behandeln.

Aus (*) folgt (A - ky)x + (B + kx)y = c für jede natürliche Zahl k.

Wähle k maximal, sodass A - ky >= 0.

Wenn B + kx >= 0, dann ist alles klar und wir sind fertig. Setze nämlich a := A - ky, b := B + kx

Sei nun B + kx <= -1. Wollen zeigen, dass dies unmöglich ist.

Da k maximal gewählt wurde, folgt A - (k + 1)y <= -1.

Damit ist
c = (A - (k + 1)y) x + (B + (k + 1)x) y
= (A - (k + 1)y) x + (B + kx) y + xy
<= (-1) x + (-1) y + xy
= (x - 1)(y - 1) - 1

Das ist ein Widerspruch zu c >= (x - 1)(y - 1)

Schönen Gruß

Z.

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page