Autor |
Beitrag |
helmut (Hoocker)
| Veröffentlicht am Donnerstag, den 13. Dezember, 2001 - 17:04: |
|
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 |
Lars Brünjes (Lbrunjes)
| Veröffentlicht am Freitag, den 14. Dezember, 2001 - 10:34: |
|
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.:
| Betrag | ich bezahle | | Wechselgeld | | | 7-er | 5-er | 7-er | 5-er | 1 | 3 | 0 | 0 | 4 | 2 | 6 | 0 | 0 | 8 | 3 | 9 | 0 | 0 | 12 | 4 | 12 | 0 | 0 | 16 | ... | ... | ... | ... | ... | n | 3n | 0 | 0 | 4n | 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:
| Betrag | Siebener | Fünfer | 80 | 0 | 16 | 81 | 3 | 12 | 82 | 6 | 8 | 83 | 9 | 4 | 84 | 12 | 0 | | 85 | 0 | 17 | 86 | 3 | 13 | 87 | 6 | 9 | 88 | 9 | 5 | 89 | 12 | 1 | | 90 | 0 | 18 | 91 | 3 | 14 | ... | ... | ... | 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 |
SpockGeiger (Spockgeiger)
| Veröffentlicht am Sonntag, den 16. Dezember, 2001 - 13:42: |
|
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 |
Lars Brünjes (Lbrunjes)
| Veröffentlicht am Montag, den 17. Dezember, 2001 - 08:55: |
|
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 |
helmut (Hoocker)
| Veröffentlicht am Montag, den 17. Dezember, 2001 - 17:19: |
|
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 |
SpockGeiger (Spockgeiger)
| Veröffentlicht am Montag, den 17. Dezember, 2001 - 23:40: |
|
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 |
Zaph (Zaph)
| Veröffentlicht am Dienstag, den 18. Dezember, 2001 - 20:52: |
|
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. |
Zaph (Zaph)
| Veröffentlicht am Dienstag, den 18. Dezember, 2001 - 21:27: |
|
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. |
|