| Autor |
Beitrag |
    
UniMicha
| | Veröffentlicht am Mittwoch, den 24. Oktober, 2001 - 17:08: | 
|
Hilfe! Habe folgende Aufgabe in einer Übung:
Folgende Aufgabe ist mit einer vollständigen Induktion zu beweisen:
In Russland gibt es Geldscheine im Werte von 3 Rubel und 5 Rubel. Man beweise, dass man jeden Rubelbetrag, der grösser als 7 ist, mit solchen Geldscheinen bezahlen kann, ohne dass herausgegeben werden muss. |
matroid
| | Veröffentlicht am Mittwoch, den 24. Oktober, 2001 - 19:58: |
|
Ind.Anfang
8 = 5+3
9 = 3*3
10 = 2*5
Ind.Voraussetzung.
Für alle Zahlen n<=n-{0} ist n als Summe von 3-en und 5-en darstellbar.
Ind.schluß n->n+1 (n>=10)
Wenn n>=10, dann ist n+1>=11 und n+1-3>=8
Wenn n+1-3 entweder 8 oder 9 oder 10 ist, dann kann man eine Lösung für n+1 angeben, indem man die Lösung für n+1-3 nimmt und eine 3 hinzufügt.
Wenn n+1-3>=10 ist, dann kann ma nochmal 3 abziehen usw. bis n+1-k*3<=10.
Die Lösung ist dann die von n+1-3k plus k mal die 3.
Gruß
Matroid
n+1 = (i*3+j*5) + 1 |
|
