Zeigen Sie mit starker Induktion, dass jede Postgebühr ≥12 Cent mit 4-Centund 5-Cent Briefmarken exakt bezahlt …

Question

Hallo zusammen, bin wieder am grübeln... Die Teilaufgabe b habe ich schon nur a verstehe ich nicht...

Es sei A(n) eine Aussage deren Wahrheitsgehalt von n ∈ Nabhängt. Die starke Induktionsvoraussetzung lautet: Angenommen A(k) ist wahr für alle 1 ≤k ≤n. Auf dieser Basis wird im Induktionsschritt gezeigt, dass auch A(n + 1) wahr ist.

a) Zeigen Sie mit starker Induktion, dass jede Postgebühr ≥12 Cent mit 4-Centund 5-Cent Briefmarken exakt bezahlt werden kann

Comments

Hier reicht auch normale Induktion:

IA: 12ct = 3*4 Cent

IV: n≥12 ct lassen sich exakt in 4 und 5ct Stücken bezahlen

IS:

IB: Es lassen sich auch n+1 ct in 4 und 5ct Stücken bezahlen

Beweis: Da n≥12 werden für die exakte Bezahlung von n ct mindestens 3 Münzen benötigt, denn:

4+4=8<12, 4+5=9<12, 5+5=10<12

Falls in der Münzmenge von n ct mind. eine 4ct Münze auftaucht, ersetze genau eine davon durch eine 5ct Münze. Man erhält dann genau n-4+5 = n+1 ct.

Andernfalls befinden sich in der Münzmenge von n ct mindestens drei 5ct Münzen, ersetze von diesen genau drei 5ct münzen durch 4ct Münzen und füge eine 4ct Münze hinzu: n-3*5+4*4=n+1 ct.

Answer 1

Zeige, dass 12ct, 13 ct. 14 ct und 15 ct bezahlt werden können. Schlussfolgere, dann dann auch 16, 17, 18 und 19 ct bezahlt werden können...,