Induktion & russische Moneten < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | In Russland gab es Geldscheine zu 3 und zu 5 Rubel. Zeigen Sie, dass man damit jeden ganzzahligen Rubelbetrag größer als 7 Rubel bezahlen konnte, ohne dass herausgegeben werden muss. Man überlege sich zuerst eine präzise mathematische Formulierung dieser Aussage und beweise sie dann mit Induktion. |
Hallo,
ich habe leider teilweise damit Probleme, die Musterlösung zu verstehen:
Formal: Für alle r > 7 gibt es $a,b [mm] \in \IN,$ [/mm] so dass $3 [mm] \cdot [/mm] a + 5 [mm] \cdot [/mm] b = r.$
Wir zeigen die Aussage per (Werteverlaufs-)Induktion über $r [mm] \in \IN.$ [/mm] Die Induktionsbasis ist trivialerweise erfüllt, da 0 > 7 falsch ist. Induktionsschritt von r - 1 auf r. Sei $r [mm] \in \IN$ [/mm] beliebig gegeben und gelte die Aussage für alle r' < r. Wir müssen sie für r zeigen. Wir haben fünf Fälle.
Fall $r [mm] \le [/mm] 7.$ Da die Prämisse falsch ist, muss hier nichts gezeigt werden.
Fall r = 8. Wähle a = b = 1.
Fall r = 9. Wähle a = 3 und b = 0.
Fall r = 10. Wähle a = 0 und b = 2.
Fall $r [mm] \ge [/mm] 11.$ Nach Induktionsvoraussetzung für r' = r - 3 gibt es $a',b' [mm] \in \IN$ [/mm] mit $r' = 3 [mm] \cdot [/mm] a'+5 [mm] \cdot [/mm] b'.$ Wähle also a = a' + 1 und b = b'.
Da mir der Induktionsschritt ("Induktionsschritt von r - 1 auf r.") und die Aussage r' < r nicht klar sind, kann ich auch den letzten Fall nicht nachvollziehen. Hat vielleicht jemand ein paar hilfreiche Worte parat, was hier gemeint ist?
Vielen Dank!
Gruß
el_grecco
|
|
| |
|
Hallo grec,
blöder Beweis, scheint aber sauber formuliert.
Wenn man für r=8,9,10 gezeigt hat, dass die Zahlung (Aufteilung) möglich ist, ist man ja fertig. Alle größeren Zahlen lassen sich dann ja mühelos durch Addition eines Vielfachen von 3 zu 8 oder 9 oder 10 darstellen, nichts anderes behauptet der letzte Schritt.
Ich würde ja ganz anders vorgehen und die Zahlen [mm] \mod{3} [/mm] betrachten. Die monetären Einheiten sind [mm] 3\equiv 0\mod{3} [/mm] und [mm] 5\equiv 2\mod{3}.
[/mm]
Also sind alle [mm] r\equiv 0\mod{3} [/mm] darstellbar (sogar r=0: man nehme 0 Scheine von jeder Sorte...).
Die [mm] r\equiv 2\mod{3} [/mm] sind nur für [mm] r\ge{5} [/mm] darstellbar.
Die [mm] r\equiv 1\mod{3} [/mm] sind nur für [mm] r\ge{10} [/mm] darstellbar.
Das heißt, dass nur [mm] r\in\{1,2,4,7\} [/mm] nicht darstellbar sind. Diese Aussage ist sogar weitergehend als die zu zeigende Aussage, die also darin vollständig enthalten ist.
Man könnte das gleiche [mm] \mod{5} [/mm] zeigen, aber es sind mehr Schritte nötig...
Grüße
reverend
|
|
|
| |
|
Hallo rev,
Danke für Deine Antwort.
Das Rechnen mit Modulo kam in der Vorlesung erst später vor, daher wohl diese alternative Lösung, welche mir leider noch immer nicht ganz klar ist.
Warum steht hier ein "Induktionsschritt von r - 1 auf r" und was meint das r' in der Aussage r' < r?
Dann nochmal zum letzten
Fall $ r [mm] \ge [/mm] 11. $ Nach Induktionsvoraussetzung für r' = r - 3 gibt es $ a',b' [mm] \in \IN [/mm] $ mit $ r' = 3 [mm] \cdot [/mm] a'+5 [mm] \cdot [/mm] b'. $ Wähle also a = a' + 1 und b = b'.
Warum r' = r - 3?
Viele Fragen, aber ich stehe hier leider fest auf dem Schlauch...
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:14 Do 05.07.2012 | | Autor: | fred97 |
> Hallo rev,
>
> Danke für Deine Antwort.
> Das Rechnen mit Modulo kam in der Vorlesung erst später
> vor, daher wohl diese alternative Lösung, welche mir
> leider noch immer nicht ganz klar ist.
>
> Warum steht hier ein "Induktionsschritt von r - 1 auf r"
> und was meint das r' in der Aussage r' < r?
>
> Dann nochmal zum letzten
>
> Fall [mm]r \ge 11.[/mm] Nach Induktionsvoraussetzung für r' = r - 3
> gibt es [mm]a',b' \in \IN[/mm] mit [mm]r' = 3 \cdot a'+5 \cdot b'.[/mm]
> Wähle also a = a' + 1 und b = b'.
>
> Warum r' = r - 3?
>
>
> Viele Fragen, aber ich stehe hier leider fest auf dem
> Schlauch...
Hallo Grieche,
komm ganz schnell runter von diesem Schlauch, denn er ist mit Retsina gefüllt ! Dieses , nach Kloreiniger schmeckende, Getränk mag der reverend zwar nicht, aber meine Frau Gemahlin um so mehr, und die will was davon abhaben.
Es gibt eine Variante des Induktionsbeweises:
Induktionsanfang: wie üblich.
Induktionsvoraussetzung: sei n [mm] \in \IN [/mm] und die Beh. gelte für alle m [mm] \in \IN [/mm] mit m [mm] \le [/mm] n.
Induktionsschritt: zeige, dass die Beh. auch für n+1 gilt.
Zu Deiner Frage: "Warum r' = r - 3?"
Es ist r'<r. Nach IV gibt es [mm]a',b' \in \IN[/mm] mit [mm]r' = 3 \cdot a'+5 \cdot b'.[/mm]
Dann ist $r=r'+3=3 [mm] \cdot [/mm] a'+5 [mm] \cdot [/mm] b' +3=3(a'+1)+5b'$
Grüße FRED
>
> Gruß
> el_grecco
>
|
|
|
| |
|
Hallo Fred,
> Hallo Grieche,
>
> komm ganz schnell runter von diesem Schlauch, denn er ist
> mit Retsina gefüllt ! Dieses , nach Kloreiniger
> schmeckende, Getränk mag der reverend zwar nicht, aber
> meine Frau Gemahlin um so mehr, und die will was davon
> abhaben.
beim nächsten Mal bin ich ehrlich und schreibe statt "stehe auf dem Schlauch" besser "ich hänge am Ouzo-Tropf, sehe nur noch die "12"". 
> Es gibt eine Variante des Induktionsbeweises:
>
> Induktionsanfang: wie üblich.
>
> Induktionsvoraussetzung: sei n [mm]\in \IN[/mm] und die Beh. gelte
> für alle m [mm]\in \IN[/mm] mit m [mm]\le[/mm] n.
>
> Induktionsschritt: zeige, dass die Beh. auch für n+1
> gilt.
>
Ich habe die alten Analysis-Unterlagen rausgeholt, aber ich bekomme es nicht hin (kein Witz: die Induktions-Aufgaben damals waren wirklich angenehmer).
> Zu Deiner Frage: "Warum r' = r - 3?"
>
> Es ist r'<r. Nach IV gibt es [mm]a',b' \in \IN[/mm] mit [mm]r' = 3 \cdot a'+5 \cdot b'.[/mm]
>
> Dann ist [mm]r=r'+3=3 \cdot a'+5 \cdot b' +3=3(a'+1)+5b'[/mm]
Danke, die Rechnung kann ich nachvollziehen und allmählich wird es mir klarer, wie kommt man aber auf die Zahl 3 in r' = r - 3?
Ich zerbreche mir auch den Kopf über den Induktionsschritt r-1 (angenommen man muss z.B. r = 17 Rubel zahlen, warum interessiert man sich dann für 16 Rubel?)...
Gruß
el_grecco
|
|
|
| |
|
Hallo nochmal,
> > komm ganz schnell runter von diesem Schlauch, denn er ist
> > mit Retsina gefüllt ! Dieses , nach Kloreiniger
> > schmeckende, Getränk mag der reverend zwar nicht, aber
> > meine Frau Gemahlin um so mehr, und die will was davon
> > abhaben.
Da bin ich nicht so sicher. Sie steht eher auf Roten.
> beim nächsten Mal bin ich ehrlich und schreibe statt
> "stehe auf dem Schlauch" besser "ich hänge am Ouzo-Tropf,
> sehe nur noch die "12"".
Schlecht. In dem Zustand kriegt man schnell einen auf die Zwölf...
> > Es gibt eine Variante des Induktionsbeweises:
> >
> > Induktionsanfang: wie üblich.
> >
> > Induktionsvoraussetzung: sei n [mm]\in \IN[/mm] und die Beh. gelte
> > für alle m [mm]\in \IN[/mm] mit m [mm]\le[/mm] n.
> >
> > Induktionsschritt: zeige, dass die Beh. auch für n+1
> > gilt.
>
> Ich habe die alten Analysis-Unterlagen rausgeholt, aber ich
> bekomme es nicht hin (kein Witz: die Induktions-Aufgaben
> damals waren wirklich angenehmer).
>
> > Zu Deiner Frage: "Warum r' = r - 3?"
> >
> > Es ist r'<r. nach="" iv="" gibt="" es="" <span="" class="math">[mm]a',b' \in \IN[/mm] mit [mm]r' = 3 \cdot a'+5 \cdot b'.[/mm]
> >
> > Dann ist [mm]r=r'+3=3 \cdot a'+5 \cdot b' +3=3(a'+1)+5b'[/mm]
>
> Danke, die Rechnung kann ich nachvollziehen und allmählich
> wird es mir klarer, wie kommt man aber auf die Zahl 3 in r'
> = r - 3?
Das müsste Dir bei der Variante in Modulrechnung klar werden. Eben weil es 3-Rubel-Scheine gibt! Wenn Du für eine natürliche Zahl s gezeigt hast, dass sie aus Dreiern und Fünfern zusammengesetzt werden kann, dann kann auch jede Zahl s+3k zusammengesetzt werden, [mm] k\in\IN. [/mm]
> Ich zerbreche mir auch den Kopf über den Induktionsschritt
> r-1 (angenommen man muss z.B. r = 17 Rubel zahlen, warum
> interessiert man sich dann für 16 Rubel?)...
Diese Angabe ist in der Tat Quatsch.
Im übrigen ist es doch egal, ob man von r-1 auf r schließt, oder (wie früher sozusagen) von n auf n+1. Dazu setze man r=n+1 und schon hat man seine alten Gewohnheiten wieder.
Es gab übrigens tatsächlich Dreirubelscheine!
lg
rev
</r.>
|
|
|
| |
|
Hallo rev,
ich bin zwar kein großer Freund von Wein, aber ich muss sagen, dass man den griechischen Wein nicht auf Retsina reduzieren darf (das haben sich aber die Griechen auch selbst zuzuschreiben). Es gibt zum Glück einige, wenn auch wenige griechische Weinerzeuger, die gegen diesen Hype ankämpfen und hochwertige Weine erzeugen, die aber nur den eingefleischten Kennern bekannt sind. Hier mal die beiden Geheimtipps "TRILOGIA" und "MOVA" vom Erzeuger
![[]](/images/popup.gif) Christos Kokkalis (seine Vita ist auch interessant).
> > Ich zerbreche mir auch den Kopf über den Induktionsschritt
> > r-1 (angenommen man muss z.B. r = 17 Rubel zahlen, warum
> > interessiert man sich dann für 16 Rubel?)...
>
> Diese Angabe ist in der Tat Quatsch.
Nur um sicher zu gehen: richtig wäre also "Induktionsschritt von r - 3 auf r"?
Vielen Dank nochmal!
Gruß
el_grecco
|
|
|
| |
|
Hallo grec,
> ich bin zwar kein großer Freund von Wein,
Gut. Dann bleibt mehr für mich.
> aber ich muss
> sagen, dass man den griechischen Wein nicht auf Retsina
> reduzieren darf
Oh, ich weiß. Und wenn man die Billigweine von Achaia Clauss auch noch streicht, bleiben ein paar recht gute übrig.
> (das haben sich aber die Griechen auch
> selbst zuzuschreiben). Es gibt zum Glück einige, wenn auch
> wenige griechische Weinerzeuger, die gegen diesen Hype
> ankämpfen und hochwertige Weine erzeugen, die aber nur den
> eingefleischten Kennern bekannt sind. Hier mal die beiden
> Geheimtipps "TRILOGIA" und "MOVA" vom Erzeuger
>
> Christos Kokkalis (seine Vita ist auch interessant).
Von dem höre ich hiermit zum zweiten Mal. Vielleicht muss ich da doch mal hin.
> > > Ich zerbreche mir auch den Kopf über den Induktionsschritt
> > > r-1 (angenommen man muss z.B. r = 17 Rubel zahlen, warum
> > > interessiert man sich dann für 16 Rubel?)...
> >
> > Diese Angabe ist in der Tat Quatsch.
>
> Nur um sicher zu gehen: richtig wäre also
> "Induktionsschritt von r - 3 auf r"?
Ja.
Es geht aber auch viel einfacher.
Ein altes russisches Mütterchen, das bei uns am Straßenrand gerade "dicke deutsche Kirschen" und unter der Theke frische selbstgemachte Pirogis verkauft, hat es mir gerade erklärt:
***
Towarischtsch, das kann doch jedes Kind.
Wenn bei dem Betrag, den Du um einen Rubel vermehren willst, ein Fünfer liegt, dann ersetzt Du ihn durch zwei Dreier, dann hast Du da einen mehr.
Wenn da kein Fünfer liegt, ersetzt Du drei Dreier durch zwei Fünfer, dann hast Du da auch einen mehr.
Darum muss erst einmal genügend Geld da sein, mindestens acht Rubel. Dann geht es immer, und sonst nur noch mit fünf Rubel.
Wenn Du also einen Rubel verschenken willst, dann solltest Du genügend Kopeken in der Tasche haben.
Darauf ich: und woher weiß ich, dass dann immer mindestens ein Fünfer dabei ist, oder eben mindestens drei Dreier?
Denkst Du zuviel oder zuwenig, Towarischtsch? Wenn kein Fünfer dabei sind, dann hast Du nur Dreier. Und wenn das keine drei sind, dann höchstens zwei, also sechs Rubel. Ich habe doch gesagt, es geht erst ab acht.
Moment: weil es für sechs nicht geht, geht es erst ab acht?
Wie machst Du denn sieben? Wenn ein Fünfer dabei ist, passt kein Dreier mehr dazu, und nur aus Dreiern gehts auch nicht.
Und wenn ich also jemandem einen Rubel wegnehmen will, dann ersetze ich also entweder zwei Fünfer durch drei Dreier, oder ich tausche zwei Dreier gegen einen Fünfer aus, richtig?
Wenn Du schon die zwei Fünfer oder die zwei Dreier weggenommen hast, dann solltest Du nicht noch Zeit darauf verschwenden, etwas hinzulegen. So wirst Du als Dieb nie Erfolg haben.
***
Unter uns Orthodoxen: da hat sie recht. Ich habe also meine Kirschen bezahlt und mich auf ein Pirogi einladen lassen. Lecker.
lg
rev
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:32 Fr 06.07.2012 | | Autor: | el_grecco |
Hallo rev,
> Von dem höre ich hiermit zum zweiten Mal. Vielleicht muss
> ich da doch mal hin.
sehr empfehlenswert!
> > > > Ich zerbreche mir auch den Kopf über den Induktionsschritt
> > > > r-1 (angenommen man muss z.B. r = 17 Rubel zahlen, warum
> > > > interessiert man sich dann für 16 Rubel?)...
> > >
> > > Diese Angabe ist in der Tat Quatsch.
> >
> > Nur um sicher zu gehen: richtig wäre also
> > "Induktionsschritt von r - 3 auf r"?
>
> Ja.
>
> Es geht aber auch viel einfacher.
>
> Ein altes russisches Mütterchen, das bei uns am
> Straßenrand gerade "dicke deutsche Kirschen" und unter der
> Theke frische selbstgemachte Pirogis verkauft, hat es mir
> gerade erklärt:
>
> ***
>
> Towarischtsch, das kann doch jedes Kind.
> Wenn bei dem Betrag, den Du um einen Rubel vermehren
> willst, ein Fünfer liegt, dann ersetzt Du ihn durch zwei
> Dreier, dann hast Du da einen mehr.
> Wenn da kein Fünfer liegt, ersetzt Du drei Dreier durch
> zwei Fünfer, dann hast Du da auch einen mehr.
> Darum muss erst einmal genügend Geld da sein, mindestens
> acht Rubel. Dann geht es immer, und sonst nur noch mit
> fünf Rubel.
>
> Wenn Du also einen Rubel verschenken willst, dann solltest
> Du genügend Kopeken in der Tasche haben.
>
> Darauf ich: und woher weiß ich, dass dann immer mindestens
> ein Fünfer dabei ist, oder eben mindestens drei Dreier?
>
> Denkst Du zuviel oder zuwenig, Towarischtsch? Wenn kein
> Fünfer dabei sind, dann hast Du nur Dreier. Und wenn das
> keine drei sind, dann höchstens zwei, also sechs Rubel.
> Ich habe doch gesagt, es geht erst ab acht.
>
> Moment: weil es für sechs nicht geht, geht es erst ab
> acht?
>
> Wie machst Du denn sieben? Wenn ein Fünfer dabei ist,
> passt kein Dreier mehr dazu, und nur aus Dreiern gehts auch
> nicht.
>
> Und wenn ich also jemandem einen Rubel wegnehmen will, dann
> ersetze ich also entweder zwei Fünfer durch drei Dreier,
> oder ich tausche zwei Dreier gegen einen Fünfer aus,
> richtig?
>
> Wenn Du schon die zwei Fünfer oder die zwei Dreier
> weggenommen hast, dann solltest Du nicht noch Zeit darauf
> verschwenden, etwas hinzulegen. So wirst Du als Dieb nie
> Erfolg haben.
>
> ***
>
Eine russische Anleitung zum Wulffen. Aber eine gute Geschichte! 
> Unter uns Orthodoxen: da hat sie recht. Ich habe also meine
> Kirschen bezahlt und mich auf ein Pirogi einladen lassen.
> Lecker.
>
Ein orthodoxer reverend? Russisch? Armenisch? Serbisch? ...?
> lg
> rev
>
Gruß
el_grecco
|
|
|
|
