vollständige indukion /textauf < Analysis < Hochschule < Mathe < Vorhilfe
|
Ich habe die vollständige Induktion noch nicht wirklich ganz verstanden, also was Ziel dieser ganzen SAche ist. Vielleicht kann mir das erstmal jemand behilflich sein? Das wäre lieb! :)
Dann habe ich folgende Aufgabe :
In der ehemaligen Sowjetunion gab es Geldscheine im Wert von 3 Rubel und 5 Rubel. Man zeige ( induktion ) dass man jeden rubelbetrag der größer als 7 ist, mit solchen geldscheinen bezahlen kann, ohne dass herausgegeben werden muss.
Und damit weiß ich leider gar nichts anzufangen :(
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:47 So 29.05.2005 | | Autor: | Faenol |
Hi !
Du müßtest eigentlich zeigen,dass wenn n>7 ist, dass es dann möglich ist, diese Zahl n dann nur mit der 3 und der 5 (Primfaktoren) darzustellen.
Bsp: n=13=2*5+1*3
Mit der Induktion zeigst du zuerst, dass es für einen Anfang gilt(n=8) und dann zeigst du, dass es für die weiteren auch gilt. Wenn der Dominostein kippt, dann kippt auch der nächste...
Aber machen wir zuerst den Induktionsanfang.
n=8
8=5+3 stimmt also
Behauptung: Jedes n>7 lässt sich durch a*5+b*3 darstellen. Für a,b [mm] \in \IN [/mm] (aber mit der 0)
Die Induktionsbehauptung gelte nun bis n.
Induktionsschritt: n [mm] \to [/mm] n+1
A(n+1)=n+1=a*5+b*3+1=a*5+b*3+6-5=a*5+b*3+2*3-5*1=5*(a-1)+3*(b+2)
Aufgrund des Kommentars von Marc (siehe später):
Jetzt muss man aber noch zeigen, dass a-1 [mm] \ge0 [/mm] ist, denn negative Schein Anzahl gibts net ! Da happerts bei mir ! Eigentlich ist das klar, aber mathematisch korrekt ist folgendes nicht:
z.z. a [mm] \ge [/mm] 1
8=5*1+1*3
9=5*0+3*3
10=5*2+0*3
Wenn n [mm] \ge [/mm] 10 ist, dann ist das sicherlich richtig, da dann immer [mm] a-1\ge2 [/mm] gilt. Bei n=9 soll a-1 = 0 sein und bei n=8 a-1 = 1.
Also verallgemeinernd a-1 [mm] \ge [/mm] 0
Im Prinzip macht nur die 9 Probleme....
Faenôl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:53 So 29.05.2005 | | Autor: | Marc |
Hallo Faenôl!
> Induktionsschritt: n [mm]\to[/mm] n+1
>
> A(n+1)=n+1=a*5+b*3+1=a*5+b*3+10-9=a*5+b*3+5*2-3*3=5*(a+2)+3*(b-3)
Aber wie stellst du denn hier sicher, dass [mm] $b-3\in\IN$? [/mm] Eine negative Anzahl Scheine wäre schlecht...
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:21 So 29.05.2005 | | Autor: | Faenol |
Hi Marc !
Stimmt, hast Recht ! Genau aus diesem Grund (wobei ich den speziel net wußte, sondern eh weil irgendwas immer happert, schreib ich auch nur Mitteilungen) !
Hab meine Antwort editiert, aber nun muss noch [mm] a-1\ge [/mm] 0 gezeigt werden, und eigentlich hatte man ja angenommen a [mm] \in \IN [/mm] mit 0.....
*grübel*
Faenôl
|
|
|
| |
|
Hallo!
Ich würde die Aufgabe so lösen:
Induktionsanfang:
Für $8$ Rubel gilt: $8=3+5$.
Für $9$ Rubel gilt: $9=3*3$.
Für $10$ Rubel gilt: $10=2*5$.
Induktionsannahme: [mm] $N\to [/mm] N+1$
Sei die Behauptung für $7< n [mm] \le [/mm] N$ gezeigt, wobei [mm] $N\ge [/mm] 10$.
Induktionsschritt:
$N+1=(N-2)+3$.
Nach Induktionsannahme gibt es eine Darstellung $N-2=a*3+b*5$ (weil [mm] $N-2\le [/mm] N$ und $N-2>7$), mit [mm] $a,b\in\IN_0$. [/mm] Damit gilt:
$N+1=(N-2)+3=a*3+b*5+3=(a+1)*3+b*5$.
Gruß, banachella
|
|
|
|
